Kami dari Kelompok 06 Kecerdasan Buatan D akan mengimplementasikan tentang 2 Algoritma Informed Search yaitu A* Algorithm dan Greedy BFS
Kelompok 06 Kecerdasan Buatan D :
Nama | NRP |
---|---|
Calvin Janitra | 5025211020 |
Kevin Nathanael Halim | 5025211140 |
M. Zhafran Dzaky | 5025211142 |
M. Naufal Badruttamam | 5025211240 |
Pada repository ini, kami mengimplementasikan 2 Algoritma Informed Search yaitu Greedy Best First Search Algorithm dan A* Algorithm menggunakan bahasa Python ke dalam file dengan format .ipynb untuk menjalankan satu contoh kasus yang telah diberikan. Contoh kasus yang digunakan sendiri adalah contoh kasus pada powerpoint yakni Romania Problem yang merupakan permasalahan klasik untuk Informed Search. Pada permasalahan tersebut terdapat peta Romania yang terdiri dari beberapa kota dengan diberikan informasi jarak antar kota-kota yang ada. Tujuan pada kasus yang digunakan adalah untuk melakukan pencarian jalur terpendek untuk pergi dari satu kota ke yang lain, dalam hal ini adalah dari Aran ke Bucharest. Selain dari contoh kasus yang ada, kami juga menyertakan kasus custom yang kami buat sendiri dengan judul Java Problem dimana terdapat peta pulau Jawa yang terdiri dari beberapa kota di sana dengan diberikan informasi jarak antar kota-kota yang ada. Tujuan pada kasus ini sama dengan contoh kasus sebelumnya, akan tetapi jalur terpendek yang dicari adalah dari Surabaya ke Tulungagung. Tujuan : Untuk mengetahui bagaimana performa kedua metode informed search tersebut dan perbandingannya antara yang satu dengan yang lain.
Greedy Best First Search adalah salah satu algoritma Informed Search yang bekerja dengan memilih satu jalur pencarian yang terlihat menjanjikan atau terbaik saat itu. Merupakan hasil penggabungan dari algoritma Depth-First Search dan Breadth-First Search sehingga lebih efisien dari keduanya karena dapat bergerak dengan memilih mana yang lebih baik dari kedua algoritma tersebut sesuai dengan kondisi terkini. Cara kerja algoritma Greedy BFS ini sendiri adalah dengan memanfaatkan Heuristic Functions untuk menentukan jarak dari state terkini ke goal state dan memilih node yang terlihat paling baik (jaraknya paling dekat) pada setiap langkah pencarian hingga goal state tercapai. Algoritma ini dapat diimplementasikan menggunakan struktur data Priority Queue. Perumusan yang digunakan untuk menentukan cost terbaik dari node yang akan dilalui sendiri sebagai berikut,
f(n) = h(n)
Dimana :
Algoritma A* adalah salah satu jenis algoritma Informed Search yang juga memanfaatkan Heuristic Function untuk mempercepat proses pencarian solusi terbaik. Kelebihan dari algoritma ini adalah konsepnya yang mengkombinasikan informasi tentang jarak yang telah ditempuh dengan estimasi jarak yang tersisa untuk mencapai tujuan.
Cara kerja algoritma A* adalah dengan mempertimbangkan dua nilai untuk setiap node pada setiap langkah pencarian, yaitu cost aktual yang telah ditempuh dari state awal ke state yang sedang dipertimbangkan (biasanya dinotasikan dengan g(n)) dan estimasi cost yang tersisa untuk mencapai tujuan (biasanya dinotasikan dengan h(n)).
Algoritma A* memiliih node yang memiliki nilai f(n) = g(n) + h(n) yang terkecil pada setiap langkah pencarian, di mana f(n) adalah fungsi yang menghitung total cost dari state awal hingga goal state melalui state yang sedang dipertimbangkan.
Untuk mengimplementasikan algoritma A*, kita dapat menggunakan struktur data Priority Queue untuk menyimpan node-node yang akan dievaluasi. Selain itu, kita juga memerlukan sebuah sebuah Heuristic Function yang dapat memberikan estimasi cost yang tersisa untuk mencapai tujuan dari setiap state pada graf.
Sehingga, formulasi untuk algoritma A* dapat dituliskan sebagai berikut,
f(n) = g(n) + h(n)
di mana :
Algoritma A* cenderung menghasilkan cost yang lebih kecil dibandingkan dengan Greedy Search, karena A* menggabungkan informasi biaya dan heuristik dalam pemilihan node berikutnya, sehingga memungkinkan A* untuk mengeksplorasi jalur yang lebih efisien. Namun, ada kemungkinan bahwa Greedy Search bisa menghasilkan solusi yang lebih baik dalam beberapa kasus, terutama ketika goal state cukup dekat dengan state awal dan heuristik yang digunakan sudah cukup akurat.
Sementara itu, jumlah node yang diekspansi oleh A* dan Greedy Search tidak tetap karena dipengaruhi oleh struktur graf dan heuristik yang digunakan. Dalam beberapa kasus, A* dapat menghasilkan jumlah node yang lebih sedikit dibandingkan dengan Greedy Search, tetapi dalam kasus lain, jumlah node yang diekspansi oleh A* bisa jadi lebih besar daripada Greedy Search.
Oleh karena itu, untuk memilih algoritma pencarian yang tepat, kita perlu mempertimbangkan karakteristik dari masalah yang akan diselesaikan dan melakukan evaluasi kinerja dengan melakukan beberapa test case yang mencakup berbagai kemungkinan kondisi masalah.