kecerdasan buatan (artificial intelligence)

KECERDASAN BUATANKECERDASAN BUATAN(ARTIFICIAL INTELLIGENCE)(ARTIFICIAL INTELLIGENCE)

PERTEMUAN 3PERTEMUAN 3MASALAH, RUANG KEADAAN DAN PENCARIAN 1MASALAH, RUANG KEADAAN DAN PENCARIAN 1

Metode PencarianMetode Pencarian Terdapat banyak metode yang telah diusulkan.Terdapat banyak metode yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam 2 jenis :Semua metode yang ada dapat dibedakan ke dalam 2 jenis :

1. Pencarian buta / tanpa informasi (1. Pencarian buta / tanpa informasi (blind / un-informed blind / un-informed searchsearch))

2. Pencarian heuristik / dengan informasi (2. Pencarian heuristik / dengan informasi (heuristicheuristic atau atau informed searchinformed search))

setiap metode mempunyai karakteristik yang berbeda-beda setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangan masing-masing.dengan kelebihan dan kekurangan masing-masing.

4 Kriteria mengukur performansi4 Kriteria mengukur performansi

1. Completeness : 1. Completeness : Apakah metode tersebut menjamin penemuan solusi Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?jika solusinya memang ada?

2. Time complexity : 2. Time complexity : Berapa lama waktu yang diperlukan ?Berapa lama waktu yang diperlukan ?

3. Space complexity : 3. Space complexity : Berapa banyak memori yang diperlukan ?Berapa banyak memori yang diperlukan ?

4. Optimality : 4. Optimality : Apakah metode tersebut menjamin menemukan solusi Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang yang terbaik jika terdapat beberapa solusi yang berbeda ?berbeda ?

Heuristic Searching Heuristic Searching Sebagai Dasar dari Kecerdasan BuatanSebagai Dasar dari Kecerdasan Buatan

Para peneliti awal kecerdasan buatan menitik beratkan Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaian masalah yang tidak menggunakan pada penyelesaian masalah yang tidak menggunakan metoda komputasi konvensional.metoda komputasi konvensional.

Hal ini disebabkan metoda pemecahan masalah Hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan.konvensional tidak dapat lagi digunakan.

Permasalahan pada sistem KB tidak memiliki algoritma Permasalahan pada sistem KB tidak memiliki algoritma tertentu. Kalaupun ada tentulah sangat kompleks.tertentu. Kalaupun ada tentulah sangat kompleks.

Karena itu haruslah ditemukan sebuah teknik baru yang Karena itu haruslah ditemukan sebuah teknik baru yang mirip dengan cara yang digunakan oleh manusia untuk mirip dengan cara yang digunakan oleh manusia untuk menyelesaikan masalah dan dapat diimplementasikan pada menyelesaikan masalah dan dapat diimplementasikan pada komputer. komputer.

Salah satu metoda yang cukup terkenal adalah Salah satu metoda yang cukup terkenal adalah metoda metoda searchingsearching..

Searching dalam sebuah struktur data telah Searching dalam sebuah struktur data telah menjadi dasar bagi algoritma komputer, tetapi menjadi dasar bagi algoritma komputer, tetapi proses searching pada KB memiliki perbedaan.proses searching pada KB memiliki perbedaan.

Metoda searching pada KB merupakan searching Metoda searching pada KB merupakan searching terhadap terhadap problem space problem space bukan searching data bukan searching data (e.g., angka, karakter, string) tertentu. (e.g., angka, karakter, string) tertentu.

Proses searching ini berupa jalur yang Proses searching ini berupa jalur yang menggambarkan keadaan awal sebuah masalah menggambarkan keadaan awal sebuah masalah menuju kepada penyelesaian masalah yang menuju kepada penyelesaian masalah yang diinginkan (i.e., the solved problem). diinginkan (i.e., the solved problem).

Jalur-jalur ini mengambarkan langkah-langkah Jalur-jalur ini mengambarkan langkah-langkah penyelesaian masalah. penyelesaian masalah.

