Uts Kecerdasan Buatan Mirza Alfariz. No 1 [PDF]

Citation preview

MAKALAH KECERDASAN BUATAN Disusun untuk memenuhi ujian tengah semester Mata Kuliah : Kecerdasan Buatan Dosen Pengampu : Alda Cendekia Siregar, S.Kom.,M.Cs



Oleh : Mirza Alfariz (202220096)



KELAS 20 JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH PONTIANAK



KATA PENGANTAR



Segala puji bagi Tuhan Yang Maha Esa yang telah menolong hamba-Nya menyelesaikan makalah ini dengan penuh kemudahan. Berkat pertolongan-Nya saya mampu menyelesaikan makalah ini tepat pada waktunya. Makalah ini disusun untuk memenuhi ujian tengah semester dalam mata kuliah Kecerdasan Buatan, yang saya sajikan berdasarkan pengamatan dari berbagai sumber. Makalah ini saya susun penuh dengan teliti untuk mempersiapkan makalah ini dengan baik. Saya juga mendapati beberapa rintangan ketika membuat makalah ini, namun dengan penuh kesabaran dan terutama pertolongan dari Tuhan YME akhirnya makalah ini dapat terselesaikan.



Semoga makalah ini dapat memberikan wawasan yang lebih luas kepada pembaca. Walaupun makalah ini memiliki kelebihan dan kekurangan. Saya mohon untuk saran dan kritiknya untuk pengembangan makalah yang lebih baik di masa depan. Terima kasih.



Pontianak, 1 Februari 2021



Penulis



iii



DAFTAR ISI



JUDUL ……………………………………………………….……………….……………...i KATA PENGANTAR ……………………………………....................................................ii DAFTAR ISI ……………………………………...……………………………...…………iii BAB I PENDAHULUAN ………………………………………………………….……….1 1. Latar Belakang ………………………………………………………….……….……1 2. Tujuan …………………………………………………………………..……………..1 3. Metode Penulisan …………………………………………………….……….………1 BAB II PEMBAHASAN ………………………….………….…..........................................2 1. 2. 3. 4.



Algoritma Pencarian Melebar (Breadth – First Search)………………………………2 Cara Kerja Algoritma BFS……………………………………………………………2 Aplikasi Algoritma BFS dalam Teori Graf..………………………………………….3 Pencarian Terbaik Pertama (Best First Search)……………………………………….4



BAB III PENUTUP…………………………………………………….…………………...10 1. Kesimpulan .…………………………………………………………….…………...10 DAFTAR PUSTAKA ………………………………………………………………………11



BAB I iiii



PENDAHULUAN 1.



Latar Belakang



Pemecahan masalah dengan representasi graf dilakukan pertama-tama dengan membuat representasi objek masalah sebagai simpul dalam graf serta membuat representasi hubungan antar objek dengan garis yang menghubungkan simpul-simpul tersebut. Setelah itu, setiap simpul dalam graf dikunjungi secara sistematis (traverse). Dalam graf terdapat dua macam algoritma traversal, yaitu: a. Algoritma pencarian melebar (breadth-first search / BFS) b. Algoritma pencarian mendalam (depth-first search / DFS) Meskipun kedua algoritma ini memiliki tujuan yang sama, yaitu mengunjungi setiap simpul dalam graf, pendekatan yang dilakukan oleh keduanya masing-masing berbeda, sehingga aplikasi penggunaan masing-masing algoritma ini juga berbeda sesuai kebutuhan masalah. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yangsederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informedmenggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarianuntuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun dalammetode pencarian heuristik digunakan dengan metode terbimbing karena memangmemudahkan dalam proses pencarian. Algoritma Pencarian ini menggunakan Metode BFS,Generate and test, dll. 2.



Tujuan



Untuk memenuhi Ujian Tengah Semester mata kuliah Kecerdasan Buatan yang Dibimbing Oleh dosen Alda Cendekia Siregar, S.Kom.,M.Cs 3.



