IKI30320 Kuliah 4 5 Sep Ruli Manurung. Ulasan. Breadth-first. Uniform-cost. Depth-first. Pengulangan state. Ringkasan

Outline IKI30320 Kuliah 4 5 Sep 2007

IKI30320 Kuliah 4 5 Sep 2007

Ruli Manurung

Ruli Manurung

Ulasan Breadth-first Uniform-cost

IKI 30320: Sistem Cerdas Kuliah 4: Uninformed Search Strategies (Rev.)

Ulasan

Uniform-cost Depth-first

Iterativedeepening

Iterativedeepening

Ruli Manurung

Ringkasan

Pengulangan state

Fakultas Ilmu Komputer Universitas Indonesia

Problem-solving agent & search

Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state


Goal & problem formulation: masalah dinyatakan sebagai sebuah state space, yang sering direpresentasikan dalam bentuk graph. Action adalah abstraksi tindakan yang dapat diambil State adalah abstraksi keadaan yang dapat terjadi

Ruli Manurung

Solution search: solusi diperoleh dengan mencari rangkaian tindakan (action sequence) yang membawa agent ke goal state.

Uniform-cost

Ulasan Breadth-first

Pengulangan state

Arad

Ringkasan

Ringkasan

Fagaras

Timisoara

Oradea

Rimnicu Vilcea

Arad

Zerind

Lugoj

3

Uniform-cost

4

Depth-first

5

Iterative-deepening

6

Pengulangan state

7

Ringkasan

Arad

Oradea

1

Pada awalnya, fringe = himpunan node yang mewakili initial state.

2

Pilih satu node dari fringe sebagai current node (Kalau fringe kosong, selesai dengan gagal).

3

Jika node tsb. lolos goal test, selesai dengan sukses!

4

Jika tidak, lakukan node expansion terhadap current node tsb. Tambahkan semua node yang dihasilkan ke fringe.

5

Ulangi langkah 2.

Depth-first Iterativedeepening

Proses pencarian solusi sebagai search tree

Arad

Breadth-first

Algoritma penelusuran search tree

Sebuah problem-solving agent memecahkan sebuah masalah dalam 2 tahap:

Sibiu

2

Ringkasan

5 September 2007


Ulasan

Breadth-first

Depth-first

Pengulangan state

1

function T REE S EARCH (problem, fringe) returns solution or failure fringe ← I NSERT(M AKE N ODE(I NITIAL S TATE(problem)),fringe) loop do if E MPTY?(fringe) then return failure node ← R EMOVE F IRST(fringe) if G OALT EST(problem) applied to S TATE(node) succeeds then return S OLUTION(node) fringe ← I NSERTA LL(E XPAND(node,problem),fringe)

Strategi pencarian IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Uninformed search strategies

Terdapat berbagai jenis strategi untuk melakukan search. Semua strategi ini berbeda dalam satu hal: urutan dari node expansion. Search strategy di-evaluasi berdasarkan: completeness: apakah solusi (jika ada) pasti ditemukan? time complexity: jumlah node yang di-generate. space complexity: jumlah maksimum node di dalam memory. optimality: apakah solusi dengan minimum cost pasti ditemukan?

IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Time & space complexity diukur berdasarkan b - branching factor dari search tree d - depth (kedalaman) dari solusi optimal m - kedalaman maksimum dari search tree (bisa infinite!)

Breadth-first search IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung

Uniform-cost Depth-first Iterativedeepening

Bisa diterapkan secara generik terhadap semua jenis masalah yang bisa direpresentasikan dalam sebuah state space. Ada beberapa jenis: Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative-deepening search

Sifat breadth-first search IKI30320 Kuliah 4 5 Sep 2007

Prinsip algoritma breadth-first search Lakukan node expansion terhadap node di fringe yang paling dekat ke root.


Uninformed strategy hanya menggunakan informasi dari definisi masalah.

Ruli Manurung Ulasan

Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang

Pengulangan state

Uniform-cost Depth-first Iterativedeepening Pengulangan state

