Nama : Resti YuliantieNRP : 113040286Intelejensia Buatan Kelas B

Tugas 31. buat studi kasus menggunakan 2 contoh seperti sebelumnya (peta

Romania & tree A-Q)2. tentukan sendiri initial state & goal state nya untuk masing-masing

contoh3. telusuri peta Romania menggunakan salah satu algoritma pencarian4. telusuri tree A-Q menggunakan ketiga algoritma pencarian5. bandingkan ketiga algoritma tersebut6. tuliskan hasil pengamatan serta kelebihan dan kekurangan masing-masing

algoritma7. simpulkan algoritma mana yang paling baik

Jawaban :1. Penelusuran peta Romania dengan menggunakan Uniform Cost.

Penelusuran dimulai dari Gradea dan berakhir di Bucharest.

Penelusuran pertama diawali dengan mencari cost dengan nilai paling rendah dan seterusnya hingga didapatkan jalur dari Gradea ke Bucharest dengan nilai cost yang rendah. Berdasarkan perhitungan yang sudah dilakukan maka didapatkan pohon pencarian sebagai berikut:

Yang bergaris merah merupakan jalur yang memiliki cost terendah.

2. Penelusuran three A-Q dengan menggunakan 3 algoritma pencarian.

Dibawah ini merupakan gambar sebuah pohon yang berisikan huruf acak yang terdiri dari huruf A sampai dengan huruf Q.

State dengan lingkaran berwarna merah merupakan Initial State dan state dengan lingkaran

berwarna kuning merupakan Goal State.

a. Pencarian pertama menggunakan algoritma DFS (Depth-First Search). Dengan pencarian DFS tersebut di dapatkan langkah pencarian sebagai berikut:

Angka yang berada pada lingkaran menunjukan urutan langkah dalam pencarian. Sehingga didapatkan jalan pencarian sebagai berikut:A - H - I - K - L - M - P - Q - D – O - B - C - E – F

b. Pencarian kedua menggunakan algoritma BFS (Breadth-First Search). Dengan Pencarian BFS didapatkan langkah pencarian sebagai berikut:

Berdasarkan gambar diatas didapatkan langkah pencarian sebagai berikut:A - H - O - B - I - P - C - J - K - Q - D - E - F

c. Pencarian ketiga menggunakan algoritma UCS (Uniform-First Search).

A - H - O - P - I - B - C - Q - D - J - K - E - F

3. Hasil PengamatanBerdasarkan pengamatan yang telah dilakukan didapatkan bahwa

dengan pencarian algoritma DFS merupakan cara dengan jalan yang paling panjang. Butuh waktu extra untuk menggunakan algoritma DFS karena cara pencariannya yang mengharuskan kita untuk hanya mulai mencari dari sebelah kiri.

Selanjutnya pencarian dengan cara BFS, setelah melakukan pengamatan dengan pencarian ini didapatkan bahwa dengan menggunakan algoritma pencarian ini pencarian akan jauh lebih cepat dibandingkan dengan algoritma DFS. Namun ketika pencarian menemukan cabang dengan length yang sama, maka kita di tuntut untuk memilih secara acak langkah selanjutnya. Dengan algoritma

BFS maka ini lah langkah yang membuatnya menjadi lambat karena ketika harus memilih acak akan membuat kebingungan tersendiri.

Algoritma pencarian UCS sejauh ini merupakan cara yang paling efisien karena kita dapat melakukan pencarian dengan perkiraan jarak atau cost yang terdekat. Jika state yang dicari adalah state yang jaraknya dekat dengan state awal maka dengan algoritma ini pencarian akan jauh lebih cepat.

4. KesimpulanAlgoritma pencarian UCS merupakan algoritma yang paling efisien

karena goal state dengan jarak dekat dapat dengan cepat ditemukan dengan algoritma ini sedangkan jika menggunakan algoritma BFS meskipun state goal nya dekat kita tetap akan mengalami kesulitan karena diharuskan memilih langkah selanjutnya secara acak. Sedangkan bila kita menggunkan algoritma pencarian DFS maka waktu yang dibutuhkan akan sangat lama karena kita harus menulusuri satu demi satu jalur dan harus dimulai dari sebelah kiri.