Melalui proses searching menuju sebuah Melalui proses searching menuju sebuah penyelesaian akan terbentuk sebuah penyelesaian akan terbentuk sebuah solution solution spacespace..

Perhatikan contoh penyelesaian masalah komputer Perhatikan contoh penyelesaian masalah komputer pada Gambar 1.4. pada Gambar 1.4.

Langkah pertama untuk mengetahui apakah Langkah pertama untuk mengetahui apakah komputer dapat digunakan atau tidak adalah men-komputer dapat digunakan atau tidak adalah men-switch ON. switch ON.

Selanjutnya dengan melakukan inspeksi terhadap Selanjutnya dengan melakukan inspeksi terhadap kondisi lampu indikator kita dapat menentukan kondisi lampu indikator kita dapat menentukan langkah berikutnya.langkah berikutnya.

Misalnya kondisi lampu OFF.Misalnya kondisi lampu OFF. Dengan melakukan searching terhadap problem Dengan melakukan searching terhadap problem

space kita akan tiba pada sebuah penyelesaian space kita akan tiba pada sebuah penyelesaian masalah agar komputer dapat diaktifkan kembali.masalah agar komputer dapat diaktifkan kembali.

BLIND / UN-INFORMED SEARCHBLIND / UN-INFORMED SEARCH

Istilah Istilah blindblind atau buta digunakan karena memang tidak ada atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. informasi awal yang digunakan dalam proses pencarian.

Berikut ini, sekilas 6 metode yang tergolong blind searchBerikut ini, sekilas 6 metode yang tergolong blind searcha.a. Breadth-First Search (BFS)Breadth-First Search (BFS)b.b. Depth-First Search (DFS)Depth-First Search (DFS)c.c. Depth-Limited Search (DLS)Depth-Limited Search (DLS)d.d. Uniform Cost Search (UCS)Uniform Cost Search (UCS)e.e. Iterative-Deepening Search (IDS)Iterative-Deepening Search (IDS)f.f. Bi-Directional Search (BDS)Bi-Directional Search (BDS)

1. Breadth-first Search1. Breadth-first Search Breadth-first search (BFS) Breadth-first search (BFS) melakukan melakukan

proses searching pada semua node yang proses searching pada semua node yang berada pada level atau hirarki yang sama berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. searching pada node di level berikutnya.

Urutan proses searching BFS ditunjukkan Urutan proses searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,dalam Gambar 1.6 adalah: A,B,C,D,E,F,

Pada metode Breadth-First Search, semua Pada metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada dahulu sebelum mengunjungi node-node pada level n+1level n+1

Pencarian dimulai dari node akar terus ke Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusidari kiri ke kanan hingga ditemukannya solusi

Tidak akan menemui jalan buntu (solusi lebih Tidak akan menemui jalan buntu (solusi lebih optimal)optimal)

Jika ada satu solusi, maka breadth-first search Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan satu solusi, maka solusi minimum akan ditemukan.ditemukan.

Membutuhkan memori yang cukup banyak, Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu karena menyimpan semua node dalam satu pohonpohon (membutuhkan simpul yam umumnya (membutuhkan simpul yam umumnya relatif banyak)relatif banyak)

Membutuhkan waktu yang cukup lama, Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)mendapatkan solusi pada level yang ke-(n+1)

2. Depth-first Search2. Depth-first Search

Depth-first search (DFS) Depth-first search (DFS) adalah proses searching sistematis adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. path yang lain.

Proses searching mengikuti sebuah path tunggal sampai Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end.menemukan goal atau dead end.

Apabila proses searching menemukan dead-end, DFS akan Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum apakah node tersebut memiliki path cabang yang belum dieksplorasi. dieksplorasi.

Apabila cabang ditemukan, DFS akan melakukan cabang Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. tersebut.

Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah. parent sampai menemukan penyelesaian masalah.

Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 adalah: A, B, E, F, G, C, ...adalah: A, B, E, F, G, C, ...

