Metode Penyelesaian Masalah AI dan Implementasi Algoritma A*(star) dalam Pencarian Rute Terpendek
1. Dalam bahasan Kecerdasan Buatan sebuah software/hardware disebut cerdas jika memiliki kemampuan untuk Searching, Reasoning, Planning, dan Learning. Jelaskanlah pernyataan tersebut disertai dengan Contoh!
- Searching adalah metode penyelesaian masalah yang terjadi di dalam Artifical Intelligence. Metode searching pada Artifical Intelligence merupakan searching terhadap penyelesaian suatu permasalahan bukan searching terhadap sebuah data tertentu. Adapun 2 teknik pencarian yaitu blind search dan heuristik search.
- Pencarian buta (blind search) adalah pencarian tanpa adanya informasi terkait permasalahan yang akan diselesaikan. Blind search dibagi menjadi 3 yaitu BFS (Breadth First Search), DFS (Depth First Search) dan UCS (Uniform Cost Search).
- Pencarian dengan informasi (heuristik search) pencarian yang memberikan suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi.
Contohnya ada pada drama korea Starup
yaitu ketika dalmi menanyakan jam berapa di San Francisco kepada Yeong-sil.
Contohnya fuzzy logic untuk menyelesaikan masalah yang didalamnya
terdapat ketidak pastian.
- Planning adalah suatu
metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub
masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu,
kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah
solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada di
antara sub masalah.
Contohnya adalah Aplikasi kalender pada android
- Learning adalah sebuah cara memperoleh knowledge yang paling sederhana. Dengan cara ini komputer menyimpan data hasil perhitungan kedalam cache.
Contohnya ada sama ada pada drama korea startup pada scene
di bawah ini
Yeongsil adalah contoh dari learing karna yeongsil dapat memahami
apa yang pengguna tanyakan dan dapat mengetahui apa yang ada di depannya dengan
kamera ponsel.
2. Gambar di bawah 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. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90 km/jam. Bantulah petugas tersebut menemukan rute jalan dengan total waktu tercepat dari S ke G dengan menggunakan Metode A*.
Penyelesaian
:
S =
Titik awal pemadam kebakaran
G =
Lokasi Kebakaran
Pertama cari titik sambung yang
mempunyai nilai paling kecil diantara titik A,B dan C. Cara mencarinya yaitu : f(n)
= g(n) + h(n)
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
S - A
dan S - C mempunyai nilai yang sama yaitu 20,5
Kedua
cari titik sambung yang mempunyai nilai paling kecil diantara A – D dan C – F
F(D)
= g(s)+g(S ke D)+h(D) = 0+(5+14)+5 = 24
F(F)
= g(s)+g(S ke F)+h(F) = 0+(5+12)+5 =22
Nilai C – F lebih kecil dari A – D
Karna
tujuan pemadam kebakaran adalah titik G makan langsung saja ke titik G. Jadi
rute tercepat untuk ke titik G adalah S – C – F – G.
Sumber :
Fatkhan. (n.d.). Teknologi. Retrieved 11 24,
2020, from fatkhan.web.id:
http://fatkhan.web.id/artificial-intelligence-reasoning/
Hikmah, N. (2017, 12 08). Artikel. Retrieved
11 23, 2020, from arafarra17:
https://arafarra17.blogspot.com/2017/12/metode-metode-pencarian-dalam.html
