8/3/2019 AI_6A Problema & Pendekatan ian Masalah

1/31

Problema &Pendekatan

Penyelesaian Masalah

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

2/31

Langkah Penyelesaian Masalah

Tiga langkah utama yang dibutuhkan untuk membuat sebuahsistem dapat menyelesaikan suatu persoalan khusus, yaitu:

1. Mendefinisikan problema dengan tepat.

Definisi ini harus berisi spesifikasi tentang kondisi awal dan

situasi akhir yang menghasilkan solusi yang dapat diterima dariproblema tersebut.

2. Menganalisis problema.

Beberapa sifat yang sangat penting bisa memiliki dampak yangsangat kuat pada kelayakan banyak teknik pemecahan problema

yang dimungkinkan.3. Memilih teknik penyelesaian masalah yang terbaik.

Dalam Sistem Cerdas ditambahkan satu langkah lagi:

4. Merepresentasikan pengetahuan.

Ini diperlukan untuk menyelesaikan masalah tersebut.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

3/31

Hipotesis Sistem Simbol Fisis

Newelldan Simonmengemukakan bahwa aktivitascerdas (intelligent) dicapai melalui digunakannya :

Pola-pola simbol untuk merepresentasikan aspek-aspek penting dari problema.

Operasi pada pola-pola tersebut untukmenghasilkan solusi potensial dari problema.

Proses pencarian untuk memilih sebuah solusidiantara kemungkinan-kemungkinan yang ada itu.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

4/31

Hipotesis Sistem Simbol Fisis

Asumsi-asumsi ini membentuk dasar bagihipotesis sistem simbol fisis.

Hipotesis sistem simbol fisis secara implisitmembedakan antarapolayang dibentuk olehsusunan simbol-simbol dan mediayang dipakaiuntuk mengimplementasikannya.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

5/31

Hipotesis Sistem Simbol Fisis

Pendefinisian struktur dan operasi simbol yangdiperlukan dalam

pemecahan problema kecerdasan,

pengembangan strategi bagi proses pencarian yangbekerja dengan efisien dan benar untukmendapatkan solusi yang potensial.

Asumsi-asumsi hipotesis sistem simbol fisismendasari hampir semua aspek praktis danteoritis dalam sistem pakar, perencanaan, dan

pemahaman bahasa alamiah

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

6/31

Representasi Pengetahuan

Perepresentasian dimaksud untuk menangkap sifat-sifatpenting problema dan membuat informasi itu dapatdiakses oleh prosedur pemecahan problema.

Bahasa representasi harus dapat membuat seorangpemrogram mampu mengekspresikan pengetahuanyang diperlukan untuk mendapatkan solusi problema.

Ekspresifitas dan efisiensi merupakan dimensi utamadalam melakukan evaluasi bahasa-bahasa representasipengetahuan .

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

7/31

Representasi Pengetahuan

Perepresentasian seharusnya :

Memadai untuk mengekspresikan informasi yangdiperlukan.

Mendukung eksekusi yang efisien dari kode yangdihasilkan.

Menghasilkan sesuatu yang alamiah untuk

mengekspresikan pengetahuan yang dibutuhkan

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

8/31

Bahasa Kecerdasan Buatan

Agar dapat mendukung perepresentasian, bahasaKecerdasan Buatan haruslah:

1. Mampu menangani pengetahuan kualitatif

2. Memperbolehkan dilibatkannya pengetahuan barudari sejumlah fakta dasar

3. Memperbolehkan digunakannya representasi prinsip-

prinsip umum dan situasi-situasi khusus4. Dapat menangkap arti semantik yang rumit

5. Memperbolehkan digunakannya kerangka sebab-akibat meta-level.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

9/31

Penganalisisan dan

Karakteristik Problema Penganalisisan problema diperlukan untuk

memilih metode (atau gabungan beberapametode) yang paling baik untuk suatu problema

tertentu sangatlah penting.

Beberapa pertanyaan berkenaan denganpenganalisisan suatu problema dapat diajukan

seperti :

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

10/31

1. Apakah suatu problema dapat

didekomposisi/dipilah-pilah menjadi

sejumlah upa-problema independen yanglebih kecil atau lebih mudah?

Untuk problema yang tidak dapat

didekomposisi, ditangani dengan teknik bagi dantaklukan (divide and conquer).

Contoh problema yang dapat didekomposisi

adalah problema menghitung integral takberbatas.

(x4 + 7x + cos2x) dx

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

11/31

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

12/31

2. Dapatkah langkah-langkah penyelesaian

yang terbukti tidak tepat, diabaikan atau

tidak perlu dikerjakan? Berkaitan dengan langkah-langkah yang diambil

dalam penyelesaian problema, akan muncul 3

problema penting yang berbeda dapat diabaikan, dimana langkah solusi dapat diabaikan,

seperti pada pembuktian teorema.

