PEMECAHAN MASALAH (PROBLEM SLOVING)
PENGETAHUAN TEKNOLOGI SISTEM CERDAS
AGEN PEMECAH MASALAH
DOSEN : ESSY MALAYS SARI SAKTI
3KA10
NABILAH AIDAHNANDA GANARI
NPM. 14115887
UNIVERSITAS GUNADARMA
II.1
Agen Pemecah Masalah
Dalam kasus agen penalaran yang paling sederhana tentang apa yang harus dilakukan, tanpa ketidakpastian
dan dengan tujuan yang ingin dicapai. Ini adalah representasi datar (non-hirarkis) atau satu tingkat hierarki.
Agen dapat menentukan bagaimana mencapai tujuannya dengan mencari-cari representasi ruang negara dunia
untuk mendapatkan sesuatu dari keadaan saat ini ke keadaan sasaran. Ini dapat menemukan urutan tindakan
yang akan mencapai tujuannya sebelum harus bertindak di dunia.
Masalah ini dapat diabstraksikan ke masalah matematika untuk menemukan jalur dari simpul awal ke simpul
tujuan dalam grafik terarah. Banyak masalah lain juga dapat dipetakan ke abstraksi ini, jadi ada baiknya
mempertimbangkan tingkat abstraksi ini. Sebagian besar bab ini membahas berbagai algoritma untuk
menemukan jalur semacam itu.
II.2
Pencarian Sebagai Solusi Pemecahan Masalah
Gagasan pencarian ini adalah perhitungan di dalam agen. Berbeda dengan pencarian di dunia, ketika
mungkin harus bertindak di dunia, misalnya, agen yang mencari kuncinya, mengangkat bantal, dan sebagainya.
Hal ini juga berbeda dengan pencarian web, yang melibatkan pencarian informasi. Pencarian dalam bab ini
berarti mencari di representasi internal untuk jalan menuju tujuan.
Gagasan untuk mencari sangat mudah: agen membangun serangkaian solusi parsial potensial untuk
masalah yang dapat diperiksa untuk melihat apakah solusi tersebut benar atau apakah solusi tersebut dapat
mengarah pada solusi. Pencarian dilanjutkan dengan berulang kali memilih solusi parsial, menghentikan jika itu
adalah jalan menuju tujuan, dan sebaliknya memperluasnya dengan satu busur lagi dengan segala cara yang
mungkin.
Pencarian mendasari banyak kecerdasan buatan. Ketika agen diberi masalah, biasanya hanya diberi
deskripsi yang memungkinkannya mengenali solusi, bukan algoritma untuk mengatasinya. Ia harus mencari
solusinya. Adanya masalah NP-complete, dengan cara yang efisien untuk mengenali jawaban namun tidak ada
metode yang efisien untuk menemukannya, mengindikasikan bahwa pencarian adalah, dalam banyak kasus,
merupakan bagian penting dalam memecahkan masalah.
Hal ini sering diyakini bahwa manusia dapat menggunakan intuisi untuk beralih ke solusi untuk masalah yang sulit. Namun, manusia tidak cenderung memecahkan masalah umum; Sebagai gantinya mereka memecahkan beberapa contoh spesifik yang mungkin mereka ketahui lebih banyak daripada ruang pencarian yang mendasarinya. Masalah di mana struktur kecil ada atau di mana strukturnya tidak dapat dikaitkan dengan dunia fisik sangat sulit dihadapi manusia. Adanya kode enkripsi kunci publik, di mana ruang pencariannya jelas dan tes untuk solusi diberikan - yang bagaimanapun manusia tidak memiliki harapan untuk memecahkan dan komputer tidak dapat menyelesaikannya dalam kerangka waktu yang realistis - menunjukkan kesulitan pencarian.
Kesulitan mencari dan fakta bahwa manusia mampu memecahkan beberapa masalah pencarian
secara efisien menunjukkan bahwa agen komputer harus memanfaatkan pengetahuan tentang kasus khusus
untuk membimbing mereka menuju solusi. Pengetahuan tambahan di luar ruang pencarian adalah pengetahuan
heuristik.
II.3
Strategi Pencarian yang Tidak Terbentuk ( uninformed search strategy)
Uninformed Serach, yang juga disebut pencarian buta dan pencarian naif, adalah kelas algoritma
pencarian tujuan umum yang beroperasi secara bruteforce cara. Algoritma ini bisa diaplikasikan ke berbagai
search masalah, tapi karena mereka tidak memperhitungkan masalah targetnya tidak efisien Sebaliknya, metode
pencarian informasi gunakan heuristik untuk memandu pencarian masalah yang ada dan karena itu jauh lebih
efisien.
Masalah menentukan grafik dan sasaran tapi bukan jalur mana yang harus dipilih dari perbatasan.
Ini adalah tugas strategi pencarian. Strategi pencarian menentukan jalur mana yang dipilih dari perbatasan.
Strategi yang berbeda diperoleh dengan memodifikasi bagaimana pemilihan jalur di perbatasan diterapkan.
Bagian ini menyajikan tiga uninformed search strategy yang tidak memperhitungkan lokasi tujuan.
Secara intuitif, algoritma ini mengabaikan ke mana tujuannya sampai mereka menemukan sasaran dan
melaporkan keberhasilan.
1. depth-first search
Strategi pertama adalah depth-first search. Pada depth-first search, frontier bertindak seperti tumpukan
keluar pertama. Unsur ditambahkan ke stack satu per satu. Yang dipilih dan diambil dari perbatasan
setiap saat adalah elemen terakhir yang ditambahkan.
Perhatikan grafik berbentuk pohon. Misalkan simpul awal adalah akar pohon (simpul di bagian atas)
dan nodus dipesan dari kiri ke kanan sehingga tetangga paling kiri ditambahkan ke tumpukan terakhir.
Pada pencarian mendalam-pertama, urutan titik-titik yang diperluas tidak bergantung pada lokasi
tujuan. Lima belas node pertama diperluas diberi nomor agar ekspansi. Simpul yang diarsir adalah
simpul di ujung jalan di perbatasan setelah enam belas langkah pertama.
Perhatikan bagaimana enam node pertama diperluas semuanya dalam satu jalur tunggal. Simpul
keenam tidak memiliki tetangga. Dengan demikian, simpul berikutnya yang diperluas adalah anak
dari nenek moyang terendah dari simpul ini yang memiliki anak yang tidak terekspos.
Menerapkan garis depan sebagai hasil susun dalam jalur yang dikejar secara mendalam pertama -
mencari satu jalan untuk menyelesaikannya sebelum mencoba jalur alternatif. Metode ini dikatakan melibatkan
backtracking: Algoritma memilih alternatif pertama di setiap node, dan menggulung ke alternatif berikutnya saat
ia telah menempuh semua jalur dari seleksi pertama. Beberapa jalur mungkin tak terbatas saat grafik memiliki
siklus atau banyak node, sehingga pencarian mendalam pertama mungkin tidak akan pernah berhenti.
Algoritma ini tidak menentukan urutan tetangga ditambahkan ke tumpukan yang mewakili perbatasan.
Efisiensi algoritma sensitif terhadap pemesanan ini.
2.
Breadth-First Search
Dalam Breadth-First Search, perbatasan diterapkan sebagai antrian FIFO
(first-in, first-out). Dengan demikian, jalur yang dipilih dari perbatasan
adalah yang pertama kali ditambahkan. Pendekatan ini menyiratkan bahwa jalur
dari simpul awal dihasilkan sesuai dengan jumlah busur di jalur. Salah satu
jalur dengan busur paling sedikit dipilih pada setiap tahap.
Perhatikan grafik berbentuk pohon. Misalkan node awal adalah simpul di bagian atas. Dalam pencarian
pertama, seperti pencarian mendalam-pertama, urutan titik-titik perluasan diperluas tidak bergantung
pada lokasi sasaran. Lima belas node pertama diperluas diberi nomor agar ekspansi pada gambar.
Simpul yang diarsir adalah simpul di ujung jalan perbatasan setelah enam belas langkah pertama.
3. Uniform-Cost Search (UCS)
Salah satu keuntungan dari BFS adalah selalu menemukan solusi dangkal. Tapi pertimbangkan tepi yang memiliki
biaya yang terkait dengannya. Solusi paling dangkal
mungkin bukan yang terbaik, dan solusi yang lebih dalam dengan biaya jalur yang dikurangi akanmenjadi lebih
baik Seragam -Cost Search (UCS) bisa diterapkan untuk menemukan jalur dengan biaya paling rendah melalui
grafik dengan mempertahankan sebuah memerintahkan daftar node agar turun biaya. Hal ini memungkinkan kita
untuk mengevaluasi jalur biaya paling sedikit dulu
Contoh grafik di mana memilih jalur biaya terendah untuk simpul pertama (A-> C)
mungkin tidak menghasilkan jalur keseluruhan terbaik melalui grafik (A-> B-> E).
Uniform-Cost Search adalah metode pencarian yang kurang informasi karena tidak ada heuristik sebenarnya
digunakan Algoritma mengukur biaya aktual jalur tanpa mencoba memperkirakannya.
Algoritma untuk UCS menggunakan akumulasi path cost dan priority queue untuk menentukan jalan untuk
mengevaluasi. Antrian prioritas (diurutkan dari biaya paling kecil sampai terbesar) berisi simpul yang akan
dievaluasi. Sebagai Anak node dievaluasi, kami menambahkan biaya mereka ke node dengan agregat jumlah
jalur saat ini Nodus ini kemudian ditambahkan ke antrian, dan kapan Semua anak sudah dievaluasi, antriannya
diurutkan demi naik biaya. Bila elemen pertama dalam antrian prioritas adalah simpul tujuan, maka Solusi terbaik
telah ditemukan.
II.4
Referensi
EBOOK = Jones, M. Tim, ARTIFICIAL
INTELLIGENCE A
Systems Approach, INFINITY SCIENCE PRESS LLC, Hingham, Massachusetts New Delhi. Page. 24
Komentar
Posting Komentar