ALGORITMA PENCARIAN (1)

ALGORITMA PENCARIAN (1) Permasalahan, Ruang Keadaan, Pencarian Farah Zakiyah Rahmanti Diperbarui 2016

Universitas Dian Nuswantoro

Overview 

    

Deskripsi Permasalahan dalam Kecerdasan Buatan Definisi Permasalahan Pencarian Breadth First Search (BFS) Depth First Search (DFS) Studi Kasus


Masalah ... ? 

Kita ingin makan nasi, tetapi kenyataannya tidak punya beras dan tidak punya uang !


Deskripsi Permasalahan dalam Kecerdasan Buatan (1) 

Masalah-masalah dapat dikonversi ke dalam ruang keadaan, keadaan awal (initial state), dan keadaan tujuan (goal state).



Dapat dibuat aturan tertentu untuk mengubah keadaan (state) ke keadaan (state) lainnya.


Deskripsi Permasalahan dalam Kecerdasan Buatan (2) 

Ruang keadaan (state space) Suatu ruang yang berisi semua keadaan yang mungkin.



Keadaan awal (initial state) Keadaan dimulainya pencarian.



Keadaan akhir / tujuan (goal) Keadaan diakhirinya sebuah pencarian.



Aturan Aturan yang dapat digunakan untuk mengubah suatu keadaan (state) ke keadaan (state) lainnya. Universitas Dian Nuswantoro

Langkah Mendeskripsikan Permasalahan    

(1) Mendefinisikan suatu ruang keadaan (2) Menetapkan satu/lebih keadaan awal (3) Menetapkan satu/lebih tujuan (goal) (4) Menetapkan kumpulan aturan


Studi Kasus 







Ada seorang petani yang ingin memindahkan serigala, kambing, dan rumput yang dimilikinya ke sebrang sungai. Namun, perahunya terbatas. Hanya bisa membawa satu obyek dalam satu kali penyebrangan. Petani tidak boleh meninggalkan serigala dengan kambing dalam satu tempat. Karena serigala akan memakan kambing tersebut. Petani tidak boleh meninggalkan kambing dengan rumput dalam satu tempat. Karena kambing akan memakan rumput tersebut. Universitas Dian Nuswantoro

Studi Kasus - Ruang Keadaan 

Daerah asal dan daerah sebrang digambarkan sebagai (petani P, serigala S, kambing K, rumput R)


Studi Kasus - Keadaan Awal  

Daerah asal : (S, K, R, P) Daerah tujuan : (0, 0, 0, 0)


Studi Kasus - Tujuan  

Daerah asal : (0, 0, 0, 0) Daerah tujuan : (S, K, R, P)


Studi Kasus - Aturan No

Rules

1

Kambing dan petani menyebrang

2

Rumput dan petani menyebrang

3

Serigala dan petani menyebrang

4

Kambing dan petani kembali

5

Rumput dan petani kembali

6

Serigala dan petani kembali

7

Petani kembali Universitas Dian Nuswantoro

Studi Kasus - Solusi Daerah Asal (S, K, R, P) (1, 1, 1, 1) (1, 0, 1, 0) (1, 0, 1, 1) (0, 0, 1, 0) (0, 1, 1, 1) (0, 1, 0, 0) (0, 1, 0, 1) (0, 0, 0, 0)

