SMA * Search (Simplified Memory-Bounded) A*

Simplified Memory-Bounded A* atau biasa disebut SMA* merupakan algoritma pencarian yang dapat menggunakan semua memori yang tersedia untuk melakukan pencarian. Menggunakan lebih banyak memori hanya dapat meningkatkan efisiensi pencarian, salah satunya bisa selalu mengabaikan ruang tambahan, tetapi biasanya lebih baik untuk mengingat node daripada harus membuatnya kembali bila diperlukan.

SMA* memiliki gambaran berikut :

1. Dia akan memanfaatkan memori apa pun yang tersedia untuk nya.
2. Dia menghindari pernyataan berulang sejauh memori memungkinkan.
3. Dia selesai jika memori yang tersedia cukup untuk menyimpan jalur solusi dangkal.
4. Dia optimal jika tersedia cukup memori untuk menyimpan jalur solusi dangkal optimal. Jika tidak, dia mengembalikan solusi terbaik yang dapat dicapai, dengan memori yang tersedia.

Algoritma SMA* ini merupakan sebuah algoritma yang dikembangkan dari algoritma A* (A Star). Algoritma A* sendiri adalah variasi dari algoritma Branch and Bound. Jadi secara tidak langsung, algoritma SMA* itu sendiri merupakan salah satu variasi pengembangan dari algoritma Branch and Bound. Menggunakan algoritma SMA* berarti kita memperhitungkan biaya sebenarnya ditambah dengan biaya perkiraan. Biaya sebenarnya dinotasikan dengan g(n). Sedangkan biaya perkiraan dinotasikan dengan h(n). Jadi kita memperhitungkan g(n) + h(n). 

Contoh penggunaan Algoritma SMA* dalam pencarian lintasan

Dalam algoritma SMA* yang digunakan untuk mencari lintasan yang paling efisien ini, dibutukan sebuah Queue yang digunakan untuk memanipulasi antrian simpul yang terurut berdasarkan f-cost-nya. f-cost itu sendiri adalah g(n)+h(n).

Ini contoh gambar jalurnya :

Permasalahan yang ada adalah bagaimana kita mengetahui jalur yang paling efisien untuk pergi dari satu kota ke kota lainnya. Untuk memudahkan pengertian mengenai makalah ini, penulis akan memberikan gambaran singkat dimana apabila kita akan pergi dari kota A menuju kota O, maka akan ada banyak jalur yang bisa ditempuh dengan berbagai macam jarak dan tarif antar kotanya. Setiap perjalanan dari simpul satu ke simpul lainnya, akan ada dua variable. Variable pertama adalah jarak yang menghubungkan kedua simpul. Sedangkan variable kedua adalah biaya yang harus dibayarkan oleh seseorang apabila ingin berpergian dari satu simpul ke simpul lainnya.

Jalur-jalur yang dapat ditempuh dari kota A menuju kota O adalah sebagai berikut : 

1.  A > B > D > L > O 

2.  A > B > H > K > O 

3.  A > C > F > I > J > O 

4.  A > E > G > I > J > O 

5.  A > E > G > N > M > O

========================================================================

Berikut langkah penyelesaiannya :

Pada langkah ini, nilai f(A) = 0 

Pada langkah ini, dicari nilai dari setiap simpul dari suksesor (A), yaitu simpul B,C,E dan didapatkan hasil :  

f-cost(B) = 175 

f-cost(C) = 187 

f-cost(E) = 197

Pada langkah ini, didapat nilai f-cost untuk masing-masing simpul sebagai berikut :

f-cost(D) = 285 

f-cost(H) = 415 

f-cost(F) = 267 

f-cost(G) = 341

pada langkah ini, simpul G dan E dihapus karena sesuai dengan aturan SMA* no 2 dan 3 yang ada di atas.

Pada langkah ini, didapat nilai f-cost sebagai berikut : 

f-cost(L) = 500 

f-cost(K) = 500 

f-cost(I) = 367 

pada langkah ketiga ini, simpul B dan semua suksesornya dihapus, karena sesuai dengan aturan SMA* no 2 dan 3, sehingga kita tinggal menyisakan rute A>C>F>I

Pada langkah ini, didapat dua simpul suksesor dari simpul I dengan nilai f-cost masing-masing sebagai berikut : 

f-cost(J) = 500 

f-cost(M) = 443 

Kemudian pada langkah terakhir, kita telah sampai simpul tujuan, dan didapatkan hasil yang minimum adalah dengan nilai f-cost = 643 dan memiliki jalur A>C>F>I>J>O.

Sumber :

http://cs.txstate.edu/~ma04/files/CS5346/SMA%20search.pdf

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-065.pdf