2.state space search
Post on 02-Aug-2015
126 Views
Preview:
TRANSCRIPT
Artificial Intellegence
Lecture 2 State Space Solution Search(BFS dan DFS)
Joan Santoso, S.Kom.
© Sekolah Tinggi Teknik Surabaya
1
State Space Search» Search dapat diaplikasikan pada
beberapa problem , contoh :˃ Menyelesaikan puzzle˃ Shortest path dari sebuah peta˃ Mencari jalan dalam sebuah maze atau
labirin» State space search adalah sebuah
proses didalam computer science, untuk mencari sebuah state atau konfigurasi menuju ke goal state. 2
© Sekolah Tinggi Teknik Surabaya
State Space Search» Banyak permasalahan dapat
direpresentasikan ke dalam bentuk state.
» Tetapi problem nya adalah bagaimana mencapai goal atau tujuan dari sebuah start yang diberikan.
» Sebuah search problem dalam state space dapat direpresentasikan dengan STATE-SPACE Graph/Tree dimana node yang adalah states dan vertexnya adalah langkah menuju ke state tersebut.
3
© Sekolah Tinggi Teknik Surabaya
State Space Search
4
© Sekolah Tinggi Teknik Surabaya
Contoh dari state space tree
State Space Search» Sebuah State-space graph biasanya yang
menjadi root adalah starting state dan yang menjadi leaf terakhir adalah solusi dari problem kita.
» Seluruh strategi search pada State space jika kita telusuri pada state space tree dapat kita lihat :˃ Sebuah node akan diexpand jika kita telah
menggenerated semua succesorrnya˃ Sebuah node akan dieksplorasi jika kita telah
menggenerate beberapa successornya˃ Sebuah node akan digenerated jika kita berhasil
mencapai node tersebut.
5
© Sekolah Tinggi Teknik Surabaya
State Space Search» State space dapat direpresentasikan
menjadi 4 pasang, yaitu : N,A, S, GD» Dimana :
˃ N adalah sekumpulan node atau state dari graph.
˃ A adalah vertex atau proses atau langkah dari sebuah node/state ke state yang lain.
˃ S adalah Starting State˃ GD adalah Goal State
6
© Sekolah Tinggi Teknik Surabaya
Metode State Space Search» Metode pencarian dalam State Space
Search dibagi menjadi 2 macam, yaitu :˃ Pencarian tanpa informasi (Blind Search)
+ Breadth First Search+ Depth First Search+ Uniform Cost Searcch
˃ Pencarian heuristik (Informed/Heuristic Search)
+ Best First Search+ Optimum A*
7
© Sekolah Tinggi Teknik Surabaya
Perfomansi State Space Search» Untuk mengukur perfomansi pencarian
terdapat 4 kriteria yang digunakan menurut Stuart Russel dan Peter Norvig, yaitu:˃ Completeness : Solusi ditemukan ?˃ Time Complexity : Waktu ?˃ Space Complexity : Memori ?˃ Optimality : Solusi terbaik ?
8
© Sekolah Tinggi Teknik Surabaya
Problem dalam State Space Search» Eight Puzzle
9
© Sekolah Tinggi Teknik Surabaya
Problem dalam State Space Search» Missionaris and Canibal
10
© Sekolah Tinggi Teknik Surabaya
Problem dalam State Space Search» Traveling Salesman Proble
11
© Sekolah Tinggi Teknik Surabaya
Algoritma DFS
12
© Sekolah Tinggi Teknik Surabaya
Algoritma BFS
13
© Sekolah Tinggi Teknik Surabaya
BFS VS DFS» BFS
˃ BFS selalu mencari shortest path menuju ke goal
˃ Sangat efficient jika solusi ditemukan pada kedalaman yang pendek
˃ Tidak efficient jika solusi berada pada kedalaman yang dalam.
» DFS ˃ Dapat terperangkap di dalam tree˃ Lebih effisien jika solusi berada di dalam
kedalaman tree» Siapa yang lebih baik ?
14
© Sekolah Tinggi Teknik Surabaya
Terima Kasih + Latihan
15
© Sekolah Tinggi Teknik Surabaya
Referensi» Bahan Kuliah Artificial Intelgence STTS yang dibuat oleh Ir.
Gunawan, M.Kom. » Slide AI “State Space Solution Search” University of
Victoria CENG 420.» http://en.Wikipedia.org/wiki/State_space_search» http://www.cis.temple.edu/~giorgio/cis587/readings/sear
ch.html» http://www.cs.trincoll.edu/~ram/cpsc352/notes/search.ht
ml» AIMA Slides, (C) Stuart Russel and Peter Norvig, 1998» Rajjan Shinghal. 1992.“Formal Concepts in Artificial
Intellegence”. Chapman & Hall» Suyanto, ST, MSC., 2007, “Artificial Intelligence Searching-
Reasoning-Planning-Learning”, Informatika:Bandung. 16
© Sekolah Tinggi Teknik Surabaya
top related