Oct 13

Nama               : Fitri Handayani Ritonga

NIM                : 1000050

Tugas Individu 1 AI (Artificial Intelligent) / Kecerdasan Buatan

 Algoritma A* / A Star / A Bintang

Algoritma A* adalah algoritma yang dikemukakan oleh Hart, Nilsson, dan Raphael pada tahun 1968. Algoritma A* merupakan salah satu algoritma Branch and Bound atau disebut juga sebagai sebuah algoritma untuk melakukan pencarian solusi dengan menggunakan informasi tambahan (heuristic) dalam menghasilkan solusi yang optimal.

Ada beberapa variasi A* seperti berikut :

–          Iterative Depeening A*  (IDA*)

–          Simplified Memory-Bounded A*  (SMA*)

–          Bi-Directional A*  (BDA*)

–          Modified Bi-Directional A*  (MBDA*)

–          Dynamic Weighting A* (DWA*)

–          Beam A* (BA*)

 

PENJELASAN BEBERAPA VARIASI ALGORITMA A*

  • Iterative Deepening A* (IDA*)

Iterative Deepening A* atau yang sering disebut dengan IDA* merupakan gabungan dari algoritma BFS dan DFS, dimana algoritma BFS merupakan algoritma complete dan optimal dan algoritma DFS merupakan algoritma yang space complexity rendah.

IDA* menggunakan pencarian iterative dimana nilai batasan/limit pencarian didasarkan pada nilai f(n). Dimulai dari status awal, tentukan suatu limit awal. Bangkitkan semua node dari status awal tersebut lalu hitung f(n) untuk setiap anak yang terkecil. Apakah f(n) terkecil lebih kecil dari limit ? Jawabannya bias Ya bias Tidak. Jika jawaban Iya maka bangkitkan semua anak dari node dengan f(n) terkecil tersebut, lalu lanjutkan pencarian. Jika jawabannya tidak maka jadikan f(n) tersebut sebagai limit baru kemudian ulang pencarian dari status awal (restart).

IDA* merupakan algoritma yang time complexity nya tinggi dikarenakan proses pencarian dilakukan secara iterative sehingga terjadi proses penelusuran menggunakan algoritma DFS yang berulang-ulang tetapi walaupun boros waktu IDA* tetap memberikan solusi terbaik.

Algoritma IDA*

Function depth_first_search(n, limit)

If f(n) > limit

Then Return f(n)

If h(n) = 0 Then BERHASIL

Return nilai terendah dari depth_first_search (ni;, limit) bagi semua successor n; dari n

end

Procedure IDA* (n)

Limit = h(n)

repeat

limit = depth_first_search (n, limit)

until BERHASIL

end

Jalur Terpendek S ke G dengan IDA*

1

  • Mulai dari status awal, tentukan limit misalnya 80.
  • Bangkitkan semua anak dari S, hitung f(n), mana f(n) terkecil ? Node E, f(e) = 84
  • Karena f(n) terkecil > limit, limit = f(n) = 84. Restart.
  • Bangkitkan semua anak dari status awal. Cari f(n) terkecil, diperoleh f(E)= 84. Karena f(n) belum melebihi limit, kembangkan node E (bangkitkan anak-anaknya).
  • Hitung f(n) semua anak E. Apakah masih belum melebihi limit? SUDAH MELEBIHI
  • Diantara semua node yang sudah dibuka, berapa f(n) terkecil? 85. Limit baru = 85.
  • RESTART…

 

  • Simplefied Memory Bounded A* (SMA*)

Algoritma Simplefied Memory Bounded A* atau yang sering disebut dengan (SMA*).

–          Memiliki jumlah memori yang sangat terbatas

–          Menghindari ekspansi terhadap node-node yang telah diekspan sebelumnya

–          Hanya menyimpan node yang paling menjanjikan

–          Harus mengingat “sesuatu” untuk membangkitkan kembali yang tak disimpan dengan cepat

–          Jika memori penuh dan masih perlu membangkitkan node tambahan :

  • Hapus node daun dengan nilai f tertinggi
  • Ingat nilai f dari anak terbaik (yang tak disimpan) pada setiap node induk

Algoritma SMA*

if (status awal adalah status tujuan), then return status tersebut

Langkah1. Tambahkan node root ke antrian Q.

Langkah2. WhileQ tidak kosong atau Gagal Do

Langkah2.1 if Q kosong return Gagal

Langkah2.2.Ambil node berprioritas top dari Q sebagai node terkini

Langkah2.3 if ini adalah status tujuan then return status ini

Langkah2.4 Ambil successor dari node terkini

Langkah2.5 if successor bukan status tujuan dan batas kedalaman yang dicapai

then set f(successor) ke INFINITE

else if (successor) = MAX(f(current), f(successor))

Langkah2.6 if successor adalah yang terakhir then update biaya f ancestors menjadi minimum dari biaya f successornya