Kelebihan DFS adalah:Kelebihan DFS adalah:

Pemakaian memori hanya sedikit, berbeda Pemakaian memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.semua node yang pernah dibangkitkan.

Jika solusi yang dicari berada pada level Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.menemukannya secara cepat.

Kelemahan DFS adalah:Kelemahan DFS adalah: Jika pohon yang dibangkitkan mempunyai Jika pohon yang dibangkitkan mempunyai

level yang dalam (tak terhingga), maka tidak level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi ada jaminan untuk menemukan solusi ((Tidak Tidak CompleteComplete).).

Jika terdapat lebih dari satu solusi yang Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (menemukan solusi yang paling baik (Tidak Tidak OptimalOptimal).).

3. Depth-Limited Search (DLS)3. Depth-Limited Search (DLS)

Metode ini berusaha mengatasi kelemahan DFS Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan (tidak complete) dengan membatasi kelemahan maksimum dari suatu jalur solusi.maksimum dari suatu jalur solusi.

Tetapi, sebelum menggunakan DLS, kita harus Tetapi, sebelum menggunakan DLS, kita harus tahu berapa level maksimum dari suatu solusi.tahu berapa level maksimum dari suatu solusi.

www.themegallery.com

DefinisiDefinisi Algoritma Depth-Limited Search (DLS), adalah salah satu Algoritma Depth-Limited Search (DLS), adalah salah satu

jenis jenis algoritma pencarian solusi. Algoritma ini dijalankan algoritma pencarian solusi. Algoritma ini dijalankan dengan cara membangkitkan pohon pencarian dengan cara membangkitkan pohon pencarian secara secara dinamis. Pencarian solusi dilakukan secara mendalam.dinamis. Pencarian solusi dilakukan secara mendalam.

Pada dasarnya, algoritma DLS sama dengan algoritma Pada dasarnya, algoritma DLS sama dengan algoritma DFS, hanya saja dalam permasalahan penelusuran graf, DFS, hanya saja dalam permasalahan penelusuran graf, sebelumnya ditentukan terlebih dahulu batas maksimum sebelumnya ditentukan terlebih dahulu batas maksimum level yang dikunjungi. level yang dikunjungi.


AlgoritmaAlgoritma

1.1.Tentukan batas kedalaman pohon yang akan dikunjungi.

2.2.Kunjungi simpul v.

3.3.Kunjungi simpul w yang bertetangga dengan simpul v, yang berada di kedalaman pohon <= batas.

Misalkan terdapat graf/pohon dengan n buah simpul dan v merupakan Misalkan terdapat graf/pohon dengan n buah simpul dan v merupakan simpul awal penelusuran maka algoritma DFS adalah sebagai berikut:simpul awal penelusuran maka algoritma DFS adalah sebagai berikut:


4.4.Ulangi DLS mulai dari simpul w.

5.5.Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.

6.6.Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi dalam kedalaman pohon <= batas.

Kelebihan dan KekuranganKelebihan dan Kekurangan DLS lahir untuk mengatasi kelemahan DLS lahir untuk mengatasi kelemahan

DFS(tidak complete) dengan membatasi DFS(tidak complete) dengan membatasi kedalaman maksimum dari suatu jalur solusi. kedalaman maksimum dari suatu jalur solusi. Tetapi harus diketahui atau ada batasan dari Tetapi harus diketahui atau ada batasan dari sistem tentang level maksimum. Jika batasan sistem tentang level maksimum. Jika batasan kedalaman terlalu kecil, DLS tidak complete.kedalaman terlalu kecil, DLS tidak complete.



Contoh 1Contoh 1

Bila simpul awal adalah 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 4, 5, 3, 6,7.


Contoh 2Contoh 2

Bila simpul awal juga 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 5, 6, 3, 7, 4


Water Jug ProblemWater Jug Problem

4

3

2

1

Terkadang apa yang kita

punya, tidak sesuai dengan

apa yang kita harapkan.

DefinisiDefinisi Water Jug problem adalah masalah yang Water Jug problem adalah masalah yang