A

Ringkasan

Breadth-first

Complete? Ya, jika b terbatas Time complexity? b + b2 + b3 + . . . + bd + b(bd − 1) = O(bd+1 ) → eksponensial dlm. d. Space complexity? O(bd+1 ), karena semua node yang di-generate harus disimpan. Optimal? Ya, jika semua step cost sama, tapi pada umumnya tidak optimal.

Ringkasan

Masalah utama breadth-first search adalah space B D

C E

F

G

Mis: 1 node memakan 1000 byte, dan b = 10 Jika d = 6, ada 107 node ≈ 10 gigabyte. Jika d = 12, ada 1013 node ≈ 10 petabyte!

Uniform-cost search

Sifat uniform-cost search

IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan Breadth-first


Prinsip algoritma uniform-cost search

Ruli Manurung

Lakukan node expansion terhadap node di fringe yang path cost-nya paling kecil.

Uniform-cost

Ulasan Breadth-first Uniform-cost

Depth-first

Implementasi: fringe adalah sebuah priority queue di mana node disortir berdasarkan path cost function g(n).

Iterativedeepening Pengulangan state

Jika semua step cost sama, uniform-cost sama dengan breadth-first.

Ringkasan

Depth-first Iterativedeepening Pengulangan state Ringkasan

Complete? Ya, jika step cost ≥ untuk > 0 Time complexity? Jumlah node dengan ∗ g(n) ≤ C ∗ = O(bbC /c+1 ) di mana C ∗ adalah cost dari optimal solution Space complexity? Semua node yang di-generate ∗ harus disimpan ≈ O(bbC /c+1 ) Optimal? Ya, karena urutan node expansion dilakukan urut g(n).

Bandingkan dengan shortest-path algorithm-nya Dijkstra!

Contoh uniform-cost search IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung

Depth-first search

Coba gunakan uniform-cost search untuk mencari optimal solution dari Arad ke Bucharest!

IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung

Oradea

71

Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

75

Neamt

Zerind

Breadth-first

Iasi

Arad

140 Sibiu

111

Lugoj

Pengulangan state

Pitesti

97

142

211

70

98

75 Dobreta

146

85

101

Implementasi: fringe adalah sebuah stack , data struktur LIFO (Last In First Out) Hasil node expansion ditaruh di depan Depth-first search sangat cocok diimplementasikan secara rekursif.

Ringkasan

A

Hirsova

B

Urziceni

C

86

138

Bucharest

120 Craiova

Iterativedeepening

Vaslui

80 Rimnicu Vilcea

Mehadia

Depth-first

Fagaras

118 Timisoara

Uniform-cost

92 99

Lakukan node expansion terhadap node di fringe yang paling jauh dari root.

Ulasan

87

151

Prinsip algoritma depth-first search

D

90 Giurgiu

E

F

G

Eforie

H

I

J

K

L

M

N

O

Sifat depth-first search IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Variasi depth-first search IKI30320 Kuliah 4 5 Sep 2007

Complete? Tidak, bisa gagal jika m tak terbatas, atau state space dengan loop.

Ruli Manurung

Time complexity? O(bm ) → jika m d, parah!

Breadth-first

Space complexity? O(bm) → linear space! Optimal? Tidak. Depth-first search mengatasi masalah space Mis: 1 node memakan 1000 byte, dan b = 10 Jika d = 12, space yang dibutuhkan hanya 118 kilobyte . . . bandingkan dengan 10 petabyte!

Ulasan

Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan


function R ECURSIVE DLS (node, problem, limit) returns solution or failure/cutoff cutoff _occurred? ← false if G OALT EST[problem](S TATE[node]) then return S OLUTION(node) else if D EPTH[node] = limit then return cutoff else for each successor in E XPAND(node,problem) do result ← R ECURSIVE DLS(successor ,problem,limit) if result = cutoff then cutoff _occurred? → true else if result 6= failure then return result if cutoff _occurred? then return cutoff else return failure function D EPTH L IMITED S EARCH (problem, limit) returns solution or failure/cutoff return R ECURSIVE DLS(M AKE N ODE (I NITIAL S TATE[problem]), problem, limit)

