penyelesaian masalah searching -...
TRANSCRIPT
PENYELESAIAN MASALAH
:SEARCHING
PROBLEM SOLVING AGENT
• Agen penyelesaian masalah memutuskan apa yang harusdilakukan dengan menemukan urutan tindakan yang mengarahke keadaan yang diinginkan. Agen dapat merumuskanpandangan yang tepat dari masalah yang dihadapinya.
• Jenis masalah yang dihasilkan dari proses formulasi akanbergantung pada pengetahuan yang tersedia untuk agen:apakah agen mengetahui keadaan saat ini dan hasil daritindakan.
• Sebelum agen dapat mulai mencari solusi, harus dirumuskantujuan dan kemudian menggunakan tujuan tersebut untukmerumuskan masalah.
PROBLEM SOLVING AGENT
• Agen yang cerdas seharusnya bertindak sedemikian rupasehingga lingkungan berjalan melalui urutan keadaan yangmemaksimalkan ukuran kinerja. Tugasnya adalah agen dapatmengetahui tujuan dan bertujuan untuk melakukannya denganbaik dan benar.
• Goal formulation adalah langkah pertama dalam pemecahanmasalah. Bersamaan dengan merumuskan tujuan, agen mungkiningin memutuskan beberapa faktor lain yang mempengaruhikeinginan dengan berbagai cara untuk mencapai tujuan.
PROBLEM SOLVING AGENT
• Actions dapat dilihat sebagai penyebab transisi antara states. Agenharus mencari tahu tindakan yang akan membawanya ke goal state.Sebelum bisa melakukan ini, perlu diputuskan actions dan statesapa yang harus dipertimbangkan.
• Problem formulation adalah proses memutuskan actions dan statesapa yang perlu dipertimbangkan, dan mengikuti goal formulation.
• Proses mencari urutan seperti ini disebut search. Algoritmapencarian mengambil masalah sebagai input dan mengembalikansolusi dalam bentuk urutan action.
• Setelah ditemukan solusi, action yang disarankan dapat dilakukan.Hal ini disebut execution phase.
DEFINISI MASALAH
• Masalah terdiri dari empat bagian: initial state, a set ofoperators, goal test, dan a path cost.
• Initial State - State awal dari suatu masalah.
• Set of operators - Kumpulan kemungkinan tindakan yangtersedia untuk agen.
• Goal Test - Menguji apakah deskripsi state sesuai dengangoal state.
• Path Cost - Jumlah biaya dari tindakan sepanjang path.
DEFINISI MASALAH
• State space dari masalah adalah himpunansemua state yang dapat dijangkau dari initialstate oleh setiap urutan tindakan.
• Path pada state space adalah urutan tindakanyang mengarah dari satu state ke state lain.
• Jalur yang melalui state space dari initial state kegoal state adalah solusi.
STRATEGI PENCARIAN
• Terdapat 5 strategi pencarian yang termasuk dalamuninformed search, yaitu Breadth-first search, Uniform-cost search, Depth-first search, Depth-limited search, danIterative deepening search.
• Uninformed search dapat juga disebut dengan blindsearch.
• Istilah tersebut berarti bahwa tidak memiliki informasitentang jumlah langkah atau path cost dari keadaan saatini ke tujuan (goal), yang dapat dilakukan hanyalahmembedakan goal state dari non-goal state.
STRATEGI PENCARIAN
• Breadth-first search memperluas node yang paling dangkal disearch tree terlebih dahulu. Semua node pada depth d disearch tree diperluas sebelum node pada depth d + 1.
• Uniform-cost search memperluas node leaf dengan costpaling kecil terlebih dahulu. Strategi ini memodifikasi strategibreadth-first search dengan selalu memperluas node biayaterendah di pinggiran (yang diukur dengan path cost)daripada node terendah-mendalam.
STRATEGI PENCARIAN
• Depth-first search memperluas node terdalam di search tree terlebihdahulu. Hanya ketika pencarian mencapai jalan buntu (node non-goaltanpa ekspansi), pencarian akan kembali dan memperluas node padalevel yang lebih dangkal.
• Depth-limited search menempatkan batas pada seberapa dalam depthpencarian dapat dilakukan. Langkah ini dapat diimplementasikandengan algoritma pencarian khusus depth-limited atau denganmenggunakan algoritma pencarian umum dengan operator yangmelacak depth.
• Iterative deepening search disebut dengan depth-limited searchdengan peningkatan batas hingga goal ditemukan. Pencarian inimenghindari masalah memilih batas depth terbaik dengan mencobasemua batas depth yang mungkin: depth pertama 0, lalu depth 1, laludepth 2, dan seterusnya.
BREADTH-FIRST SEARCH
BREADTH-FIRST SEARCH
UNIFORM COST SEARCH
UNIFORM COST SEARCH
DEPTH-FIRST SEARCH
DEPTH-LIMITED SEARCH
ITERATIVE DEEPENING SEARCH
ITERATIVE DEEPENING SEARCH
ITERATIVE DEEPENING SEARCH
ITERATIVE DEEPENING SEARCH
STRATEGI PENCARIAN
Empat kategori dalam penentuan strategi pencarian dalammemecahkan masalah :
• Completeness: Apakah strategi dapat menjamin untuk menemukan solusi ketika ada?
• Time complexity: Berapa lama waktu yang dibutuhkanuntuk menemukan solusi?
• Space complexity: Berapa banyak memori yang dibutuhkan untuk melakukan pencarian?
• Optimality: Apakah strategi menemukan solusi berkualitas tinggi ketika ada beberapa solusi yang berbeda?
PERBANDINGAN STRATEGI PENCARIAN