Langkah2.7 if tidak ada lagi memory bagi successorthen hapus node nilai f paling tinggi paling dangkal dan ingatlah biaya f terlupakan paling baik

Langkah2.8 Sisipkan anak ke dalam antrian Q

end

Contoh Jarak Terpendek dengan menggunakan algoritma SMA*

 2

  • Pohon dengan 6 node. Node 1 status awal, node 5 dan 6 adalah node tujuan
  • Angka diatas node adalah nilai dari fungsi f untuk node tersebut.
  • Cari jalur terpendek menggunakan SMA* dengan memory maksimum 3 node.

Langkah – langkah :

  • Buka node 1 , diperoleh node 2 dengan f = 12. Simpan ke memory.
  • (b) Memory masih dapat menerima satu node. Buka node 1 dan dapatkan node 3 dan masukkan ke memory. Memory penuh dan tidak ditemukan node tujuan.

Proses selanjutnya:

  • update f dari node 1 dengan f minimum dari anaknya (12/node 2)
  • Buka node 2
  • Keluarkan node daun dengan f paling tertinggi(node 3)
  • Ingat f dari node 3(13).
  • Buka node 4, masukkan ke memory. Bukan tujuan. Selanjutnya:
  • Ingatkan node 3 ke dalam node 1
  • Memory penuh
  • Node 4 bukanlah node tujuan, tandai infinite.
  • Lakukan :
  • Keluarkan node 4 dan tambahkan node 5
  • node 2 mengingat node 5
  • update f dari node 2 dengan f minimum dari anak-anaknya
  • update f dari node 1

Node 5 adalah tujuan. Tetapi masih ada nilai 13 dalam memory, lebih kecil daripada fnode tujuan yang diperoleh. Selanjutnya buka node yang diingat.

  • Node 3dibukalagi, kemudian:
  • Lepaskan node 2 dan tambahkan node 6
  • Ingatkan node 2ke dalam node 1
  • Node 6 adalah tujuan dan node dengan biaya f terkecil.
  • SELESAI

 

  • Bi-Directional A* (BDA*)

Algoritma Bi-Directionan A* atau sering disebut dengan BDA* merupakan turunan dari algoritma A* dimana terdapat dua arah yaitu simpul asal dan simpul tujuan. Pencarian dihentikan jika Best Node dari simpul asal telah berada di dalam CLOSED dari simpul tujuan. Lalu cek apakah harus mengganti parent dari best node tersebut dari arah simpul tujuan atau sebaliknya, pencarian dihentikan jika best node dari simpul tujuan telah berada di dalam CLOSED dari simpul asal. Cek apakah harus mengganti parent dari best node tersebut dari arah simpul asal.

3

Area pencarian yang dilakukan oleh BDA* (b) lebih sempit dibandingkan dengan area pencarian A*(a).

4

 56

 

Modified Bi-Directional A* (MBDA*)

  • Fungsi heuristic untuk simpul n pada pencarian maju (dari S ke G) :

mbda1

  • Fungsi heuristic untuk simpul n pada pencarian mundur (dari G ke S) :

mbda2

7

  •  S         : simpul asal atau initial state
  • G         : simpul tujuan atau goal state
  • g(S,n)             : biaya sebenarnya dari S ke n
  • g(G,n) : biaya sebenarnya dari G ke n
  • hs(n) : biaya perkiraan dari n ke G
  • hg(n) : biaya perkiraan dari n ke S

510

11

  • Dynamic Weighting A* (DWA*)

Algoritma A* yang dinamis. Parameter biaya dapat berubah selama proses penyelesaian masalah. Fungsi heuristic h diberi bobot dinamis, pada awal iterasi lebih baik pencarian dilakukan kearah mana saja tetapi ketika goal sudah dekat barulah pencarian difokuskan ke arah goal. Fungsi heuristic yang digunakan adalah : f(n) = g(n) + w(n) * h(n) dimana w(n) adalah bobot yang pada langkah pertama ditentukan besar dan semakin kecil pada langkah berikutnya. Saat dianggap mendekati tujuan, nilainya mendekati 1, misalnya 11.

dwa1

dwa2

dwa3

  • Beam A* (BA*)

Algoritma Beam A* (BA*) :

  • Membatasi jumlah simpul yang bias disimpan di dalam OPEN
  • Ketika jumlah simpul di Open sudah melebihi batas tertentu, maka simpul dengan nilai f terbesar akan dihapus.
  • Sedangkan jumlah simpul di dalam CLOSED tetap dibiarkan tanpa batasan karena simpul yang didalam CLOSED memang tidak mungkin dihapus.
  • Dengan membatasi jumlah simpul di OPEN, maka pencarian menjadi lebih terfokus seperti sinar (beam).

ba1

Pada kasus ini, misalkan jumlah simpul maksimum yang bias disimpan di dalam OPEN adalah 4. Bagaimana BA* menemukan solusi ?

ba2ba3

 

« Previous Entries