Breadth-First Search

Gordugumuz bir Tree. 1 Root node, kendisi 2, 3 ve 4 u uretmis, ayni sekilde 2, 5 ve 6 yi vs..
Ornek problem vermek gerekirse, agentimiz Node 1 deki state'den Node 10'a varmaya calisiyor.

Searching algorithmlerden soz ederken, 2 cesit liste turunden bahsederiz. Cozumun adim adim saklandigi bir liste, Cozum yada Solution Listesi, ve bir onceki Node'un childlarini iceren Frontier Listesi.

Ilk olarak arama su sekilde gerceklesir. Current Node, Solution listesine eklenir. Current Node'un childlari Frontier listesine eklenir. Bu andan itibaren, Frontier listesinin ilk elemani secilir, Childlari Frontier listesine eklenir, kendisi Frontier listesinden silinip, Solution listesine eklenir. Secilen frontier elemani, aradigimiz Node yada State (Durum) olana kadar devam eder yani frontier listesinin ilk elemani dequeue edilir, onun cocuk nodelari frontier'e eklenir ve dequeue edilen node solution'a eklenir.



Bahsettigimiz iki liste, Frontier ve Solution listesinin veri tipleri onemlidir. Breadth First'de Frontier bir FIFO listesi yani Queue dir. Kodlanan programlama diline gore Solution'a herhangi bir hizli veri turu atayabilirsiniz. HashSet gibi. Fakat Solution da Queue olabilir, bir sakincasi bulunmamaktadir.

Queue veya FIFO hakkinda bilgi vermek gerekirse:

FIFO, first in first out anlamina gelmektedir. Ilk giren son cikar, turkce karsiligiyla.

Queue'ye bir veri girisi yaparken, Enqueue yapmis olursunuz. Queue'nin en eski elemanini Queue'den koparip bir degiskene atamak icin Dequeue fonksiyonunu kullanabilirsiniz.

Asagidaki ornekte Queue'ye A node'u ve ardindan B node'u sokuluyor. A Queue'nin en eski elemani oldugundan, cagirilan bir Dequeue fonksiyonu sonucunda, Queue'den ilk olarak silinecek Node ta kendisi.
























Konuya geri donecek olursak Breadth First complete bir arama algoritmasidir. Tum olasiliklari dener ve bir cozum varsa, kesinlikle bunu bulur. Fakat her node'u teker teker denediginden perfonmans konusunda zayiftir (yinede baska birkac arama algoritmasindan daha hizli)

Frontier'e child nodelari eklerken, her zaman soldan saga bir yol izler. Ve bir leveldaki tum nodelari denemeden (yada frontier'e eklemeden) daha derin bir level'e inmez.

Yukaridaki verileri goz onune aldigimizda, 1 den 10 a varmak istersek, Breadth-First search asagidaki asamalardan gecerek bizi sonuca ulastirir.



Current Node: 1
Solution List: Bos
Frontier Queue: Bos

Current Node: 1
Solution List:
Frontier Queue: 2 3 4

Current Node: 2
Solution List: 1
Frontier Queue: 3 4

Current Node: 2
Solution List: 1 2
Frontier Queue: 3 4 5 6

Current Node: 3
Solution List: 1 2
Frontier Queue: 4 5 6

Current Node: 3
Solution List: 1 2 3
Frontier Queue: 4 5 6

* (3 child'a sahip degil)

Current Node: 4
Solution List: 1 2 3
Frontier Queue: 5 6

Current Node: 4
Solution List: 1 2 3 4
Frontier Queue: 5 6 7 8

Current Node: 5
Solution List: 1 2 3 4
Frontier Queue: 6 7 8

Current Node: 5
Solution List: 1 2 3 4 5
Frontier Queue: 6 7 8 9 10

Current Node: 6
Solution List: 1 2 3 4 5
Frontier Queue: 7 8 9 10

Current Node: 6
Solution List: 1 2 3 4 5 6
Frontier Queue: 7 8 9 10

Current Node: 7
Solution List: 1 2 3 4 5 6
Frontier Queue: 8 9 10

Current Node: 7
Solution List: 1 2 3 4 5 6 7
Frontier Queue: 8 9 10 11 12

Current Node: 8
Solution List: 1 2 3 4 5 6 7
Frontier Queue: 9 10 11 12

Current Node: 8
Solution List: 1 2 3 4 5 6 7 8
Frontier Queue: 9 10 11 12

Current Node: 9
Solution List: 1 2 3 4 5 6 7 8
Frontier Queue: 10 11 12

Current Node: 9
Solution List: 1 2 3 4 5 6 7 8 9
Frontier Queue: 10 11 12

//cozum bulundu

Current Node: 10
Solution List: 1 2 3 4 5 6 7 8 10
Frontier Queue: temizlendi.


Gordugumuz gibi son durumda Current Node, 10. Aradigimiz node 10 oldugundan algoritma bize solutionu dondurecek.

Solution List 1 2 3 4 5 6 7 8 10 u iceriyor. Her child node'un parent node'unun idsini barindirdigini varsayarsak (ki bir dizi halinde sonucu gostermek icin bu destegi saglamaliyiz), 10 dan baslayarak geriye donmeliyiz.

Yazacigimiz ufak bir fonksiyon su sart ifadeleri icerisinde cozumu dondurmeli.

v_id = 10'un idsi.
Dongu
Eger v_id null ise
Donguden cik
v_node = solution icerisinde id'si v_id degiskenine esit olan node
v_id = v_node'un id si
Dongu Bitis

Breadth First Search, bir cozum varsa onu mutlaka dondurur, Queue kullanir, ve Tree'yi level, level tarar, ve bir level icerisindeki nodelar aranilan durumu icermiyorsa, tree'nin bir level asagisina inerek en soldaki node'u kontrol eder. Eger sonuc o degilse, node'un cocuklarini frontier'e ekler.