Aycan iRiCAN wrote:
Merhaba,
Bahsedilen BFS algoritmasının ağaçlar (trees not graphs) üzerinde
çalıştığını hatırlatmakta fayda var. Paul Graham'ın algoritması yapay
zeka programlamada kullanılan temel arama algoritmalarından belkide en
basitinin kısaca yazılmış hali.
"In computer science <http://en.wikipedia.org/wiki/Computer_science>,
*breadth-first search* (*BFS*) is a tree search algorithm
<http://en.wikipedia.org/wiki/Tree_search_algorithm> used for traversing
or searching a tree <http://en.wikipedia.org/wiki/Tree_data_structure>,
tree structure <http://en.wikipedia.org/wiki/Tree_structure>, or graph
<http://en.wikipedia.org/wiki/Graph_%28data_structure%29>. The algorithm
begins at the root node
<http://en.wikipedia.org/wiki/Node_%28computer_science%29> and explores
all the neighboring nodes. Then for each of those nearest nodes, it
explores their unexplored neighbor nodes, and so on, until it finds the
goal."
Graf üzerinde calismamasi gibi bir durum söz konusu degil bildigim
kadari ile. Bu baglamda, bir graf
üzerinden ilerlerken bir agac olusturmus olursunuz.
Asagidaki kaynaklar benzer seyler söylüyor:
1- http://en.wikipedia.org/wiki/Breadth-first_search
2- *Artificial Intelligence: A Modern Approach*. (Second Edition) by
Stuart Russell
and Peter Norvig, 3. bölüm
Siz assoc'da ne gibi bir problem gördünüz bilmek isterim.
'((1 5 ) (5 1 12 17) ( 12 26 28 55) (17 1)) listesi bir ağaç olmadığı
için algoritma döngüye giriyor. Burada 1 numaralı düğüm (node) sadece
5'i gösteriyor, halbuki 17'yi de göstermeliydi (there is a cycle
here. aynı durum listenin ikinci elemanında 5'in 1'i göstermesinde de
mevcut). Aksi olursa bu düğümlerin çift yönlü yollar ile bağlandığı
bir grafiğe dönüyor.
Değişkenleri düzgün verirsek algoritma gayet hızlı çalışıyor.
CORE> (time (shortest-path 1 54 '((1 5 17) (5 12 17) (12 26 28 55))))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 29 cons cells, 0 other bytes, 0 static bytes
NIL
Biraz daha ayrıntılı anlatacak olursak:
CORE> (shortest-path '1 '2 '((1 3) (2 1) (3 1)))
Yukarıdaki yanlış kullanımı düşünelim. Fonksiyona verdiğimiz başlangıç
değer (1) ve bitiş değeri (2). Ancak ağaç yerine çift yönlü bir grafik
vermiş olalım ( ((1 3) (2 1) (3 1)) listesinde 1 3'ü 3 ise 1'i
döngüsel olarak gösteriyor).
Bu durumda her adımda algoritmanın kullandığı kuyruk (QUEUE as Q)
şöyle gidecektir.
1. ((1)) - Başlangıç olarak Q sadece ilk değeri içerir.
2. ((3 1)) - İlk değer olan (1) çıkarılır, yerine 1'e bağlı
diğer yollar eklenir.
3. ((1 3)) - İlk değer olan (3 1) çıkarılır, yerine 3'e bağlı
diğer yollar eklenir.
4. ((3 1)) - Burada döngü başlayacaktır.
5. ...
6. ...
Graham'ın algoritması kanımca böyle döngüler içeren bir grafikle ancak
*ziyaretçi listesi* (visitor list) tutarak çalışabilir. Bu da fazladan
(en kötü ihtimalle b^(d+1)) hafıza kullanmak demektir.
Bence bahsedilen web sayfasının problemi veritabanındaki bilgilerin
ağaç haline getirilerek işlenmesi ile çözülebilir. Ya da "new-paths"
adlı *successor* fonksiyon (x durumunda S(x), x'in ulaşabileceği yeni
durumları üretir) veritabanındaki bilgilerden durum üretecek şekilde
yazılabilir.
Bir de BFS üzerinde ısrarcı olmamak gerekebilir, veritabanı nasıl bir
durumda bilmiyorum ama alternatif (PDS gibi) bir çok arama stratejisi
uygulanabilir diye düşünüyorum. Umarım başınızı ağrıtmamışımdır.
Sevgiler...
Chris Stephenson <[EMAIL PROTECTED]> writes:
Emre and everyone
Kod düzgün çalışmıyor....
The Graham code , even with input in the correct format, does NOT work
correctly.
Consider this input
(shortest-path 1 54 '((1 5 ) (5 1 12 17) ( 12 26 28 55) (17 1)))
This should produce the answer () or nil, because there is no path from 1 to 54.
It does not. The fact that it does not also exposes indirectly the algorithmic
problem with his code.
------------------------------------------------------------------------
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
--
Emre Sevinç
eMBA Yazılım Geliştirme
İstanbul Bilgi Üniversitesi
<http://getfirefox.com/>
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