Metode Penulisan



Metode penulisan yang digunakan untuk pembuatan makalah ini, research; dimana dalam pencarian teori, peneliti mengumpulkan informasi sebanyak-banyaknya dari kepustakaan yang berhubungan.



BAB 1 II



PEMBAHASAN 2.1.



Algoritma Pencarian Melebar (Breadth – First Search)



Algoritma pencarian melebar (BFS) mengunjungi setiap simpul dalam graf mulai dari simpul akar, lalu dilanjutkan dengan mengunjungi simpul-simpul yang bertetangga dengan simpul akar tersebut. Setelah itu, untuk setiap simpul yang sudah dikunjungi tersebut, dikunjungi simpul-simpul yang bertetangga dengannya dan belum dikunjungi, demikian seterusnya sampai seluruh simpul berhasil dikunjungi. Berikut gambar yang mengilustrasikan urutan simpul yang dikunjungi pada algoritma BFS:



Gambar 2.1 Ilustrasi urutan kunjungan simpul pada algoritma BFS Dari gambar di atas, dapat dilihat bahwa dengan algoritma BFS, setiap simpul pada tingkat x dikunjungi lebih dahulu sebelum simpul pada tingkat di bawahnya (x+1). 2.2.



Cara Kerja Algoritma BFS



Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS: 1. Masukkan simpul ujung (akar) ke dalam antrian 2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi 3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan. 4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian 5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan 2 mengembalikan hasil solusi tidak ditemukan



6. Ulangi pencarian dari langkah kedua 2.3.



Aplikasi Algoritma BFS dalam Teori Graf



Karena algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf. Berikut contoh-contoh penggunaan algoritma BFS dalam persoalan teori graf: 2.3.1. Pengecekan Graf Bipartit Graf bipartit adalah graf yang seluruh simpulnya dapat dipisah menjadi dua bagian, serta setiap sisi graf menghubungkan dua simpul yang masing-masing berada pada bagian yang berbeda, sehingga tidak ada simpul pada bagian yang sama yang bertetangga. BFS digunakan untuk mengecek apakah suatu graf merupakan graf bipartit atau bukan dengan memulai pencarian pada simpul manapun, lalu memberi nilai 0 dan 1 pada setiap simpul yang dikunjungi. Angka ini menandakan bagian di mana simpul tersebut berada. Contoh pemberian nilai pada graf: Jika simpul awal diberi nilai 0, maka seluruh simpul yang bertetangga dengannya diberi nilai 1, lalu seluruh simpul yang bertetangga dengan simpul bernilai 1 tersebut diberi nilai 0, dan seterusnya. Dalam pemberian nilai ini, jika dicapai simpul yang telah dikunjungi sebelumnya, dicek apakah simpul tersebut berada pada tingkat yang sama dengan simpul ayahnya, dengan cara pengecekan nilai kedua simpul tersebut yang bertetangga tersebut. Jika simpul bertetangga dengan simpul yang bernilai sama dengannya, maka dapat disimpulkan bahwa graf bukan merupakan graf bipartit. Jika sampai akhir pemberian nilai hal tersebut tidak terjadi, maka graf tersebut merupakan graf bipartit. 2.3.2. Pencarian Komponen Terhubung dalam Graf Dua buah komponen dinyatakan terhubung dalam graf jika terdapat lintasan antara keduanya. Dalam algoritma BFS, seluruh simpul yang dikunjungi pasti merupakan simpul yang terhubung dengan simpul akar, karena simpul-simpul tersebut hanya dikunjungi jika bertetangga dengan simpul ayahnya. Seluruh simpul yang terhubung dengan simpul akar juga pasti dikunjungi. Oleh karena itu, seluruh simpul yang dikunjungi dalam algoritma BFS dan masuk ke dalam pembentukan pohon BFS adalah komponen terhubung terbesar pada graf yang mencakup simpul awal (akar). 2.3.3. Pencarian Jarak Terpendek pada Graf Tak Berbobot Pada graf tak berbobot, jarak terpendek antara dua simpul hanya ditentukan oleh jumlah simpul atau jumlah sisi yang berada di lintasan antara dua simpul tersebut. Untuk mendapatkan jarak terpendek seperti ini, algoritma BFS dapat digunakan untuk menyelesaikan persoalan. Pohon yang dibentuk dalam algoritma BFS memiliki sisi yang menghubungkan simpul-simpul pada setiap tingkat. Tidak mungkin ada sisi dalam graf yang terhubung dan berada di luar tingkat-tingkat pada pohon tersebut. Hal ini menandakan bahwa pohon 3



