Pada kesempatan kali ini saya akan membahas tentang
problem 8-puzzle menggunakan metode BFS (Breadth
First Search). Sebelum ke topik utama, saya ingin membahas secara singkat
apa itu BFS. Breadth-first search adalah algoritma yang melakukan
pencarian secara melebar yang mengunjungi simpul secara pre-order yaitu
mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga
dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum
dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi , demikian
seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d
dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1.
Bagaimana? setelah kalian mengenal apa itu BFS,
sekarang kita akan ke topik utama. Cekidottt….
- Pertama-tama saya akan membahas 4 problem pada 8-puzzle :
1. Initial State (status awal masalah)
1
|
0
|
3
|
4
|
2
|
6
|
7
|
5
|
8
|
2. Operator Succesor
Ruang kosong yang bergerak ke arah kiri,
atas, kanan, bawah.
3. Path Cost
Ruang kosong yang bergerak ke arah kiri,
atas, kanan, bawah.
Kemungkinan yang terjadi :
1. Langkah 0 (situasi awal) 103426758
1. Langkah 0 (situasi awal) 103426758
2.
Langkah
1 013426758
(0 ke kiri)
3. Langkah
2 123406758 (0 ke bawah) dipilih ke-1
4. Langkah
3 130426758 (0 ke kanan)
5. Langkah
1.1 413026758 (0 ke bawah)
6. Langkah
2.1 123046758 (0 ke kiri)
7. Langkah
2.2 123456708 (0 ke bawah) dipilih ke-2
8. Langkah
2.3 123460758 (0 ke kanan)
9. Langkah 3.1 136420758 (0 ke bawah)
9. Langkah 3.1 136420758 (0 ke bawah)
10. Langkah 1.1.1
413206758 (0 ke kanan)
11. Langkah 1.1.2 413726058 (0 ke bawah)
12. Langkah 2.1.1 023146758 (0 ke atas)
13. Langkah 2.1.2 123746058 (0 ke bawah)
14. Langkah 2.2.1 123456078 (0 ke kiri)
15. Langkah 2.2.2 123456780 (0 ke kanan) dipilih ke-3
16. Langkah 2.3.1 120463758 (0 ke atas)
17. Langkah 2.3.2 123468750 (0 ke bawah)
18. Langkah 3.1.1 136402758 (0 ke kiri)
19. Langkah 3.1.2
136428750 (0 ke bawah)
1. 103426758
2. 123406758 (0 ke bawah)
3. 123456708 (0 ke bawah)
4. 123456780 (0 ke kanan)
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
0
|
- Selanjutnya kita akan menelusuri pohon pencarian dengan BFS
- Selanjutnya kita masuk ke tahap sekuen aksi BFS dari pohon diatas
Untuk lebih jelasnya kalian bisa menyimak video berikut :
Sumber referensi :
- http://andiktaufiq.wordpress.com/2010/04/16/8-puzzle-problem-bagian-1/
- http://artificialintelligence-notes.blogspot.co.id/2010/07/8-puzzle-problem.html
- http://onbuble.wordpress.com/2011/05/26/6/
- http://mypuzzle.org/sliding