Perhatikan perbedaan antara cutoff dan failure.

Mengatasi masalah untuk state space tak terbatas. Sayangnya, ada unsur incompleteness baru, jika ` < d. Biasanya d tidak diketahui (tapi bisa ada estimasi, mis. diameter suatu graph).

Iterative-deepening search

Implementasi rekursif depth-limited search IKI30320 Kuliah 4 5 Sep 2007

Backtracking search: lakukan node expansion satu-per-satu. Jika gagal backtrack dan coba nilai successor function yang lain. Depth-limited search: Batasi kedalaman maksimal yang dilihat adalah `.

Ruli Manurung Ulasan

Prinsip algoritma iterative-deepening search Lakukan depth-limited search secara bertahap dengan nilai ` yang incremental.

Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state

Strategi ini menggabungkan manfaat depth dan breadth first: space complexity linier dan completeness terjamin! Lakukan depth-limited search dengan ` = 0, 1, 2, . . . sampai tidak cutoff .

Ringkasan

function I TERATIVE D EEPENING S EARCH (problem) returns solution or failure for depth → 0 to ∞ do result → D EPTH L IMITED S EARCH(problem, depth) if result 6= cutoff then return result

Contoh iterative-deepening search


IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan


`=0

Ruli Manurung

Limit = 0

A

A

Ulasan

Breadth-first

Breadth-first

Uniform-cost

Uniform-cost

Depth-first

Depth-first

Iterativedeepening

Iterativedeepening

Pengulangan state

Pengulangan state

Ringkasan

Ringkasan


Ulasan

A

`=2

Ruli Manurung

Limit = 2

A

A

B D

C E

F

A

B G

D

C E

F

A

B G

D

C E

F

Ulasan

B G

D

C

C

E

F

A

A

B D

C E

F

A

B G

D

C E

F

A

B G

D

C E

F

C

A

B

C

B

C

D

A C

D H

E J

I

L

K

N

C

D

G M

A

B

F

O

H

E I

J

G N

M

L

K

A

B

F

C

D O

H

E I

J

B

F

G N

M

L

K

F

A

A

C E

A

B

C

D O

H

E I

J

F

G N

M

L

K

O

Depth-first

B G

Limit = 3

G

Uniform-cost

Depth-first

G

Iterativedeepening

B

Pengulangan state

H

E I

J

F N

C

D

G M

L

K

O

H

E I

J

H

C E

I

J

O

H

E I

J

L

G M

N

C

D O

H

E I

J

N

M

L

K

G

C

D O

H

E I

J

F

L

G M

N

C

D O

H

E I

J

B

F K

G N

M

L

K

O

A

B

F K

B

F

A

B

F K

N

C

D

A

B D

G M

L

K

A

B

F

A

Ringkasan

A

B

C

D

Ringkasan

A

B

`=3

Breadth-first

Uniform-cost

Pengulangan state

A

B


Breadth-first

Iterativedeepening

Limit = 1


IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung

`=1

L

G M

N

C

D O

H

E I

J

F K

L

G M

N

O

Kinerja iterative-deepening search

Sifat iterative-deepening search IKI30320 Kuliah 4 5 Sep 2007


Ruli Manurung

Ruli Manurung

Ulasan

Secara sekilas, strategi ini kelihatan tidak efisien, atau boros: banyak usaha terulang!

Ulasan

Breadth-first

Complete? Ya.

Breadth-first

Iterative-deepening search malah lebih cepat dari breadth-first search!

Uniform-cost

Time complexity? db1 + (d − 1)b2 + . . . + bd = O(bd )

Uniform-cost

N(IDS) = db + (d − 1)b2 + . . . + (1)bd N(BFS) = b + b2 + . . . + bd + (bd+1 − b)


Depth-first

Space complexity? O(bd) Optimal? Ya, jika semua step cost sama. Bisa dimodifikasi spt. uniform-cost tree, namanya iterative lengthening search.

