Tugas 1 Kecerdasan Buatan

Tugas Mata Kuliah Kecerdasan Buatan

Nama : Sigit Agung Hariyadi

NIM : 1730511052

1.      Algoritma Searching Hill Climbing

a.      Pengertian

Algoritma Hill Climbing adalah salah satu metode pencarian Heuristic, pencarian Heuristic merupakan teknik pencarian dengan informasi awal sebagai acuan untuk proses selanjutnya dan metode ini memiliki aturan – aturan tertentu untuk mencapai tujuannya. Dalam metode Heuristic terdapat bermacam macam teknik pencarian salah satunya Hill Climbing, Hill Climbing atau Mendaki Bukit dibagi menjadi dua jenis yaitu Simple HC dan Steepest-Ascent HC.

b.      Langkah atau Alur

Alur atau langkah yang digunakan pada metode Hill Climbing adalah dengan cara membandingkan sebuah cara dengan cara lain sehingga ditemukan cara yang efisien misalkan kita akan melakukan perjalanan dari kota A ke kota B maka langkah nya sebagai berikut.

-          Menentukan Posisi awal atau initial state, kemudian dilakukan pengujian dari posisi awal itu. Pengujian dilakukan dengan cara menghitung total jarak yang ditempuh dari kota A ke kota B untuk mendapatkan nilai Heuristic, hasil dari penghitungan tersebut akan dijadikan perbandingan untuk langkah selanjutnya.

-          Setelah menentukan langkah awal maka selanjutnya yaitu melakukan kombinasi penukaran dua jalan kemudian dilakukan pengujian seperti sebelumnya sampai menemukan jarak terdekat dengan kondisi panjang jalur baru < panjang jalur lama

-          Jika jarak terpendek ditemukan maka itu adalah solusinya dan jika bukan maka bukan solusi.

c.       Implementasi dalam Studi Kasus

Untuk implementasinya bisa diambil pada contoh kasus Travelling Salesman Problem (TSP). pada kasus ini Salesman harus berpindah pindah kota dengan ketentuan dalam waktu yang singkat dan biaya yang sedikit. Maka dalam melakukan perjalanan nya seorang Salesman harus menentukan rute terpendek dalam berpindah pindah kota, maka dapat di uraikan sebagai berikut:

-          Jika Salesman berada di kota A dan akan melakukan perjalanan ke kota B, C, D, dan E. maka Kota A akan di tetapkan menjadi posisi awal atau Initial State.

-          Dalam perjalanan nya menuju Kota B, C, D, dan E Salesman akan melakukan penelitian jarak antar kota dan mencari rute yang dapat dilalui.

-          Setelah data rute nya di dapatkan salesman akan melakukan perbandingan jarak sehingga mendapatkan jarak terpendek untuk mencapai kota yang di tuju.

2.      Algoritma Breadth First Search

a.      Pengertian

Metode Pencarian dengan Breadth First Search merupakan teknik pencarian dimana langkah pertamanya adalah root node yang diekspansi, setelah itu dilanjutkan semua successor dari root node juga di expand hal ini diulang sampe node tidak mempunyai successor lagi.

Kelebihan:

-          Tidak menemui jalan buntu

-          Jika ada suatu solusi, maka BFS akan menemukannya, dan jika didapat lebih dari satu solusi maka solusi minimum akan ditemukan

Kekurangan:

-          Membutuhkan memori yang banyak

-          Membutuhkan waktu yang lama

b.      Langkah atau Alur

Pada metode pencarian ini, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya. Demikian seterusnya hingga ditemukannya solusi.

c.       Implementasi pada Studi Kasus

Untuk studi kasus nya disini akan menggunakan permainan Othello, tujuan permainan Othello adalah untuk menghalangi lawan mendapat point dengan cara mem block lawan agar tidak mendapat point. Dalam game ini pemain akan menggunakan warna hitam dan komputer menggunakan warna putih untuk bidak, algoritma BFS yang bekerja dalam permainan ini yaitu jika skor seimbang maka komputer akan mengambil keputusan paling pertama, misal slot yang tersedia adalah A, B, dan C maka komputer akan memilih slot A untuk diisi hal ini diulang sampai permainan selesai.

Referensi 

- Irfan, Muhammad. (2017). Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Hill Climbing dan MATLAB. Jurnal Matematika Vol.16 No.2 Desember 2017.

- Lumenta, Arie S. M. (2014). PERBANDINGAN METODE PENCARIAN DEPTH-FIRST SEARCH, BREADTH-FIRST SEARCH DAN BEST-FIRST SEARCH
PADA PERMAINAN 8-PUZZLE. e-journal Teknik Elektro dan Komputer (2014) ISSN: 2301-8402 1

- Chandra, Yunita., Sabloak, Simmi., Angreni, Renni. Penerapan Algoritma Minimax dan Breadth First Search pada Permainan Othello Menggunakan Framework Phonegap.

- http://azizmusyaffaa.blogspot.com/2016/10/breadth-first-search-depth-first-search.html diakses pada tanggal (14 Oktober)