membutuhkan konversi situasi menjadi situasi membutuhkan konversi situasi menjadi situasi lain yang diinginkan dengan menggunakan lain yang diinginkan dengan menggunakan sekumpulan operasi tertentu. Dan masalah ini sekumpulan operasi tertentu. Dan masalah ini dapat di selesaikan dengan merepresentasikan dapat di selesaikan dengan merepresentasikan semua kemungkinan hasil dalam sebuah semua kemungkinan hasil dalam sebuah pohon. Maka masalah ini dapat dikategorikan pohon. Maka masalah ini dapat dikategorikan sebagai masalah yang membutuhkan sebagai masalah yang membutuhkan penelusuran graf. penelusuran graf.


Oleh karena itu penulis berpendapat bahwa Oleh karena itu penulis berpendapat bahwa masalah ini dapat diselesaikan dengan baik masalah ini dapat diselesaikan dengan baik dengan menggunakan keempat algoritma dengan menggunakan keempat algoritma tersebut (BFS, DFS, DLS, dan IDS).tersebut (BFS, DFS, DLS, dan IDS).



ContohContoh1

Kita mempunyai sebuah gelas dengan kapasitas 4 liter dan sebuah gelas yang lain dengan kapasitas (misalkan) 3 liter. Kedua gelas tidak memiliki skala ukuran dan dalam keadaan kosong. Kita ingin mendapatkan air sebanyak 2 liter dalam gelas yang berkapasitas 4 liter dan tidak boleh mendapatkannya dengan menggunakan prediksi sendiri. Selain itu, kita harus mengikuti suatu operasi-operasi tertentu, seperti dalam tabel berikut. Keteranganx adalah gelas dengan kapasitas 4 liter y adalah gelas dengan kapasitas 3 liter


PenyelesaianPenyelesaian

Suatu solusi untuk Water Jug Suatu solusi untuk Water Jug ProblemProblem



DiagramDiagram

66

11

22

33

Pencarian Solusi dengan menggunakan algoritma DLS

44

55

7788


PenerapanPenerapanLangkah-langkah yang dilakukan dalam pencarian solusi Langkah-langkah yang dilakukan dalam pencarian solusi menggunakan algoritma DLS adalahmenggunakan algoritma DLS adalah

Tentukan kedalaman simpul yang dikunjungi (n), misalkan n=5.Tentukan kedalaman simpul yang dikunjungi (n), misalkan n=5. Masukkan simpul akar (0, 0) ke dalam antrian q, jika simpul Masukkan simpul akar (0, 0) ke dalam antrian q, jika simpul

akar adalah simpul tujuan (goal node) maka solusi akar adalah simpul tujuan (goal node) maka solusi ditemukan.Stop.ditemukan.Stop.

Jika S kosong, tidak ada solusi. Stop.Jika S kosong, tidak ada solusi. Stop. Cek apakah sesuai dengan keinginan (2,0).Jika true maka solusi Cek apakah sesuai dengan keinginan (2,0).Jika true maka solusi

ketemu. Jika false maka bangkitkan simpul tetangga, dan ulang ketemu. Jika false maka bangkitkan simpul tetangga, dan ulang (2), hingga kedalaman simpul yang dikunjungi <= 5.(2), hingga kedalaman simpul yang dikunjungi <= 5.

Source CodeSource Codeprocedureprocedure DLS ( DLS (inputinput v: Point, level:integer) v: Point, level:integer)kamuskamusw: pointw: pointq: antrianq: antrianalgoritmaalgoritmawrite(v)write(v)dikunjungi[v] ← true {array untuk menampung simpul yang sudah dikunjungi}dikunjungi[v] ← true {array untuk menampung simpul yang sudah dikunjungi}level level 1 1whilewhile notnot level > 5 level > 5 dodo{ kunjungi semua simpul di level 1,panggl algoritma DFS}{ kunjungi semua simpul di level 1,panggl algoritma DFS}ifif A[v,w] = 1 A[v,w] = 1 thenthen {simpul v dan simpul w bertetangga} {simpul v dan simpul w bertetangga}if if notnot dikunjungi[w] dikunjungi[w] thenthenDLS(w, level)DLS(w, level)endifendifendifendif level level level +1 level +1endwhileendwhile