algoritma BFS menampilkan jarak terpendek antara simpul akar dan simpul-simpul lainnya dalam graf. Setiap simpul terhubung dengan akar, sehingga jarak terpendek dari simpul ke akar sama dengan tingkat simpul tersebut. 2.3.4. Pencarian Diameter Pohon Diameter dari sebuah pohon adalah lintasan terpanjang dari seluruh jarak terpendek antara dua simpul pada suatu pohon. Dalam pencarian diameter pohon, digunakan algoritma BFS seperti yang telah diterangkan di atas untuk mendapatkan jarak terpendek dari setiap simpul. Hasil dari penghitungan jarak terpendek masing-masing tersebut digunakan bersama dengan satu variabel global yang menyatakan panjang maksimum untuk mendapatkan diameter pohon. Berikut algoritma untuk mencari diameter pohon: 1. Inisialisasi panjang maksimum = 0 2. Lakukan algoritma BFS pada pohon 3. Masukkan hasil jarak terpendek pada suatu simpul ke variabel temp 4. Jika panjang maksimum < temp, maka panjang maksimum = temp 5. Ulangi dari langkah 2 sampai jarak terpendek seluruh simpul telah dicari 6. Kembalikan panjang maksimum Panjang maksimum yang dikembalikan merupakan diameter pohon yang dicari. 2.4.



Pencarian Terbaik Pertama (Best First Search)



Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search dengan mengambil kelebihan dari kedua teknik tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node pada lebih rendah meskipun node tersebut memiliki nilai heuristic lebih baik. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk. Ada beberapa istilah yang sering digunakan pada metode best-first search, yaitu: 1. Start node adalah sebuah terminology untuk posisi awal sebuah pencarian. 2. Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek. 3. Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node 4. Simpul (node) merupakan representasi dari area pencarian. 5. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan. 6. Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. 7. Goal node yaitu simpul tujuan. 8. Parent adalah curret node dari suksesor.



4



2.4.1. Algoritma Best-First Search Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada gambar dibawah ini.



Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi. Algoritma selengkapnya adalah sebagai berikut. 1. OPEN berisi initial state dan CLOSED masih kosong. 2. Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN. a. Ambil simpul terbaik yang ada di OPEN. b. Jika simpul tersebut sama dengan goal, maka sukses c. Jika tidak, masukkan simpul tersebut ke dalam CLOSED d. Bangkitkan semua aksesor dari simpul tersebut e. Untuk setiap suksesor kerjakan: - Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent. - Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya.



5



Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya. Contoh: Misalkan kita memiliki ruang pencarian seperti pada gambar dibawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa mengurut nilai untuk setiap node.



Algoritma yang menggunakan metode best-first search, yaitu: a. Algoritma A* A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal. Contoh: Langkah 1: Arena 6



Berikut adalah contoh simple arena yang akan kita gunakan. Warna hijau adalah starting point, warna merah adalah goal/end point, dan biru adalah penghalang. Goal dari aplikasi ini adalah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru



Langkah 2: Movement Cost / Biaya Pergerakan Kita asumsikan setiap langkah dari hijau adalah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G adalah cost atau biaya dalam setiap langkah. Dalam kasus ini kita akan berikan nilai 10 untuk setiap langkah vertikal maupun horizontal, dan 14 untuk diagonal. Nilai 14 kita dapatkan dari perhitungan pitagoras dimana 14,1421 = sqrt(sqr(10)+sqr(10)). Hasil data nilai G ini selanjutnya kita gambarkan sbb :



