2 Ocak 2011 Pazar

Depth-First Search

Daha onceki entry'de, Tree'nin bir level'i icerisindeki tum nodelar uzerinde arama yapmadan, bir sonraki level'a gecmeyen ve complete bir arama yontemi olan Breadth-First searchden soz etmistim.

Depth-First Search ise yine Breadth-First gibi bir arama algoritmasidir. Ondan farki ise complete olmamasidir ve tek bir branch uzerinde, cozumu buluncaya (yada bulamayacagina kanaat getirene) kadar aramaya, node'un successorleri yaratmaya devam eder.

Depth-First Search'in Breadth-First'den diger farki ise Queue yerine Stack kullanmasidir. Stack bir LIFO listesidir. LIFO, Last in first out anlamina gelmektedir. Yani Stack'a push komutuyla birkac veri eklediginizde, pop komutu kullanarak stack'dan bir oge almak isterseniz, listeden alacaginiz veri, en son eklediginiz veridir. Queue'nin tam tersi yani.





Yukaridaki tree ornegine bakicak olursak, Breadth-First kullansaydik, root node olan 4 den 1 e ulasmak icin izleyecegimiz yolu belirlerken, Solution listemizde bulunan nodelar sirasiyla 4,2,6,1 olucakti. Depth-First kullanirsak solution listemiz ise 4, 2, 1'i icerir.

Depth-First Search, tree'nin guncel dalinin en sonundaki node, deaf node olana kadar, baska bir branch'a gecmez, ayni sekilde derin levellara dogru devam eder.

Yukaridaki treede Depth-First kullanmamiz isimize yaradi, Breadth-First'ten daha verimli bir sekilde cozumu bulabildi. Fakat tamamen sans eseri; eger en soldaki branchda deaf node olmasaydi ve biz 7 yi arasaydik, en soldaki branch icerisinde sonsuza kadar derinlere inerdi (deaf node olmasaydi derken sonsuz level oldugunu farzediyorum) ve cozumu bulamazdi. Dolayisiyla complete degil, ama bazi durumlarda Breadth-First'den daha iyi perfonmans saglayabilir.

Yukaridaki Tree ornegine bakacak olursak, yani 4 node'undan 1 node'una ulasmak istersek, Stack ve Solution listesi adim adim su verilere sahip olacak.

Current Node: 4
Frontier Stack: Empty
Solution List: Empty

Current Node: 4
Frontier Stack: 2 6
Solution List: 4

Current Node: 2
Frontier Stack: 6
Solution List: 4

Current Node: 2
Frontier Stack: 1 3 6
Solution List: 4 2

Current Node: 1
Frontier Stack: 3 6
Solution List: 4 2

Current Node: 1
Frontier Stack: 3 6
Solution List: 4 2 1 //Cozum bulundu

Yazarak adim adim anlatmak gerekirse,
  • Current Node 4
  • 4 un child nodelari 2 ve 6 frontier'e eklenir ve 4 solution list'e eklenir
  • frontierdeki ilk child olan 2 nin child nodelari frontiere eklenir; 1 ve 3. Ve 2 solution a eklenir.
  • frontierin su anki durumu 1 3 ve 6 iken solutionda 4, 2 bulunur.
  • frontierdan pop komutuyla yine bir child alinir, 1 current node olur.
  • current node aranilan node oldugundan solution'a eklenir.
  • solution da 4, 2, 1 bulunurkan frontier ve current node temizlenir.

Hiç yorum yok:

Yorum Gönder