Best First Search

TUGAS KELOMPOK 1

Algoritma Pencarian Terbaik Pertama (Best First Search)

Di susun untuk memenuhi tugas kecerdasan buatan

Dosen Pembimbing :

ABDUL AZIZ,  M.Kom

Disusun oleh:

Abdul Mujib                        2010.69.04.0049

Solehhudin               2010.69.04.00

M.Rojil Ghufron      2010.69.04.0047

Hisam abu Rizal       2010.69.04.00

Fatkhul ilmiah          2010.69.04.0051

Yindawati                 2010.69.04.0052

Hersarimunah          2010.69.04.00

FAKULTAS TEKNIK

JURUSAN TEKNIK INFORMATIKA

UNIVERSITAS YUDHARTA PASURUAN

2013

Algoritma Pencarian Terbaik Pertama (Best First Search)

Algoritma best first search ini merupakan kombinasi dari algoritma depth first search  dengan algoritma breadth first search  dengan mengambil kelebihan dari kedua  algoritma tersebut. Apabila pada pencarian dengan algoritma  hill climbing tidak  diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node di  level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristik yang lebih buruk (Kusumadewi, 2003).

Algoritma best first search merupakan salah satu bagian dari tipe informed search. Algoritma ini menggunakan nilai-nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai heuristik terbaik akan dibuka lebih dahulu. Bila goal state belum ditemukan, akan dilakukan pemeriksaan pada simpul berikutnya dengan nilai heuristik terbaik pada kedalaman yang sama. Simpul tersebut kemudian dibuka dan diperiksa apakah terdapat goal state pada cabang-cabangnya. Bila goal state belum ditemukan,  akan dilakukan proses yang sama pada simpul berikutnya.

Beberapa macam dari Algoritma Best First Search menurut pakar Artificial intelegency :

A. Menurut Thomas Dean, et all, AI teori & practice, page 145 sebagai berikut :

1. Himpunan N menjadi sebuah list berurutan dari node awal (initial nodes)
2. Jika N adalah kosong, maka keluar dan berikan pesan gagal/failure
3. Himpunan N menjadi node pertama dalam N, dan hapus n dari N
4. Jika N adalah node tujuan/goal maka keluar dan berikan pesan sukses
5. Selain itu, tambahkan anak dari n ke N, urutkan node-node dalam N menurut jarak estimasi dari sebuah goal, dan kembali ke langkah 2.

B.  Menurut Elaine Rich & Kevin Knight, “Artificial Intelligence”,  page73, sebagai berikut :

1. Mulai dengan OPEN yang hanya berisi keadaan awal
2. Ulangi langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong

3.      Ambil node terbaik dari OPEN

4. Bangkitkan semua successor-nya
5. Untuk tiap-tiap successor, kerjakan:

a.        jika node tersebut belum pernah dibangkitkan sebelumnya,

  evaluasi node tersebut dan masukkan ke OPEN;

b.      jika node tersebut sudah pernah dibangkitkan sebelumnya,

      ubah parent jika lintasan baru lebih baik daripada sebelumnya.

C. Menurut George F. Luger, & William A.Stubblefield, “Atificial Intelegence:Structured & Strategies for Complex Problem Solving”, sebagai berikut :

1. open=[A5]; closed=[]
2. evaluate  A5; open=[B4,C4,D6]; closed=[A5]
3. evaluate B4; open=[C4,E5,F5,D6]; closed=[B4,A5]
4. evaluate C4; open=[H3,G4,E5,F5,D6]; closed=[C4,B4,A5]
5. evaluate H5; open=[O2,P3,G4,E5,F5,D6]; closed=[H3,C4,B4,A5]
6. evaluate O5; open=[P3,G4,E5,F5,D6]; closed=[O2,H3,C4,B4,A5]
7. evaluate P3; solusi ditemukan.

Gambar diatas merupakan contoh penggunaan algoritma best first search dimana P adalah node tujuannya (goal). Oleh karenaP merupakan tujuan maka keadaan sepanjang lintasan ke P menuju nilai heuristic yang rendah. Heuristic boleh jadi keliru; O mempunyai nilai terendah daripada tujuannya dan diperiksa pertama.

Fungsi heuristic dalam Algoritma ini

