Re: [cs-lisp] Re: Another programming challenge - Another Clue Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
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 cs-lisp@cs.bilgi.edu.tr 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 cs-lisp@cs.bilgi.edu.tr http://church.cs.bilgi.edu.tr/lcg http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
Re: [cs-lisp] Re: Another programming challenge - Another Clue Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
Emre Sevinç wrote:
Graf üzerinde calismamasi gibi bir durum söz konusu degil bildigim
kadari ile. Bu baglamda, bir graf üzerinden ilerlerken bir agac
olusturmus olursunuz.
Mrb,
http://en.wikipedia.org/wiki/Breadth-first_search adresini oneriniz
uzerine ziyaret ettim. Bu algoritmayi daha once dosya sistemini gezmek
icin kullanmi$tim, bu yuzden ornekler verip deneyimimi aktarabilirim.
*function* breadthFirstSearch (Start, Goal) {
enqueue(Queue,Start)
*while* notEmpty(Queue) {
Node := dequeue(Queue)
*if* Node = Goal {
return Node /*the code below does not get executed*/
}
*for each* Child *in* Expand(Node) {
*if* notVisited(Child) {
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}
Yukarida formal yapisini listeledigim BFS algoritmasinin graphleri
gezebilmesini (trees not graphs) saglayan bolumu a$agida listeledim:
*for each* Child *in* Expand(Node) {
*if* notVisited(Child) {
setVisited(Child)
enqueue(Queue, Child)
}
}
Buna karsin paul'un kodunda bu mevcut degil. Bu yuzden kod, ba$ladigi
yere donebilmekte ve sonsuz donguye girebilmektedir.
Anlamakta zorluk cekenler icin gercek bir ornek vereyim istedim. Ornegin
bir dizindeyiz ve tum dosyalari sirayla gezmek istiyoruz. Regular file
olan dosyalari ilk dongude dolasiyoruz, buldugumuz alt dizinleri
kuyruk'a ekliyoruz. Burada yapi sadece agac olursa sorun yok. Buna
karsin, dosya sistemi, symlink'ler ile graph yapisina da sahip
olabilmekte. Bu durumda, herhangi bir symlink bizi basladigimiz yere
goturebilir, bu yuzden ziyaret ettigimiz yerleri hatirlamamiz $art.
Sonuc olarak, BFS evet, tree ve graph yapilarini gezebilir, buna kar$in,
yukarida bahsettigim sebeptendir ki, paul'in BFS uygulamasi yanlizca
tree'ler uzerinde calisabilir.
Saglicakla,
Evrim.
___
cs-lisp mailing list
cs-lisp@cs.bilgi.edu.tr
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
Re: [cs-lisp] Re: Another programming challenge - Another Clue Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
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 cs-lisp@cs.bilgi.edu.tr http://church.cs.bilgi.edu.tr/lcg http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
[cs-lisp] Re: Another programming challenge - Another Clue Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
Emre and everyone Kod dzgn almyor 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 Emre Sevinc wrote: RE: Another programming challenge - Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili - -Original Message- From: Chris Stephenson [mailto:[EMAIL PROTECTED]] Sent: Sat 12/17/2005 12:07 AM To: Emre Sevinc Cc: cs-lisp@cs.bilgi.edu.tr; cs-discuss; [EMAIL PROTECTED]; [EMAIL PROTECTED] Subject: Another programming challenge - Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili - Aldigin Kod Paul Graham'in "Ansi Common Lisp" kitabindan. Maalesef kitap online degil ve elimde degil ve kutuphane'de "out". Graham'in kodun hangi sorunu zdgn iddia ettigini grmek isterim. Kitap muhtemelen Sinan'da ya da Can Burak'ta ya da Haldun'da (ya da baska bir Common Lisp sevdalisinda, kim acaba? ;-) Bu kod bu sorunu zmyor, zemez. Istersen bunu deneyin! Try this! (shortest-path '1 '26 '((1 5) (5 1) (5 12) (5 17) (12 26) (12 28) (12 54))) daha da kt bir sonu! assoc bildigimiz assoc ise, bu kod alisamaz. Kod calisiyor. Tabii ben, elimde kitap olmadan giristigim icin ne tr input bekledigini anlayamamisim basta. BM'nin tavsiyeleri dogrultusunda kurcalayinca input'un nasil olmasi gerektigi anlasildi. Tekrar kodu gecmek gerekirse: == (defun shortest-path (start end net) (bfs end (list (list start)) net)) (defun bfs (end queue net) (if (null queue) nil (let ((path (car queue))) (let ((node (car path))) (if (eql node end) (reverse path) (bfs end (append (cdr queue) (new-paths path node net)) net)) (defun new-paths (path node net) (mapcar #'(lambda (n) (cons n path)) (cdr (assoc node net === bfs, anladigimiz kadari ile Breadth First Search manasinda. Ve her elemanin komsularini yazip yle arayacak olursak: === (time (shortest-path '1 '54 '( (1 5) (5 1 12 17) (12 5 26 28 54) (17 5) (26 12) (28 12) (54 12 Evaluation took: 0.0 seconds of real time 0.0 seconds of user run time 0.0 seconds of system run time 0 page faults and 8,192 bytes consed. (1 5 12 54) Dogru sonucu yani 1 - 5 - 12 - 54 sonucunu buluyor. Windows'ta CLISP'te ve GNU/Linux'ta SBCL ile denedim. kodu Scheme'e evirdim, ayni buglar mevcut. (buglu Scheme ektedir) Kodu alisir haline getirdim ancak hala performans aisindan byk listeler iin berbat olmasi lazim. Performansini da zmek de zor degil. Yukaridaki Common Lisp kodu grdgm kadari ile dzgn calisiyor (biraz daha bytp karmasiklastirdim inputu gene dzgn sonuc verdi) === CL-USER (time (shortest-path '1 '19 '((1 5) (5 1 12 17) (12 5 26 28 54) (17 5) (26 12) (28 12) (54 12 47) (47 15) (15 2) (2 15 100 101) (3 100) (100 2 15 19 Evaluation took: 0.417 seconds of real time 0.054991 seconds of user run time 0.014998 seconds of system run time 46 page faults and 1,211,352 bytes consed. (1 5 12 54 47 15 2 100 19) CL-USER (time (shortest-path '1 '19 '((1 5) (5 1 12 17) (12 5 26 28 54) (17 5) (26 12) (28 12) (54 12 47) (47 15) (15 2) (2 15 100 101) (3 100) (100 2 15 19 Evaluation took: 0.005 seconds of real time 0.005999 seconds of user run time 0.0 seconds of system run time 0 page faults and 1,224,704 bytes consed. (1 5 12 54 47 15 2 100 19) CL-USER (time (shortest-path '1 '19 '((1 5) (5 1 12 17) (12 5 26 28 54) (17 5) (26 12) (28 12) (54 12 47) (47 15) (15 2) (2 15 100 101) (3 100) (100 19 Evaluation took: 0.005 seconds of real time 0.004999 seconds of user run time 0.0 seconds of system run time 0 page faults and 1,204,224 bytes consed. (1 5 12 54 47 15 2 100 19) Hafiza acisindan problemli oldugu asikar, diger yandan "cache"lemenin getirdigi tekrar hesaplamalardaki hiz farki da grlebiliyor. Tail-recursive hale getirilirse herhalde hafiza problemi halledilebilir, hiz konusunda ise su anda bir fikrim yok. Bu sorun zm besbelli basit bir Bilgisayar Bilimleri sorunu. Algoritmik olarak karisik degil ancak basit olmayan kisimlarini asagida yazacagim. So a programming challenge for any student in any year. Solve either part of Emre's problem (a) find and correct the bugs in Paul Graham's code. Emre has demonstrated one, my example above demonstrates another. (b) produce
