4/7/2016
3. HEURISTIC METHOD 07/04/2016
Best First Search Algoritma yang menggunakan Metode
Best-First Search, yaitu: KECERDASAN BUATAN
Pertemuan-07 INFORMATIKA FASILKOM UNIVERSITAS IGM
a. Greedy Best-First Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h’(n).
b. A* A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan f(n)= g(n) + h’(n).
1
Literatur Review
Best First Search
Best First Search
Best First Search :
Ada beberapa istilah yang sering digunakan, yaitu:
• Kombinasi dari metode depth first search dan breadth first • Pencarian diperbolehkan mengunjungi node lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk. • Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n) • Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : – f’(n) = g(n) + h’(n) – f’ = Fungsi evaluasi – g = cost dari initial state ke current state – h’ = prakiraan cost dari current state ke goal state
• Start node adalah sebuah terminology untuk posisi awal sebuah pencarian • Current node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek • Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node • Simpul (node) merupakan representasi dari area pencarian
1
4/7/2016
Best First Search Ada beberapa istilah yang sering digunakan, yaitu: • Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan • Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan • Goal node yaitu simpul tujuan • Parent adalah current node dari suksesor.
Best First Search
Best First Search
Algoritma Best-First Search : 1. OPEN berisi initial state dan CLOSED masih kosong. 2. Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN. a. Ambil simpul terbaik yang ada di OPEN. b. Jika simpul tersebut sama dengan goal, maka sukses c. Jika tidak, masukkan simpul tersebut ke dalam CLOSED d. Bangkitkan semua aksesor dari simpul tersebut e. Untuk setiap suksesor kerjakan: i. Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent. ii. Jika suksesor tersebut sudah pernah dibangkitkan, ubah parentnya, jika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya.
Best First Search
OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSED untuk mengelola nodenode yang pernah dibangkitkan dan sudah dievaluasi.
2
4/7/2016
Best First Search
Best First Search Algoritma yang menggunakan metode best-first search, yaitu:
Best First Search
Contoh : A* Misalkan kita memiliki ruang pencarian seperti gambar berikut : Keadaan Awal : Node M
Node T (Tujuan)
a.
Greedy Best-First Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h’(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal. b. A* A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h’(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.
3
4/7/2016
Algoritma A*
Fungsi Evaluasi : f’(n)= h’(n)
FUNGSI EVALUASI F’(N) = G(N) + H’(N) Keadaan Awal : Node M
Node T (Tujuan)
4
Biaya edge M-A : Biaya yang dikeluarkan bergerak dari kota : M ke A Biaya g ---- g(n) : Nilai g diperoleh berdasarkan biaya edge minimal Nilai h’ di Node A ----- h’(n) : Hasil perkiraan terhadap biaya yang diperlukan dari Node A untuk sampai ke Tujuan (Node T) Nilai h’ : h’(n) bernilai ~ jika antara node n ke Tujuan buntu
Fungsi Evaluasi : f’(n)= h’(n)
Fungsi Evaluasi : f’(n)= h’(n)
Node diekspansi M C H T
Antrian OPEN {M(0)} {C(2), A(3), B(4)} {H(2), A(3), B(4), I(~)} {T(0), A(3), B(4), I(~), L(~)} {A(3), B(4), I(~), L(~)}
4
4/7/2016
Fungsi Evaluasi : f’(n)= h’(n)
Algoritma A*
f’(n)=g(n)+h’(n)
Alur Penelusuran dengan f’(n) = h’(n) Node diekspansi M C H T
Antrian OPEN {M(0)} {C(2), A(3), B(4)} {H(2), A(3), B(4), I(~)} {T(0), A(3), B(4), I(~), L(~)} {A(3), B(4), I(~), L(~)}
Alur Penelusuran dengan f’(n) = h’(n), solusi yang Diperoleh adalah lintasan terpendek : M-C-H-T Dengan biaya sebesar 7.
Algoritma A*
Graf Keadaan Algoritma A*
Alur Penelusuran dengan f’(n) = g(n)+h’(n) Node diekspansi M C H T
Antrian OPEN {M(0)} {C(6), B(7), A(8)} {H(7), B(7), A(8), I(~)} {T(7), B(7), A(8), I(~), L(~)} {B(7), C(8), I(~), L(~)}
Alur Penelusuran dengan f’(n) = g(n)+h’(n), solusi yang diperoleh adalah lintasan terpendek : M-C-H-T , dengan biaya sebesar 7. Lihat alur penelusuran diatas !
Terlihat dengan menggunakan Algoritma A*, yakni f’(n) = g(n)+h’(n), maka solusi yang didapat adalah lintasan terpendek : M-C-H-T sebesar 7.
5
4/7/2016
Algoritma A*
Algoritma A*
HASIL ANALISIS Coba Anda lakukan analisis , jika ada node dengan nilai heuristik terbaik yang sama, pilih node lain untuk diekspansi !
Node diekspansi ? ? ? ?
Bagaimana Alur Lintasannya dan berapa Besar biayanya ?
Antrian OPEN . . . . .
. . . . .
. . . . .
Alur Penelusuran dengan f’(n) = h’(n), solusi yang Diperoleh adalah lintasan terpendek : . . . . . . . . . ? dengan biaya sebesar …. ?
Contoh lain : A*
07/04/2016
23
07/04/2016
Keceerdasan Buatan-2015
24
6
4/7/2016
Contoh lain : A*
07/04/2016
Keceerdasan Buatan-2015
Contoh lain : A*
25
07/04/2016
Contoh lain : A*
07/04/2016
Keceerdasan Buatan-2015
Keceerdasan Buatan-2015
26
Contoh lain : A*
27
07/04/2016
Keceerdasan Buatan-2015
28
7
4/7/2016
Manfaat - LR 07/04/2016
هللا خ ر ًَْيا َك ِث ر ًْيا َج َز ماُكم م السالم عليكم ورحمة هللا وبركاته
Literatur Review
8
29