Dalam algoritma ini diperlukan fungsi heuristik yang akan mengestimasi seberapa baik dibangkitkannya setiap node. Fungsi heuristik yang digunakan dalam algoritma ini hanya memperhitungkan biaya(cost)  untuk mencapai tujuan dan mengabaikan cost  jalan yang sudah ditempuhnya untuk sampai ke  current state, sehingga sering disebut sebagai greedy best first search yang dinyatakan dengan :

f(n) = h(n)

dimana :

f(n) = fungsi heuristik

h(n) = biaya perkiraan(estimated cost) dari jalur terpendek dari current state  ke goal state (Arwin, 2006).

Masalah utama pada algoritma ini adalah cara kerjanya yang terus mencoba bergerak ke arah goal, meskipun jalan yang dilalauinya buka n jalan yang benar. Karena algoritma ini hanya memperhitungkan cost untuk mencapai goal dan mengabaikan cost jalan yang sudah ditempuhnya untuk sampai ke current state, maka algoritma tersebut terus maju meskipun jalan yang telah dilaluinya sudah terlalu panjang.

Ada dua jenis pencarian best first, yaitu:

a.      Graf or

Untuk jenis yang pertama ini, pengimplementasian dengan menggunakan graf keadaan, dibutuhkan dua antrian yang berisi node-node yaitu:

1. OPEN, berisi node-node yang telah dihasilkan dan ada fungsi heuristic yang diterapkan padanya, namun belum diperiksa. Daftar ini sebenarnya berupa antrian berprioritas dengan elemen-elemen yang mempunyai prioritas tertinggi sebagai nilai fungsi heuristic yang paling dapat diharapkan.
2. CLOSED berisi node-node yang telah diuji. 

b.Algoritma A*

Algoritma A merupakan algoritma best first search dengan pemodifikasian fungsi heuristik, yang akan meminimumkan total biaya lintasan, dan pada kondisi yang tepat  akan memberikan solusi yang terbaik dalam waktu yang optimal.

Algoritma A juga membutuhkan dua antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang memprediksi keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma untuk melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih baik jika fungsi di definisikan sebagai kombinasi atau jumlah dua komponen yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari keadaan awal sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya penerapan setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju suatu simpul dan bukan merupakan hasil estimasi.

Fungsi h(n) merupakan pengukur biaya tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya lintasan.

Secara matematis,fungsi F sebagai estimasi fungsi evaluasi terhadap node ndapat di tuliskan :

        f’(n) = g(n) + h’(n)

Dengan

    f’(n) = fungsi evaluasi

    g(n) = biaya yang sudah di keluarkan dari keadaan awal sampai

                keadaan n

    h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n

Ø  dari fungsi di atas maka ada beberapa kondisi yang perlu di perhatikan, yaitu :

Ø  Jika h = h’, berarti proses pencarian telah sampai ke tujuan ( goal ).

Ø  Jika g = h’ = 0 maka f’ random, artinya system tidak dapat di kendalikan oleh apa pun.

Ø  Jika g = k, k adalah konstanta dan biasanya bernilai 1, h’ = 0, artinya system menggunakan breadth first search.

Contoh:

Berikut ini adalah peta Romania dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.

Adapun jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus adalah sebagai berikut :

Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77

Hirsova 15 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 98

Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 Rimnicu Vilcea 193 Sibiu 253

Permasalahannya adalah untuk mencari jalan terdekat dari kota Arad menuju kota Bucharest dengan menggunakan metoda Best First Search.

Heuristik yang digunakan adalah jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus yang jaraknya seperti yang tertera di atas dengan asumsi kota terhubung yang letaknya paling dekat dengan kota Bucharest adalah jalan yang paling optimal.

Diagram pohon langkah-langkah penelusuran dengan metode Best First Search adalah sebagai berikut :

Langkah 1                                                         Langkah 2

Langkah 3

Langkah 4

Kesimpulan :

Dari Langkah-langkah di atas, dengan metode Best First Search didapatkan kota-kota yang harus dilalui untuk mendapatkan jalan yang paling dekat jaraknya dari Arad ke Bucharest adalah : Arad – Sibiu – Fagaras – Bucharest. Dari peta di atas, panjang jalan yang dilalui adalah 140+99+211 = 450 km.

Dokumentasi