Uniform
Cost Search (UCS)
A.
Pengertian Dan Penjelasan
Uniform Cost Search adalah algoritma Seach Tree (graph)
yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai
pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana
node tersebut dipilih yang memilki harga (cost) terkecil dari root node.
Algoritma ini merupakan modifikasi dari Bread First Search (BFS).
Dalam implementasi algoritma ini , melibatkan semua
node yang berhubungan dengan root node, dan meletakannya dalam priority queue
untuk mencapai node tujuan. Dimana node – node yang dipilih merupakan node yang
berharga terkecil.
Seperti tampak pada gambar, initial state terletak pada node start, kemudian
untuk mencapai node berikutnya, algoritma ini memilih jalur yang memilki harga
terkecil diantara dua node di depannya. Begitu seterusnya, dilakukan pengecekan
node yang memilki harga terkecil hingga sampai pada goal state.
UCS adalah algoritma terbaik untuk masalah pencarian,
yang tidak melibatkan penggunaan heuristik. Hal ini dapat memecahkan grafik
umum untuk biaya yang optimal. UCS kedengarannya pencarian di cabang yang
kurang lebih sama dalam biaya.
Iterative
Deepening Search (IDS)
A.
Pengertian Dan Penjelasan
Metode Iterative Deepening A* Iterative-Deepening A*
(IDA*) search algorithm adalah pengembangan dari A*search algorithm yang
dikombinasikan dengan iterative deepening search. IDA* search algorithm
merupakan best-first searches yang optimal dalam hal solution cost, time, dan
space. Prinsip algoritma iterative deepening search adalah melakukan
depth-limited search secara bertahap dengan nilai l yang incremental . Contoh
cara kerja iterative deepening search dapat dilihat pada gambar:
Pada
metode IDA* search algorithm digunakan fungsi evaluasi yang sama seperti metode
A* yaitu sebagai berikut:
f(n) =
g(n) + h(n) (6)
Dimana: f(n) = estimasi total cost suatu path dari node awal ke node tujuan melalui node n g(n) = cost dari suatu path untuk mencapai node n dari node awal h(n) = estimasi cost suatu path
Dimana: f(n) = estimasi total cost suatu path dari node awal ke node tujuan melalui node n g(n) = cost dari suatu path untuk mencapai node n dari node awal h(n) = estimasi cost suatu path
Iteratif memperdalam kedalaman-pertama
pencarian (IDS) adalah pencarian ruang strategi di mana pencarian
mendalam-terbatas dijalankan berulang kali, meningkatkan batas kedalaman dengan
setiap iterasi sampai mencapai, kedalaman negara tujuan dangkal. IDS setara
dengan luas-pertama pencarian, tetapi menggunakan memori lebih sedikit, pada
setiap iterasi, ia mengunjungi node dalam pohon pencarian dalam urutan yang
sama seperti depth-first search, tapi urutan kumulatif di mana node pertama
kali mengunjungi secara efektif luasnya -pertama.
IDS menggabungkan depth-first pencari ruang-efisiensi dan kelengkapan luas-pertama pencarian ini (ketika faktor percabangan terbatas). Ini adalah optimal ketika biaya jalan adalah fungsi non-penurunan kedalaman node.
Kompleksitas ruang IDS adalah, di mana merupakan faktor percabangan dan kedalaman dangkal gawang. Karena berulang memperdalam kunjungan menyatakan beberapa kali, hal itu mungkin tampak sia-sia, tapi ternyata menjadi tidak begitu mahal, karena di pohon sebagian besar node berada di tingkat bawah, sehingga tidak terlalu menjadi masalah jika tingkat atas yang dikunjungi beberapa kali.
Keuntungan utama dari IDS dalam mencari permainan pohon adalah bahwa pencarian sebelumnya cenderung meningkatkan heuristik yang biasa digunakan, seperti heuristik pembunuh dan pemangkasan alpha-beta, sehingga perkiraan yang lebih akurat dari skor berbagai node pada pencarian kedalaman akhir dapat terjadi, dan pencarian selesai lebih cepat karena dilakukan dalam urutan yang lebih baik. Misalnya, alpha-beta pemangkasan yang paling efisien jika ia mencari langkah terbaik pertama.
IDS menggabungkan depth-first pencari ruang-efisiensi dan kelengkapan luas-pertama pencarian ini (ketika faktor percabangan terbatas). Ini adalah optimal ketika biaya jalan adalah fungsi non-penurunan kedalaman node.
Kompleksitas ruang IDS adalah, di mana merupakan faktor percabangan dan kedalaman dangkal gawang. Karena berulang memperdalam kunjungan menyatakan beberapa kali, hal itu mungkin tampak sia-sia, tapi ternyata menjadi tidak begitu mahal, karena di pohon sebagian besar node berada di tingkat bawah, sehingga tidak terlalu menjadi masalah jika tingkat atas yang dikunjungi beberapa kali.
Keuntungan utama dari IDS dalam mencari permainan pohon adalah bahwa pencarian sebelumnya cenderung meningkatkan heuristik yang biasa digunakan, seperti heuristik pembunuh dan pemangkasan alpha-beta, sehingga perkiraan yang lebih akurat dari skor berbagai node pada pencarian kedalaman akhir dapat terjadi, dan pencarian selesai lebih cepat karena dilakukan dalam urutan yang lebih baik. Misalnya, alpha-beta pemangkasan yang paling efisien jika ia mencari langkah terbaik pertama.
