Rika Amalia-UTS MK Kecerdasan Buatan

UJIAN TENGAH SEMESTER GENAP TAHUN AKADEMIK 2020/2021

UNIVERSITAS AL-KHAIRIYAH

Nama : Rika Amalia

Nim : 18020063

Kelas : 6B

1.   Jelaskan teknik penyelesaian masalah yang dapat dipakai untuk menyelesaikan permasalahan di kecerdasan buatan (AI)!

1)      Definisikan masalah dengan jelas

Pendefinisian Masalah Sebagai Pencarian Ruang Keadaan atau “State Space Search” (SSS)

Masalah utama dalam membangun sistem berbasis AI adalah bagaimana mengkonversikan situasi yang diberikan ke dalam situasi lain yang diinginkan menggunakan sekumpulan operasi tertentu.

2)      Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai

3)      Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut.

4)      Memilih teknik penyelesaian masalah yang terbaik.

 

2.       Jelaskan dan berikan contoh mengenai Blind Search dan Heuristic Search!

Blind Search merupakan pencarian asal. Jika solusi sudah ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi].

Contoh Studi Kasus : Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.

Permasalahannya : adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.

Deskripsi

P = Petani

Sy = Sayuran

K = Kambing

Sg = Serigala

Ruang Keadaan

Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)

Keadaan Awal

Daerah Asal = (P, Sy, K, Sg)

Daerah seberang = (0, 0, 0, 0)

Tujuan

Daerah Asal = (0, 0, 0, 0)

Daerah seberang = (P, Sy, K, Sg)

Metode Penyelesaian :

a. Berikut ini adalah algoritma BFS :

Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.

Jika Q kosong, tidak ada solusi. Stop

Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.

Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.

b. Menggunakan algoritma DFS :

Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.

Jika Q kosong, tidak ada solusi. Stop.

Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2

Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.

Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.

Contoh :“Travelling Salesman Problem (TSP)”

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya  boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :Alur pencarian dengan Generate and Test

Pencarian ke-	Lintasan	Panjang Lintasan	Lintasan terpilih	Panjang Lintasan terpilih
1	ABCD	19	ABCD	19
2	ABDC	18	ABDC	18
3	ACBD	12	ACBD	12
4	ACDB	13	ACBD	12
5	ADBC	16	ACBD	12
Dst…..

 

3.        Jelaskan perbedaan antara

a.  Breadth First Search (BFS), Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

b. Depth First Search (DFS), Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

c.   Uniform Cost Search (UCS), Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

d. Depth-Limited Search (DLS), pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

e.    Iterative Deepening Search (IDS), Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

f.  Bi-Directional Search (BDS), Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.

4.       Berikan contoh dari kegunaan AI dalam kehidupan sehari hari!

Conton penerapan Artificial Intelligence di kehidupan sehari-hari yaitu Filter email di Gmail, Google menggunakan AI untuk memastikan bahwa hampir semua email yang diterima dalam kotak masukmu bersifat asli. Filter email di Gmail menggunakan penerapan Artificial Intelligence untuk mengurutkan email ke dalam sejumlah kategori, yakni utama, sosial, promosi, pembaruan, forum, dan spam. Program ini membantu mengorganisir email-mu sehingga kamu pun lebih mudah melakukan komunikasi melalui email.

Contohnya, Gmail mengurutkan email menjadi 4 kategori tab yang berbeda, dan mengirim email spam ke dalam folder terpisah. Google juga mengklaim bahwa pemfilteran berbasis AI mencegah lebih dari 99% spam masuk ke kotak masuk email-mu.