Daerah Sebrang (S, K, R, P (0, 0, 0, 0) (0, 1, 0, 1) (0, 1, 0, 0) (1, 1, 0, 1) (1, 0, 0, 0) (1, 0, 1, 1) (1, 0, 1, 0) (1, 1, 1, 1)

Aturan yang digunakan


1 7 3 4 2 7 1 solusi

Representasi Ruang Keadaan   

Graph Keadaan Pohon Pelacakan Pohon AND/OR


Graph Keadaan (1) 



    

Graph terdiri dari node-node yang menunjukkan keadaan. Node-node dihubungkan oleh busur panah (arc). Contoh : terdapat 4 lintasan dari A ke Z A-B-D-E-G-Z 1 3 K B J 4 D A-B-D-E-G-H-Z G 4 4 6 7 2 A-C-E-G-Z Z E A H 8 6 A-C-E-G-H-Z 5

3 F C

2

I 4


Graph Keadaan (2) 

Pada Graph tersebut, ada lintasan yang menemui jalan buntu. A-B-D-E-G-J-K A A-B-D-E-G-F-I A-C-F-I A-C-E-G-J-K A-C-E-G-F-I B

3

D

 

  

4

4

2

H

3

F

2


K

7

8

C

1

G

6

E

5

J

4

I

4

6

Z

Pohon Pelacakan (1)

B

3 D

4

4

2 8

5

F


H

3

C

2

1

K

G

6

E

A

J

4

4

I

7

Z 6

Pohon Pelacakan (2) 

Untuk menghindari adanya siklus, maka digunakan struktur pohon.



Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis.



Pohon terdiri dari beberapa node. Node yang terletak pada level-0 disebut node “akar” yang menunjukkan keadaan awal.





Node akar memiliki beberapa percabangan yang terdiri-atas beberapa node anak (successor) sebagai node-node perantara. Namun jika dilakukan pencarian mundur, maka dapat dikatakan bahwa node tersebut memiliki predecessor.


Pohon Pelacakan (3) 

Node-node yang tidak memiliki anak disebut node “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa goal atau jalan buntu (dead end).



sudah tidak terlihat lagi adanya siklus, karena setiap node tidak diperbolehkan memiliki cabang kembali ke node dengan level yang lebih rendah. Universitas Dian Nuswantoro

Mengapa menggunakan Pohon Pelacakan ?  

Untuk menghindari adanya siklus. Untuk menggambarkan keadaan hierarkis.


secara

Pohon AND/OR

B

3 D

4

4

2 8

5

H

3 F C


2

1

K

G

6 E

A

J

4

4

I

7

Z 6

Searching 

Sebagai teknik pemecahan masalah.



Untuk membangun sistem dalam menyelesaikan masalah-masalah di atas, biasanya mempertimbangkan :

- Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup deskripsi masalah dengan baik. - Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai. - Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut. - Memilih teknik penyelesaian masalah yang terbaik. Universitas Dian Nuswantoro

Teknik Penyelesaian Masalah yang Terbaik Pemecahan masalah dengan menggunakan searching akan lebih mudah bila obyeknya direpresentasikan sebagai graf.



Searching

(pencarian),



Reasoning (penalaran)



Planning yaitu memecah masalah kedalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap.



Learning yaitu program komputer yang secara otomatis sanggup belajar dan meningkatkan performencenya melalui pengalaman. Universitas Dian Nuswantoro

Metode Pencarian (Searching) 

Pencarian buta / blind searching - Breadth First Search (BFS) - Depth First Search (DFS)



Pencarian terbimbing / heuristic searching - Hill Climbing - Best First Search


Studi Kasus


Studi Kasus - Struktur pohon


Studi Kasus Penyelesaian dengan BFS


Definisi BFS 

Semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi nodenode pada level n+1.



Pencarian dimulai dari node akar terus ke level ke 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi.


Algoritma BFS 





1. Buat sebuah antrian (queue), inisialisasi node pertama dengan root dari tree.

2. Bila node pertama, jika ≠ GOAL, diganti dengan anakanaknya dan diletakkan dibelakang PER LEVEL. 3. Bila node pertama = GOAL, selesai.


Algoritma BFS



Lintasan yang didapat S-B-C-E-Z Universitas Dian Nuswantoro

BFS Keuntungan 

Kelemahan

Menjamin ditemukannya Solusi yang paling baik.



Karena BFS harus menyimpan semua node yang dibangkitkan maka metode ini membutuhkan memori dan waktu yang cukup banyak


Studi Kasus Penyelesaian dengan DFS


Definisi DFS 

Proses pencarian akan dilaksanakan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel.



Pencarian dimulai dari node akar ke level yang lebih tinggi.



Proses ini diulangi terus hingga ditemukannya solusi. Universitas Dian Nuswantoro

Algoritma DFS 





1. Buat sebuah tumpukan (stack), inisialisasi node pertama dengan root dari tree. 2. Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan L Child. 3. Bila node pertama = GOAL, selesai.


Algoritma DFS

Karena stack, anggap pintu masuk = pintu keluar. Asumsi pintu dari kiri.

D D B D B 

Lintasan yang didapat : S-A-B-C-E-Z Universitas Dian Nuswantoro

DFS Keuntungan 



Kelemahan

Membutuhkan memori yang relatif kecil karena hanya nodenode pada lintasan yang aktif saja yang disimpan.



Memungkinkan tidak ditemukannya tujuan yang diharapkan.



Hanya akan mendapatkan 1 solusi pada setiap pencarian.

DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dala ruang keadaan.


Latihan


Latihan 

 

Representasikan graph ke dalam struktur pohon ! Tentukan lintasannya ! Selesaikan kasus tersebut dengan menggunakan BFS dan DFS !


Terima Kasih


ALGORITMA PENCARIAN (1)

Recommend Documents