dapat diulang (recoverable), dimana langkah solusi dapatdibatalkan, seperti pada permainan teka-teki 8 (the 8-puzzle).

tidak dapat diulang (irrecoverable), dimana langkah solusi

tidak dapat dibatalkan, seperti pada permainan catur

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

13/31

Problema yang dapat diulang dapat dipecahkandengan strategi pengendalian yang agak rumit

yang kadang-kadang dapat melakukan langkahyang salah.

Dibutuhkan pelacakan kembali untuk

mengungkap kesalahan tersebut. Sehinggastruktur pengendalian harus dilakukan denganmemakaipushdown stack, dimana keputusan-

keputusan direkam agar bisa dibatalkankemudian.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

14/31

Problema yang tidak dapat diulang / dibatalkanakan membutuhkan pemecahan oleh suatu

sistem yang mampu melakukan prakiraaan setiapkeputusan, karena keputusan yang diambilmerupakan keputusan terakhir.

Beberapa problema yang tidak dapat diulangdapat dipecahkan dengan cara memakai prosesperencanaan (planning), dimana seluruh urutan

langkah dianalisis terlebih dahulu untukmenemukan apa yang bakal terjadi bila langkahtersebut benar-benar dilaksanakan.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

15/31

3. Apakah ruang lingkup atau semestapembicaraan problema dapat

diprakirakan ?

Perencanaan merupakan pemecahanproblema tanpa adanya umpan balik (feedback)dari lingkungannya.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

16/31

Ada jenis problema yang mempunyaipenyelesaian yang pasti dan ada yang tidak pasti.

Untuk memecahkan problema dengan

penyelesaian yang pasti, pendekatan loop terbukaakan dapat bekerja dengan baik begitu hasilsuatu tindakan dapat diprakirakan dengan

sempurna.

Di sini, perencanaan dapat digunakan untukmenghasilkan serangkaian operator (aturan) yangdijamin dapat sampai pada solusi.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

17/31

Untuk problema yang penyelesaiannya tidak

pasti, perencanaan hanya dapat menghasilkan

serangkaian operator(aturan) yang memilikiprobabilitas yang baik untuk sampai pada solusi.

Untuk memecahkan problema semacam ini,dibutuhkan adanya proses revisi rencana

dengan cara melibatkan adanya proses umpan

balik.

Perencanaan seringkali menjadi sangat mahal

karena jumlah jalan menuju solusi yang harusdiungkapkan akan naik secara eksponensialterhadap jumlah titik yang keluarannya tidak

dapat diprakirakan.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

18/31

4. Apakah solusi problema yang baik telah

dibandingkan dengan semua solusi yang

dimungkinkan? Sebuah solusi problema yang baik dapat bersifat

mutlak atau relatif dengan cara dibandingkan

dengan semua solusi yang dimungkinkan.

Sebuah solusi untuk suatu problema mungkin telah

memperoleh jawaban yang diinginkan denganmengikuti sebuah lintasan penalaran saja, dengantidak mempedulikan lintasan mana yangdigunakan.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

19/31

Contoh sebuah problema untuk menjawabpertanyaan: Apakah Agus hidup?, berdasarkan

pada basis data fakta-fakta sederhana berikut:1. Agus adalah seorang laki-laki

2. Agus adalah seorang berkebangsaan x

3. Agus dilahirkan pada tahun 1404. Semua manusia adalah fana

5. Semua orang berkebangsaan x meninggal karenaadanya bencana banjir di tahun 179

6. Tidak ada manusia yang dapat hidup lebih lama dari170 tahun

7. Sekarang tahun 1990

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

20/31

Dua lintasan (path) penalaran berikut akan sampaipada jawaban yang benar

Lintasan penalaran 1 Pembenaran

1. Agus adalah seorang laki-laki [Aksioma 1]

4. Semua manusia adalah fana [Aksioma 4]

8. Agus adalah fana [1, 4]3. Agus dilahirkan pada tahun 140 [Aksioma 3]

7. Sekarang adalah tahun 1990 [Aksioma 7]

9. Umur agus adalah 1854 tahun [3, 7]6. Tidak ada manusia yang dapat hidup lebih lama dari 170

tahun [Aksioma 6]

10. Agus sudah meninggal [8, 6, 9]

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

21/31

Lintasan penalaran 2 Pembenaran

7. Sekarang adalah tahun 1992 [Aksioma 7]

5. Semua orang berkebangsaan x meninggal pada tahun179 [Aksioma 5]

11. Semua orang berkebangsaan x telah meninggalseluruhnya saat ini [7, 5]

2. Agus adalah seorang berkebangsaan x [Aksioma 2]

12. Agus sudah meninggal [11, 2]

Karena yang diinginkan adalah jawaban dari

pertanyaan di atas, maka tidak memperdulikanlintasan mana yang digunakan.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

