Teknik Informatika
SEARCHING Politeknik Negeri
Indramayu
REFERENSI
Materi kuliah IF3170 Inteligensi Buatan Teknik Informatika ITB, Rinaldi
Munir
Materi kuliah Inteligensi Buatan Polindra, Adi Suheryadi
Stuart J Russell & Peter Norvig, Artificial Intelligence: A Modern
Approach, 3rd Edition, Prentice-Hall International, Inc, 2010, Textbook
Site: [Link] (2nd edition)
Free online course materials | MIT OpenCourseWare Website: Site:
[Link]
Lecture Notes in Informed Heuristic Search, ICS 271 Fall 2008,
[Link]
dechter/courses/ics-271/fall08/lecture-notes/[Link].
ppt
OVERVIEW
Merupakan algoritma untuk mencari kemungkinan
penyelesaian
Sering dijumpai pada penelitian bidang AI
Metode sederhana dari searching, hanya mencari
kemungkinan penyelesaian
Contoh : dept-first search, hill climbing, breath-first search,
dll
Metode lebih komplek mencari jarak terpendek
Contoh A*, Branch and bound, Dynamic Programming
SKEMA METODE SEARCHING
UKURAN PERFORMANSI
Completeness
Apakah metode tersebut menjamin penemuan solusi jika
solusinya memang ada?
Optimality
Apakah metode tersebut menjamin menemukan solusi yang
terbaik jika terdapat beberapa solusi berbeda?
Time complexity
Berapa lama waktu yang diperlukan?
Space complexity
Berapa banyak memori yang diperlukan?
WHAT ARE WE LEARNING
TODAY?
1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Best First Search (BFS)
4. Greedy Best First Search
5. A*
ALGORITMA PENCARIAN
Tanpa informasi (uninformed/blind search)
Tidak ada informasi tambahan
Contoh: DFS, BFS, Depth Limited Search, Iterative Deepening
Search, Uniform Cost Search
Dengan informasi (informed Search)
Pencarian berbasis heuristik
Mengetahui non-goal state “lebih menjanjikan” daripada yang
lain
Contoh: Best First Search, A*, Greedy Best First Search
UNINFORMED SEARCH
BREADTH-FIRST SEARCH
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
KELEBIHAN BFS
Tidak akan menemui jalan buntu
Jika ada satu solusi, maka BFS 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 ke-(n+1)
LATIHAN
Jika kita hendak berkunjung dari kota
1 ke kota 8, maka dengan
menggunakan Algoritma BFS, urutan
kota yang akan dihasilkan adalah:
JAWABAN:
1–2–3–4–5–6–7–8
DEPTH-FIRST SEARCH
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17 G 25
KELEBIHAN DFS
Membutuhkan memori yang relatif kecil, karena
hanya node-node pada lintasan yang aktif saja
yang disimpan.
Secara kebetulan, metode DFS akan menemukan
solusi tanpa harus menguji lebih banyak lagi dalam
ruang keadaan.
KELEMAHAN DFS
Memungkinkan tidak ditemukan tujuan yang
diharapkan
Hanya akan mendapatkan 1 solusi pada setiap
pencarian
LATIHAN
Jika kita hendak berkunjung dari kota
1 ke kota 8, maka dengan
menggunakan Algoritma DFS, urutan
kota yang akan dihasilkan adalah:
JAWABAN:
1–2–4–8–5–6–3–7
INFORMED SEARCH
BEST FIRST SEARCH
Utamakan nilai
yang
terkecil/terbesar
(Tergantung fungsi
optimal yang
ditetapkan
sebelumnya)
Tentukan rute terpendek
dari S ke I
Jawaban:
S–A–C–B–D–I
GREEDY BEST-FIRST SEARCH
Ide: menggunakan rumus/formula/fungsi f(n) untuk setiap node
f(n) = h(n) estimasi cost yang akan diperoleh dari n menuju
tujuan
Greedy best-first search
memperluas node yang
kemungkinan besar
mendekati tujuan awal
KEKURANGAN
Terdapat kemungkinan terjebak di Local Minima
Tidak dapat berbalik/berubah
ALGORITMA A*
Ide: menghindari path yang kemungkinan besar tidak efektif
Fungsi f(n) = g(n) + h(n)
g(n) = cost sejauh ini untuk mencapai n
h(n) = estimasi cost dari n ke tujuan
f(n) = estimasi total cost dari n ke tujuan
INSPIRASI TOPIK TA
[Link]
INSPIRASI TOPIK TA
[Link]
INSPIRASI TOPIK TA
[Link]