Iterativedeepening

Untuk b = 10 dan d = 5:

Pengulangan state

N(IDS) = 50 + 400 + 3, 000 + 20, 000 + 100, 000 = 123, 450 N(BFS) = 10+100+1, 000+10, 000+100, 000+999, 990 = 1, 111, 100.

Ringkasan

Pada umumnya, iterative deepening search adalah uninformed search strategy yang terbaik jika state space besar dan kedalaman solusi (d) tidak diketahui.

Masalah: state yang mengulang di dalam search tree

Perbandingan strategi pencarian IKI30320 Kuliah 4 5 Sep 2007


Ruli Manurung

Ruli Manurung


Ulasan

Criterion

Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Kegagalan menangani state yang mengulang dapat membuat masalah linier menjadi eksponensial!

Complete? Time Space Optimal?

BreadthFirst Ya∗ bd+1 bd+1 Ya∗

UniformCost Ya∗ bC ∗ /c+1 b ∗ bbC /c+1 Ya∗

DepthFirst Tidak bm bm Tidak

DepthLimited Ya, jk ` ≥ d b` b` Tidak

Iterative Deepening Ya bd bd Ya

Breadth-first

A

A

Uniform-cost Depth-first

B

B

B

Iterativedeepening Pengulangan state

C

C

C

C

Ringkasan

D

Ingat dua variasi definisi masalah 8-queens problem.

C

Solusi: belajar dari sejarah

Algoritma G RAPH S EARCH



Ruli Manurung

Ruli Manurung

function G RAPH S EARCH (problem, fringe) returns solution or failure Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Algorithms that forget their history are doomed to repeat it... Solusinya adalah untuk mencatat state mana yang sudah pernah dicoba. Catatan ini disebut closed list (fringe = open list). Modifikasi algoritma T REE S EARCH dengan closed list menjadi G RAPH S EARCH.

Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan

Ringkasan

Sifat G RAPH S EARCH IKI30320 Kuliah 4 5 Sep 2007 Ruli Manurung Ulasan Breadth-first Uniform-cost Depth-first Iterativedeepening Pengulangan state Ringkasan


Time complexity: sama, jika kita asumsi operasi S TATE[node] ∈ / closed = O(1) (implementasi dengan hashtable?)

Ruli Manurung

Space complexity: DFS dan IDS tidak lagi linier! G RAPH S EARCH tidak mencatat path menuju suatu state. Ini mempengaruhi sifat optimality suatu strategi:

Uniform-cost

Uniform-cost dan breadth-first search dengan step cost konstanta masih optimal (kenapa?). Untuk variasi Depth-first dan iterative-deepening search, jika state mengulang ditemukan, periksa apakah path cost-nya lebih kecil → update info node dan anak-anaknya!

closed ← {} fringe ← I NSERT(M AKE N ODE(I NITIAL S TATE(problem)),fringe) loop do if E MPTY?(fringe) then return failure node ← R EMOVE F IRST(fringe) if G OALT EST(problem) applied to S TATE(node) succeeds then return S OLUTION(node) if S TATE[node] ∈ / closed then add S TATE[node] to closed fringe ← I NSERTA LL(E XPAND(node,problem),fringe)



Breadth-first search: completeness terjamin, tapi rakus memory. Uniform-cost search: mirip BFS, optimality terjamin jika cost path ≥ untuk > 0. Depth-first search: Space complexity linier, tetapi tidak complete (maupun optimal). Depth-limited search: mirip DFS, tetapi kedalaman search dibatasi sampai `. Iterative-deepening search: lakukan DLS secara bertahap dengan ` = 0, 1, 2, . . .. Pengulangan state bisa dihindari dengan mencatat state yang sudah pernah dicoba. T REE S EARCH → G RAPH S EARCH.

IKI30320 Kuliah 4 5 Sep Ruli Manurung. Ulasan. Breadth-first. Uniform-cost. Depth-first. Pengulangan state. Ringkasan

Recommend Documents