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