Perbandingan Strategi PencarianPerbandingan Strategi Pencarian


Keteranganb : faktor percabangand : kedalaman solusiM : kedalaman maksimum pohon pencarianl : kedalaman

4. Uniform Cost Search (UCS)4. Uniform Cost Search (UCS)

Konsepnya hampir sama dengan BFS, Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS bedanya adalah bahwa BFS menggunakan urutan level yang menggunakan urutan level yang paling rendah sampai yang paling paling rendah sampai yang paling tinggi, sedangkan UCS menggunakan tinggi, sedangkan UCS menggunakan urutan biaya dari yang paling kecil urutan biaya dari yang paling kecil sampai yang terbesar.sampai yang terbesar.

UCS berusaha menemukan solusi UCS berusaha menemukan solusi dengan total biaya terendah yang dengan total biaya terendah yang dihitung berdasarkan biaya dari dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan.simpul asal menuju ke simpul tujuan.

5. Iterative-Deepening Search (IDS)5. Iterative-Deepening Search (IDS)

IDS merupakan metode yang IDS merupakan metode yang menggabungkan kelebihan BFS (Complete menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan complexity rendah atau membutuhkan sedikit memori)sedikit memori)

Tetapi konsekwensinya adalah time Tetapi konsekwensinya adalah time complexitynya menjadi tinggi.complexitynya menjadi tinggi.

Iterative deepening searchIterative deepening search

The problem with depth-limited search is deciding on a suitable depth The problem with depth-limited search is deciding on a suitable depth parameter. To avoid this problem there is another search called iterative parameter. To avoid this problem there is another search called iterative deepening search (IDS).deepening search (IDS).

This search method tries all possible depth limits; first 0, then 1, then 2 This search method tries all possible depth limits; first 0, then 1, then 2 etc., until a solution is found.etc., until a solution is found.

IDS may seem wasteful as it is expanding nodes multiple times. But the IDS may seem wasteful as it is expanding nodes multiple times. But the overhead is small in comparison to the growth of an exponential search overhead is small in comparison to the growth of an exponential search treetree

For large search spaces where is the depth of the solution is not known IDS For large search spaces where is the depth of the solution is not known IDS is normally the preferred search method.is normally the preferred search method.

The following slide illustrates an iterative deepening search of 26 nodes The following slide illustrates an iterative deepening search of 26 nodes (states) with an initial state of node A and a goal state of node L. Press (states) with an initial state of node A and a goal state of node L. Press space to see the example node set.space to see the example node set.

A

C D E FB

G H I J K L M N O P

Q R S T U V W X Y Z

The example node set

Initial state

Goal state

A

L

Press space to see a IDS of the example node set

AA We begin with our initial state: the node labeled A. This node is added to the queue. Press space to continue

Size of Queue: 0

Nodes expanded: 0 Current Action: Expanding Current level: n/a

Queue: EmptyQueue: ASize of Queue: 1

Current level: 0Nodes expanded: 1

Queue: EmptySize of Queue: 0

Press space to begin the search

As this is the 0th iteration of the search, we cannot search past any level greater than zero. This iteration now ends, and we begin the 1st iteration.

ITERATIVE DEEPENING SEARCH PATTERN (0th ITERATION)

Node A is then expanded and removed from the queue. Press space.

A

C D E FB

A

B C D

We again begin with our initial state: the node labeled A. Note that the 1st iteration carries on from the 0th, and therefore the ‘nodes expanded’ value is already set to 1. Press space to continue

Node A is expanded, then removed from the queue, and the revealed nodes are added to the front . Press space.

The search now moves to level one of the node set. Press space to continue

Node B is expanded and removed from the queue. Press space.

