PENGANTAR
TEKNOLOGI SISTEM CERDAS
BAB 2
PENYELESAIAN MASALAH
STRATEGI PENCARIAN YANG
TIDAK BERBENTUK/UNIFORMED SEARCH STRATEGY
a. Breadth-first
search
Breadth First Search
(BFS) merupakan metode pencarian yang bertujuan untuk memperluas dan memeriksa
semua simpul pada graph atau urutan kombinasi dengan pencarian secara
sistematis melalui setiap solusi.
BFS melakukan pencarian
secara mendalam pada keseluruhan graph atau urutan tanpa memperhatikan tujuan
sehingga menemukan tujuan tersebut. Dan juga,ia tidak menggunakan algoritma
heuristik
Karakteristik BFS,antara
lain…
- Jika
ada solusi, BFS akan menemukannya.
- BFS
akan menemukan solusi dengan jalur terpendek.
- BFS
tidak akan terjebak dalam “looping”.
- BFS
membutuhkan space untuk menyimpan node list antrian dan space yang dibutuhkan
dan mungkin space yang dibutuhkan itu cukup besar.
- Asumsi
:
1.
Ada solusi dalam pohon
2.
Pencarian tree adalah secara terurut.
Contoh BFS
Keterangan :
1. Pada metode
breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu
sebelum mengunjungi node-node pada level n+1.
2. Pencarian
dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian
berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga
ditemukannya solusi.
3. Urutan proses
searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,
Keuntungan BFS :
- Tidak
akan menemui jalan buntu
- Jika
ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada
lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan BFS :
- Membutuhkan
memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
- Membutuhkan
waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi
pada level yang ke-(n+1).
b. Uniform-cost
search
Konsepnya hampir sama
dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level yang paling
rendah sampai yang paling tinggi, sedangkan UCS menggunakan urutan biaya dari
yang paling kecil sampai yang terbesar.
UCS berusaha menemukan
solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul
asal menuju ke simpul tujuan.
c. Depth-first
search
Proses searching
sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian
masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti
sebuah path tunggal sampai menemukan goal atau dead
end.
Apabila proses searching
menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk
melihat apakah node tersebut memiliki path cabang yang belum
dieksplorasi. Apabila cabang ditemukan, DFS akan melakukan cabang
tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan
kembali ke node parent dan melakukan proses searching terhadap
cabang yang belum dieksplorasi dari node parent sampai
menemukan penyelesaian masalah.
Kelebihan DFS ,antara
lain..
- Pemakaian
memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node
yang pernah dibangkitkan.
- Jika
solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan
menemukannya secara cepat.
Kelemahan DFS,antara
lain…
- Jika
pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak
ada jaminan untuk menemukan solusi (Tidak Complete).
- Jika
terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal).
Urutan proses searching DFS
ditunjukkan dalam Gambar 1.5 adalah: A, B, E, F, G, C, ...
d. Depth-limited
search
Metode ini berusaha
mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan maksimum
dari suatu jalur solusi. Tetapi, sebelum menggunakan DLS, kita harus tahu
berapa level maksimum dari suatu solusi.
e. Iterative
Deepening Depth-first search
IDS merupakan metode yang
menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS
(space complexity rendah atau membutuhkan sedikit memori). Tetapi
konsekuensinya yaitu time complexity nya menjadi tinggi.
Disebut juga sebagai
sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree
search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini
dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan
seterusnya sampai goal sudah ditemukan.
f. Bidirectional
search
Pencarian dilakukan dari
dua arah : pencarian maju (dari start ke goal) dan
pencarian mundur (dari goal ke start). Ketika dua
arah pencarian telah membangkitkan simpul yang sama, maka solusi telah
ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.
Agen Pemecah Permasalahan
Terbagi menjadi 3 ,antara
lain…
i. Goal-Based
Agent
Mempertimbangkan
action-action yang akan datang dan hasil yang ingin dicapai.
ii. Problem
Solving Agent
Menemukan sequence action
untuk mencapai tujuannya.
iii. Algorithm
are uninformed
Tidak ada informasi untuk
Problem, hanya deskripsi pada masalah tersebut
Pencarian sebagai solusi
pemecahan masalah
Didefinisikan sebagai
suatu teknik penyelesaian masalah dengan cara merepresentasikan masalah ke
dalam state dan ruang masalah serta menggunakan strategi pencarian untuk
menemukan solusi.
Langkah-langkah dalam teknik searching,antara lain…
1. Mendefinisikan ruang masalah/ruang keadaan untuk suatu
masalah yg dihadapi.
2. Mendefinisikan aturan produksi yang digunakan untuk mengubah
suatu “state” ke “state” lainnya. Aturan
produksi adalah operasi yg mengubah suatu state ke state lainnya.
3. Memilih metode pencarian yg tepat sehingga dapat
menemukan solusi terbaik dengan usaha yang minimal.
Untuk mengukur
performansi metode pencarian, terdapat 4 kriteria yang digunakan…
- Completeness
Apakah metode tersebut
menjamin penemuan solusi jika solusinya memang ada?
- Time
complexity
Berapa lama waktu yang
diperlukan ?
- Space
complexity
Berapa banyak memori yang
diperlukan ?
- Optimality
Apakah metode tersebut
menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang
berbeda ?
Proses searching ini
berupa jalur yang menggambarkan keadaan awal sebuah masalah menuju kepada
penyelesaian masalah yang diinginkan (i.e., the solved problem)
Metoda searching pada
kecerdasan buatan merupakan searching terhadap problem space bukan searching data
(e.g., angka, karakter, string) tertentu
Sumber :
viska.web.id/wp-content/uploads/2012/03/Modul-Pertemuan-2-7.pdf
ocw.upj.ac.id/files/Slide-INF401-KECERDASAN-BUATAN-PERTEMUAN-3.pptx
https://pakeklinux.files.wordpress.com/2010/.../pertemuan-3-masalah-ruang-masalah.ppt
Tidak ada komentar:
Posting Komentar