Artikel ini dibuat untuk memenuhi tugas 2 mata kuliah Kecerdasan Buatan
1. Searching
Di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
a. Blind Searching
Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki informasi awal, Blind Searching sendiri dibagi menjadi tiga macam yaitu :
- BFS (Breadth First Search)
- DFS (Depth-first Search)
- UCS (Uniform Cost Search)
b. Heuristik Searching
Pencarian buta tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang besar, teknik pencarian buta bukan metode yang baik karena keterbatasan kecepatan komputer dan memori. Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan -> disebut fungsi heuristic Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine
2. Reasoning
Teknik ini digunakan untuk melakukan penalaran terhadap suatu masalah yang dialami manusia. Dalam teknik ini, pengetahuan menjadi basis utamanya.Contoh :
Dalam dunia kedokteran, telah berhasil dibangun sebuah software yang disebut MedicWare yang digunakan untuk merekam catatan medis pasien. MedicWare dilengkapi dengan ribuan pengetahuan tentang jenis, merek, efek samping dan interaksi berbagai jenis obat-obatan.
3. Planning
Planning adalah suatu metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satudemi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadisebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.
Dua metode perencanaan yang cukup populer dan sudah pernah diuji pada Dunia Balok adalah Goal-Stack-Planning (GSP) dan Constraint-Posting (CP). GSP dan CP memiliki kelemahan dan keunggulan masing-masing. Dari segi kemudahan implementasidan biaya komputasi, GSP lebih unggul dibanding CP. Sedangkan, dari segi efisiensiRencana Penyelesaian yang dihasilkan, CP pada umumnya lebih unggul dibanding GSP.
4. Learning
Teknik ini digunakan untuk membuat mesin-mesin otomatis melalui proses pembelajaran dan pelatihan sedemikian rupa hingga bisa menjadi cerdas layaknya manusia. Teknik ini telah diterapkan pada berbagai bidang, seperti transportasi, speech processing, computer vision, robotics dan sebagainya.
Contohnya :
Sebuah mobil bisa berjalan sendiri tanpa disetir oleh manusia. Hal ini dimungkinkan karena sistem pengendali otomatis telah dirancang sedemikian rupa dengan jaringan syaraf tiruan (JST) yang dilatih dengan berbagai gambar kondisi jalan raya yang ditangkap melalui kamera yang diletakkan di mobil.
Penerapan metode A* dalam soal pencarian jarak terdekat
Gambar ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi-posisi koordinat dua dimensi (x,y). Setiap busur memiliki 2 atribut, angka pertama menyatakan panjang jalan sebenarnya (dalam satuan kilo meter), dan angka yang berada dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah gedung yang terletak di persimpangan G.
Maka bagaimana cara penyelesaiannya?
Kita harus mengetahui dulu rumus untuk Algoritma A*
Untuk
fungsi matematisnya dapat dituliskan seperti berikut:
f(n) = g(n) + h(n)
Keterangan :
f(n) : Biaya estimasi terendah
g(n) : biaya yang telah dikeluarkan dari keadaan awal hingga node (n)
h(n) : estimasi dari biaya yang dikeluarkan dari keadaan n atau node (n) hingga
sampai ke tujuan
- Mencari Nilai Heuristik
Rumus :
Keterangan :
x2 = titik x simpul akhir y2 = titik y simpul akhir
x1 = titik x simpul awal y1 = titik y simpul awal
Untuk menghitung nilai heuristik/ h(n)/D bisa dilihat dilembar kertas berikut :
Pertama-tama kita tentukan titik koordinat lalu hitung titik indeks dari semua titik ke titik G.
Setelah selesai, kita masuk ke langkah berikutnya, yaitu menentukan Open dan Close juga Best Node, karena hanya terdapat satu simpul yaitu S maka S disini terpilih menjadi BestNode(Simpul terbaik) , kemudian titik A,B,C sebagai suksesor S masuk ke Open.
Cara menghitung f(n) setiap node,
- F(A) = g(s)+g(S ke A)+h(A) = 0+5+15,5 = 20,5
- F(B) = g(s)+g(S ke B)+h(B) = 0+10+15=25
- F(C) = g(s)+g(S ke C)+h(C) = 0+5+15,5 =20,5
A dan C karena harga terkecil maka pindah ke Closed, masukan BDF ke open
- F(D) = g(s)+g(S ke D)+h(D) = 0+(5+14)+5 = 24
- F(B) = g(s)+g(S ke B)+h(B) = 0+(5+4)+15=24 (nilai f(b) diperbaharui karena jarak S-A-B lebih kecil daripada S-B)
- F(F) = g(s)+g(S ke F)+h(F) = 0+(5+12)+5 =22
Karena F nilai terkecil maka terpilih menjadi bestnode dan dimasukan ke closed, lalu cek nilai E dan F masukkan ke open.
Karena G memiliki nilai terkecil yaitu 22, maka solusi sudah ditemukan jarak terpendek adalah S-C-F-G
Referensi
Aviaton, A. (2017, November 12). Penyelesaian Masalah Melalui Proses Pencarian ( Searching ). Retrieved from adiazep: https://adiazep.wordpress.com/2017/11/12/penyelesaian-masalah-melalui-proses-pencarian-searching/
Hestiningsih, I. (n.d.). PENGANTAR KECERDASAN BUATAN.
Setiawan, K., Supriyadin, Santoso, I., & Buana, R. (2018). MENGHITUNG RUTE TERPENDEK MENGGUNAKAN ALGORITMA A* DENGAN. SENTIKA, 70-79.
haii
BalasHapus