Jika sebelumnya Anda belum membaca tutorial sejenis tentang teknik pencarian depth first search , maka saya sarankan agar membaca terlebih dahulu tutorial tersebut. Karena sebenarnya 2 tutorial ini saling berhubungan dan identik. Meskipun pada tutorial ini membahas teknik pencarian breadth first search yang berbeda dengan tutorial sebelumnya, tapi ini merupakan rangkaian pembahasan yang tak terpisahkan. Jika Anda sudah membaca dan memahaminya, silakan Anda teruskan dengan tutorial ini.

Sebenarnya hampir sama antara depth first search dan breadth first search. Terdapat konsep dasar yang sama antara kedua metode pencarian tersebut. Perbedaannya hanya terletak pada proses penambahan hasil eksplorasi dari sebuah node. Jika pada teknik depth first search penambahan node-node tetangga hasil eksplorasi berada pada awal open list, akan tetapi pada teknik breadth first search, node-node hasil eksplorasi tersebut ditambahkan pada akhir open list. Sedangkan pada keduanya, prioritas proses sama-sama terletak pada item atau node paling depan (awal)open list.

Untuk kasus yang sama dengan yang diberikan pada penjelasan depth first search, kita gunakan acuan grafik pencarian di bawah ini:

Untitled3_3


Akan kita coba menemukan jalur antara node awal A menuju node akhir F.


Step 0

Kita mulai dari node asal yaitu node A:

Untitled4_3

Seperti pembahasan sebelumnya, akan digunakan dua container untuk menyimpan track dari apa yang akan dilakukan dan sudah dilakukan. Open list untuk track yang masih ingin dan akan dilakukan sedangkan closed list untuk menyimpan track proses yang sudah dijalankan. Pada posisi awal closed list masih belum berisi.

· Open List: A

· Closed List: <kosong >


Step 1

Sekarang waktunya untuk mengurai atau mengeksplorasi node tetangga dari node A. Akan kita dapatkan bahwa B dan C merupakan tetangga dari node A.

Untitled5_4

Kita pindah A dari open list dan kita tempatkan ke dalam closed list. Dan kita masukkan node tetanga dari A, yaitu B dan C ke dalam open list, yang akan dilakukan proses padnya setelah ini.

Data terakhir setelah step ini pada open list dan closed list adalah sebagai berikut::

· Open List: B, C

· Closed List: A


Step 2

Pada tahap ini mulai kelihatan perbedaan antara matode depth first search yang telah kita bahas sebelumnya. Kita akan meninjau lebih jauh terhadap node B, karena dia berada di awal pada open list. Kita urai dan akan kita dapatkan D dan E sebagai node tetangga dari B. Kemudian B kita pindahkan dari open list menuju ke closed list. Jika pada depth first search hasil eksplorasi tersebut (D dan E) di awal open list tapi pada teknik breadth first ini diletakkan pada akhir open list. Sehingga akan kita dapatkan data pada open list berisi C,D dan E, sedangkan pada closed list berisi A dan B.

Untitled6_3

· Open List: C, D, E

· Closed List: A, B


Step 3

Kemudian kita lakukan proses ekspansi dari node C yang berada di awal open list.

Untitled9

Karena C tidak memiliki node tetangga, maka kita cukup melakukan pemindahan C yang semula dari open list menuju ke closed list:

· Open List: D, E

· Closed List: A, B, C


Step 4

Sama dengan yang dilakukan pada step 3, kita mengekspansi node D dan kemudian memindahkannya ke closed list. Karena node D tidak memiliki tetangga, maka tidak ada penambahan pada open list.

· Open List: E

· Closed List: A, B, C, D


Step 5

Langkah selanjutnya adalah mengurai E dan akan kita dapatkan node F dan G sebagai node-node tetangga dari E. Kita pindahkan E menuju ke closed list diiringi dengan menambahkan F dan G ke dalam open list.

Untitled10

Our final versions of the Open and Closed Lists contain the following data:

· Open List: F,G

· Closed List: A, B, C, D, E


Step 6

Langkah selanjutnya adalah mengurai F. Karena F merupakan tujuan, sehingga proses pencarian bisa dihentikan sampai sini. Tersisa hanya G di open list dan A,B,C,D,E,F pada closed list.

· Open List: G

· Closed List: A, B, C, D, E,F


Dari berbagai tahap di atas akhirnya didapatkan solusi jalur dari A menuju ke F dengan menggunakan breadth first search.