22/31

Persoalan di atas merupakanproblema sembaranglintasan. Untuk problema ini, apabila dengan

mengikuti sebuah lintasan penalaran sudahberhasil memperoleh jawaban yang diinginkan,

maka tak ada alasan untuk melihat adanyakemungkinan suatu lintasan lain yang jugamenghasilkan jawaban yang diharapkan.

Sedangkan problema wiraniaga yang hendakmencari jarak total terpendek dalam melalui

beberapa kota, merupakanproblema lintasanterbaik. Dalam problema ini, sebuah jawabantidak dapat dipastikan kebenarannya kecuali

setelah semua lintasan / jalur yang ada dicoba.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

23/31

Pada umumnya, problema lintasan terbaik lebihsulit dipecahkan daripada problema sembaranglintasan.

Problema sembarang lintasan seringkali dapatdipecahkan dalam waktu yang tidak terlalu lamadengan menggunakan heuristik yang

menawarkan lintasan-lintasan mana saja yangsebaiknya ditelusuri. Untuk problema lintasanterbaik, sebaiknya melibatkan lebih banyak

exhaustive search.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

24/31

5. Apakah basis pengetahuan yang digunakan

untuk memecahkan problema bersifat

konsisten secara internal Misalkan terdapat seperangkat aksioma untuk grup

perkalian

1. XY didefinisikan untuk semua XY

2. X = Y Y = Z X = Z

3. X = X

4. (XY)Z = X(YZ)

5. IX = X

6. X-1X = I

7. X = Y ZX = ZY

8. X = Y XZ = YZ

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

25/31

Aksioma tersebut di atas digunakan untukmemecahkan problema

Buktikan bahwa XI = X

Karena kekonsistenan aksioma yang ada(merupakan basis pengetahuannya), kita dapat

membuktikannya dengan prosedur pembuktianmatematika standar

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

26/31

Sekarang kita akan memecahkan problemaberikut :

Seseorang berdiri pada jarak 50 meter dari sebuah

sasaran. Dia merencanakan untuk menembak sasaran

itu dengan sebuah senapan yang pelurunya memiliki

kecepatan 500 meter per detik saat keluar dari moncong

senapan. Seberapa tinggikah dari sasaran dia harusmengarahkan senapannya ?

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

27/31

Karena adannya ketidak konsistenan dalam basisdatanya, maka problema tersebut dipecahkansebagai berikut:

Karena adanya gravitasi yang akan membelokkanarah peluru ke bawah, maka seharusnya dia tidakmengarahkan senapannya tepat pada sasaran.

Akan tetapi jika berasumsi bahwa pelurutersebut akan menempuh garis lurus, maka halini akan bertentangan dengan yang

sesungguhnya terjadi.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

28/31

6. Apakah sebenarnya peranan pengetahuan ?

Yakni, apakah benar-benar dibutuhkan sejumlah

besar informasi untuk memecahkan problemayang sedang dihadapi, atau pengetahuan hanyapenting untuk membatasi proses pencarian ?

Untuk memecahkan problema berikut misalnya :koran-koran mana yang mendukung masalah /

isu tertentu dan mana yang menentangnya ?.Jelas dibutuhkan banyak pengetahuan agar dapatmemperoleh solusi yang diinginkan.

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

29/31

Berbeda dengan permainan catur dimanapengetahuan hanya penting untuk membatasi

proses pencarian. Yakni cukup disajikan aturan-aturan untuk menentukan langkah-langkah yang

diperkenankan serta suatu mekanisme

pengendalian sederhana yangmengimplementasikan sebuah prosedur

pencarian yang memadai.

Pengetahuan tambahan seperti taktik dan strategiyang baik tentu saja akan membantu untuk

membatasi proses pencarian serta mempercepateksekusi program

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

30/31

7. Apakah pemecahan suatu problema

membutuhkan interaksi antara komputer

dan manusia ?

Dengan perkataan lain, apakah sebuahkomputer sendirian dapat diberi problema dankemudian menyajikan solusi secara sederhana,

atau akankah solusi dari suatu problemamembutuhkan interaksi antara komputer danmanusia ?

8/3/2019 AI_6A Problema & Pendekatan ian Masalah

31/31

Ada 2 jenis problema yang harus dibedakan :

Terkucil (solitary)

Untuk problema jenis ini, komputer diberi deskripsiproblema dan akan menghasilkan sebuah jawaban, tanpaadanya komunikasi antara dan tanpa penjelasan tentangterjadinya proses penalaran.

Bercakap-cakap (conversational)Dimana akan terjadi komunikasi antara manusia dankomputer, baik itu berupa bantuan tambahan bagikomputer atau penyajian informasi tambahan bagipemakai, atau keduanya.

Tentu saja, perbedaan ini bukanlah merupakan perbedaan

yang kaku dalam menggambarkan problema tertentu