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.
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.
>
--
Aycan iRiCAN
C0R3 Computer Security Group
http://www.core.gen.tr
pgpzUyXiI1C0t.pgp
Description: PGP signature
_______________________________________________ cs-lisp mailing list [email protected] http://church.cs.bilgi.edu.tr/lcg http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
