Metode Best-First Search Pada Pencarian dengan Hill Climbing

Slide1Nama Kelompok  : 1. Marie Karunia Sari .S.   (0834010126) 2. Erna Tri Wahyu .N. (0834010214) 3. Gita Ayuningtyas (0834010 020 )

Slide2Metode best  first  search  ini  merupakan  kombinasi  dari beberapa  kelebihan  teknik  depth  first  search  dan  breadth first  search.  Pada  pencarian  dengan  hill  climbing  tidak diperkenankan  untuk  kembali  ke  node  pada  level  yang lebih  rendah  meskipun  node  pada  level  yang  lebih  rendah tersebut  memiliki  nilai  heuristik  yang  lebih  baik.  Hal  ini berbeda  dengan  metode  best  first  search  dimana  pencarian diperkenankan  mengunjungi  node  yang  ada  di  level  yang lebih  rendah  jika  ternyata  node  pada  level  yang  lebih  tiggi ternyata  memiliki  heuristic  yang  buruk.

Slide3Beberapa  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.  

Slide4B.  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 a. Ambil  node  terbaik  dari  OPEN b. Bangkitkan  semua  successor-nya c. Untuk  tiap-tiap  successor,  kerjakan:                   i.  jika  node  tersebut  belum  pernah  dibangkitkan  sebelumnya,                      evaluasi  node  tersebut  dan  masukkan  ke  OPEN;                   j.  jika  node  tersebut  sudah  pernah  dibangkitkan  sebelumnya,                      ubah  parent  jika  lintasan  baru  lebih  baik  daripada sebelumnya.

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

Slide6a.open=[A5];  closed=[] b. evaluate   A5;  open=[B4,C4,D6];  closed=[A5] c. evaluate  B4;  open=[C4,E5,F5,D6];  closed=[B4,A5] d. evaluate  C4;  open=[H3,G4,E5,F5,D6];  closed=[C4,B4,A5] e. evaluate  H5;  open=[O2,P3,G4,E5,F5,D6]; closed=[H3,C4,B4,A5] f. evaluate  O5;  open=[P3,G4,E5,F5,D6]; closed=[O2,H3,C4,B4,A5] g. evaluate  P3;  solusi  ditemukan.

Slide7Gambar 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. 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. 

Slide8B.Algoitma  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.

Slide9Fungsi 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

Slide10dari 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.

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

Slide12adapun jarak kota-kota terhadap kota bucharest jika ditarik garislurus adalah sebagai berikut : Permasalahannya adalah untuk mencari jalan terdekat dari kota Arad menuju kota Bucharest dengan menggunakan metoda Best First Search 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

Slide13heuristik yang digunakan adalah jarak kota-kota terhadap kotaBucharest 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  

Slide14Langkah 3Langkah 4

Slide15dari langkah-langkah di atas, dengan metode best first Searchdidapatkan 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.

Slide16TERIMA KASIH