Size of Queue: 0

Nodes expanded: 1 Current Action: Current level: n/a


Nodes expanded: 2

Queue: B, C, D, E, F

Press space to begin the search

Size of Queue: 5

Current level: 0Current Action: Expanding

Queue: C, D, E, FSize of Queue: 4

Nodes expanded: 3 Current level: 1Current Action: Backtracking Current level: 0Current level: 1

Queue: D, E, FSize of Queue: 3

Nodes expanded: 4 Current Action: ExpandingCurrent Action: Backtracking Current level: 0Current level: 1

Queue: E, FSize of Queue: 2

Nodes expanded: 5 Current Action: ExpandingCurrent Action: Backtracking Current level: 0Current level: 1Current Action: Expanding

Queue: F

E

Current Action: Backtracking Current level: 0Current Action: Expanding Current level: 1

Queue: Empty

F

Current level: 0Current level: 1

Press space to continue the searchPress space to continue the searchPress space to continue the search

ITERATIVE DEEPENING SEARCH PATTERN (1st ITERATION)

Size of Queue: 1Size of Queue: 0

As this is the 1st iteration of the search, we cannot search past any level greater than level one. This iteration now ends, and we begin a 2nd iteration.

Nodes expanded: 6Nodes expanded: 7

We now back track to expand node C, and the process continues. Press space.

A

C D E FB

G H I J K L

A

B

G

We again begin with our initial state: the node labeled A. Note that the 2nd iteration carries on from the 1st, and therefore the ‘nodes expanded’ value is already set to 7 (1+6). Press space to continue the search

Again, we expand node A to reveal the level one nodes. Press space.Node A is removed from the queue and each revealed node is added to the front of the queue. Press space.

The search then moves to level one of the node set. Press space to continueNode B is expanded and the revealed nodes added to the front of the queue. Press space to continue.

Size of Queue: 0

Nodes expanded: 7 Current Action: Current level: n/a


Current level: 0Nodes expanded: 8

Queue: B, C, D, E, F

Current level: 1

Queue: G, H, C, D, E, F

Nodes expanded: 9 Current level: 2

ITERATIVE DEEPENING SEARCH PATTERN (2nd ITERATION)

Size of Queue: 5

Current Action: Expanding

We now move to level two of the node set. Press space to continue.After expanding node G we backtrack to expand node H. The process then continues until goal state. Press space

Queue: H, C, D, E, F

Nodes expanded: 10 Current Action: BacktrackingCurrent Action: Expanding

Queue: C, D, E, FSize of Queue: 6

Nodes expanded: 11

H

Press space to continue the search

Size of Queue: 5Size of Queue: 4

Current Action: BacktrackingCurrent Action: Expanding

Queue: I, J, D, E, FSize of Queue: 5

Nodes expanded: 12


C

Current level: 1Current level: 2Current level: 1Current level: 0Current level: 1Current level: 2

Queue: J, D, E, FSize of Queue: 4

Nodes expanded: 13

I


Current Action: Backtracking Current level: 1Current level: 2

Queue: D, E, F

Current Action: Expanding

Size of Queue: 3

Nodes expanded: 14

J


Current Action: Backtracking Current level: 1Current level: 0Current level: 1Current Action: Expanding

Queue: K, L, E, FSize of Queue: 4

Nodes expanded: 15

D


Current level: 2

Queue: L, E, FSize of Queue: 3

Nodes expanded: 16

K


Current Action: Expanding Current level: 1Current level: 2

LLLLL

Current Action: Backtracking

Queue: EmptySize of Queue: 0

Node L is located on the second level and the search returns a solution on its second iteration. Press space to end.

SEARCH FINISHED

6. 6. Bi-Directional Search (BDS)Bi-Directional Search (BDS)

Pencarian dilakukan dari dua arah : Pencarian dilakukan dari dua arah : pencarian maju (dari start ke goal) dan pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu. menggabungkan kedua jalur yang bertemu.

kecerdasan buatan (artificial intelligence)

Documents