Selain dari perhitungan tersebut, kita dapat mengalikan dengan konstanta tertentu untuk memanipulasi biaya, misal : ketika melewati sungai maka G = G * 2. Langkah 3: Estimated Movement / Estimasi gerakan Langkah selanjutnya kita hitung biaya estimasi pergerakan dan kita simbolkan dengan H. Nilai H ini secara singkat adalah nilai jarak / estimasi biaya dari pergerakan dari suatu titik terhadap titik finish dengan mengabaikan penghalang yang ada. Untuk lebih jelasnya silahkan lihat gambar di bawah :



7



Langkah 4 : Scoring / Penilaian Setelah nilai G dan H kita dapatkan, maka kita berikan skor dari masing-masing titik yang akan dilalui. Skor kita lambangkan misalnya dengan F dimana nilai F = G + H. Nilai F selanjutnya kita masukkan dalam setiap titik dari setiap langkah yang akan dilalui. Untuk lebih jelasnya lihat gambar di bawah :



Dari setiap nilai tersebut kita ambil keputusan dengan mengambil langkah dengan nilai F terkecil.



Langkah 5 : Looping / Perulangan Setelah pergerakan pertama selesai selanjutnya lakukan perulangan dari dari langkah 1 sampai 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah :



8



b. Greedy Best-First Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.



9



BAB III PENUTUP KESIMPULAN Algoritma BFS dan DFS dapat memecahkan masalah- masalah klasik dalam teori graf dengan mangkus. Pemilihan algoritma yang digunakan untuk memecahkan masalah disesusaikan dengan kebutuhan karena algoritma BFS dan DFS memiliki kelebihan dan kekurangan masing-masing. Sebagian masalah, seperti pengecekan graf bipartit lebih tepat diselesaikan dengan menggunakan algoritma BFS, sedangkan masalah lainnya seperti pencarian komponen terhubung kuat lebih tepat diselesaikan dengan menggunakan algoritma DFS. Ada pula masalah yang dapat diselesaikan sama baiknya oleh algoritma BFS dan DFS seperti pencarian komponen terhubung dalam graf. Dengan terpecahkannya masalah-masalah klasik teori graf tersebut, terbukti bahwa pemecahan masalah-masalah aplikasi dunia nyata dengan cara pembuatan representasi masalah dalam graf dan penggunaan algoritma traversal dalam graf merupakan cara yang mangkus. Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.



10



DAFTAR PUSTAKA [1] Wikipedia, Breadth-First Search, http://en.wikipedia.org/wiki/Breadth_first_search. Tanggal akses: 31 Januari 2021, pukul 13.00. [2] Basic Graph Algorithms. cs.anu.edu.au/student/comp3600/apac/basic_graph_al gorithms.pdf. Tanggal akses: 31 Januari 2021, pukul 19.29. [3] Munir, Rinaldi. (2007). Diktat Kuliah IF2251 Strategi Algoritmik. Program Studi Teknik Informatika, Institut Teknologi Bandung. 2021. [4] Munir, Rinaldi. (2006). Diktat Kuliah IF2153 Matematika Diskrit. Program Studi Teknik Informatika, Institut Teknologi Bandung. 2021. [5] Wikipedia, Depth-First Search, http://en.wikipedia.org/wiki/Depth_first_search. Tanggal akses: 31 Januari 2021, pukul 23.50 [6] Eppstein, David. BFS and DFS. http://www.ics.uci.edu/~eppstein/161/960215.html. Tanggal akses: 31 Januari 2021, pukul 19.06. [7] Makalah kecerdasan buatan Metode Pencarian Heuristik, Generate and Test, Hill Climbing, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Best-First Seacrh, Algoritma A*, Simulated Annealing. | Teknik Elektro (elektrojoker13unc.blogspot.com)



11