Bab 4 Puan Siti Norul Huda Sheikh Abdullah Teknik ... · ♦Slot kosong / nol boleh diisi dengan...

1

Bab 4Puan Siti Norul Huda

Sheikh Abdullah

Decision Support Systems and Intelligent Systems, Efraim Turban and Jay E. Aronson6th ed, Copyright 2001, Prentice Hall, Upper Saddle River, NJ

Teknik penaakulan dan penaabiran

2

Penaakulan dalam AI♦ Pengetahuan mesti diproses (ditaakul

dengan)♦ Program komputer mencapai

pengetahuan untuk penaabiran. ♦ Enjin penaabiran atau program kawal♦ Penterjemah Petua (dalam sistem

berdasarkan petua)♦ Mengarah gelintar ke dalam pangkalan

pengetahuan.


3

Bagimana manusia taakul dan selesaikan masalah

Sumber kuasa

♦ Metod Formal (Deduksi lojikal)♦ Penaakulan Heuristik (Petua IF-THEN )♦ Fokus—pemikiran secara logik terhadap lebih

atau kurang gol yang spesifik ♦ Pecah dan Takluk (Divide and conquer)♦ Keselarian (Parallelism)


4

• Perwakilan• Analogi• Synergy• Tuah (Luck)

Lenat (1982)

Sumber kuasa diterjemah kepada penaakulan spesifik atau kaedah penaabiran (jadual 13.1)


5

Kaedah penaakulan♦ Penaakulan deduktifContohnya,Implikasi :Saya akan basah kuyup jika saya berdiri dalam hujan.Aksiom :Saya berdiri dalam hujan.

Kesimpulan:Saya akan basah kuyup.♦ Penaakulan induktifPremis: Monyet di Zoo Kuantan makan pisang.Premis: Monyet di Zoo Gombak makan pisang.

Kesimpulan: Secara umumnya, semua monyet makan pisang.

♦ Penaakulan abduktifImplikasi : Tanah adalah basah jika hari hujanAksiom : Tanah adalah basahKesimpulan : Hari hujan ?

6

Kaedah penaakulan …lainPenaakulan analogiKerangka Harimau

Kumpulan : BinatangBilangan_kaki : 4Makan : dagingTinggal : Asia Tenggara dan IndiaWarna : Berbelang keperangan

Penaakulan logik akal (common-sense)Tali kipas yang longgar akan menyebabkan bunyi bising yang

pelik.

7

Penaakulan dengan logik– Modus Ponens

– If A, then B – [A AND (A →→→→ B)] →→→→ B – A and (A →→→→ B) adalah usulan dalam

pangkalan pengetahuan– Modus Tollens: apabila B diketahui sebagai

palsu– Resolusi: menggabungkan

penambahan/penggantian (substitution) , modus ponens dan logikal ‘syllogisms’ lain .

– Syllogisms bermaksud membahas 2 penyataan untuk membuktikan penyataan ke-3 adalah benar.


8

Penaabiran petua secara rantaian hadapan dan belakang

1. Tembak satu petua: Apabilasemua hipotesis petua dipenuhi.

2. Boleh semak setiap petua dalampangkalan pengetahuan dalamarah hadapan atau belakang.

3. Ulang sehingga tiada lagi petuayang boleh ditembak atau goltelah tercapai.

9

Rantaian Hadapan dan Belakang. – Rantaian:Menghubungkan satu set

petua yang berkaitan– Proses gelintar: Diarahkan oleh satu

petua menggunakan pendekatanpenterjemah petua.

• Rantaian hadapan: apabila klausa premis sepadan dengan situasi tertentu, maka proses cuba menentukan kesimpulan.

• Rantaian belakang: sekiranya gol terkiniadalah untuk menentukan kesimpulanbenar, maka proses cuba kenalpasti sama ada klausa premis (fakta) sepadan dengansituasi tertentu.


10

Rantaian belakang

♦ Terpacu gol (Goal driven) – Bermula darikesimpulan berpotensi (hipotesis), kemudian mencari bukti-bukti yang menyokong (atau bertentangan) dengannya.

♦ Selalunya melibatkan pengiraan danmenguji hipotisis pertengahan (atau sub-hipotisis).


11

Rantaian Hadapan

♦ Terpacu data (Data driven)– Bermuladari maklumat yang diperolehisetelah mencukupi, maka cuba mencari kesimpulannya.

♦ Guna bila ?– Sekiranya semua fakta ada dahulu,

guna rantaian hadapan– Tetapi bagi masalah diagnostik –

rantaian belakang lebih baik


12

Pokok penaabiran

(Pokok gol atau Pokok logik)♦ Merupakan satu pandangan proses

penaabiran ♦ Hampir sama dengan pepokok keputusan♦ Penaabiran: tree traversal♦ Kelebihan: Menuju kepada penerangan

kenapa dan bagaimana

13

Penaabiran menggunakan kerangka

♦ Lebih kompleks dari menaakul dengan petua ♦ Slot menyediakan anggaran – pemprosesan

terpacu ♦ Slot kosong / nol boleh diisi dengan data yang

mengesahkan anggaran♦ Cari anggaran pengesahan ♦ Selalunya melibatkan pengisian nilai slot. ♦ Boleh guna petua di kerangka ♦ Penaakulan hiraki


14

Penaakulan berdasarkan model♦ Berdasarkan struktur pengetahuan dan kelakuan

sistem mesin yang direkabentuk untuk difahami. ♦ Sesuai untuk mengdiagnos masalah enjin. ♦ Boleh mengatasi sebahagian masalah

menggunakan Sistem pakar berdasarkan petua ♦ Sistem mengandungi satu (pengetahuan

mendalam) model mesin untuk mengdiagnos dimana ia boleh mencari sebab masalah enjin.

♦ Menaakul mengikut lojik akal. ♦ Selalunya digabungkan dengan perwakilan dan

penaakulan lain.


15

♦ Mudah alih♦ Merangsang struktur dan fungsi mesin

untuk mengdiagnos. ♦ Boleh jadi komponen atau matematik.♦ Amat perlu mencipta dan mengkaji satu

model sistem yang lengkap dan tepat.♦ Selalunya digunakan dalam sistem masa

nyata.


Penaakulan berdasarkanmodel..samb

16

Penaakulan Berdasarkan kes (CBR)♦ Menyesuaikan jawapan penyelesaian

lama dengan masalah baru. ♦ Variasi –Kaedah Induksi –petua ♦ Tetapi , CBR:

– Mencari kes yang hampir sama untukmenyelesaikan masalah yang sama..dan

– Menyesuaikan penyelesaian lama ataupenyelesaian yang sesuai dengan masalah terkini, sambil mempertimbangkan perbezaan antara 2 situasi.

17

Mencari kes releven yang berkaitan: – Menulis masalah input dengan menggunakan

fetur yang sesuai ke atasnya– Dapat-kembali kes yang berkaitan dengan kes

tersebut. – Pilih kes (banyak kes) yang paling padan

dengan input. – Amat sesuai dengan kes yang kompleks. – Pembaikan/perubahan – Manusia selalunya

tidak menggunakan logik (atau menaakul dariprinsipal pertama)

– Proses maklumat betul pada waktu yang betul – Masalah pusat – Mengenalpasti maklumat

sesuai apabila perlu –gunakan skrips. Decision Support Systems and Intelligent Systems, Efraim Turban and Jay E. Aronson

6th ed, Copyright 2001, Prentice Hall, Upper Saddle River, NJ

18

Apa itu Kes?♦ Kes – Menterjemahkan satu masalah dalam

ungkapan bahasa tabiee, dan menjawabkepada soalan-soalan, dan hubungkan situasi tertentu dengan dengan satu tindakan yang sesuai.

♦ Skrips – Menerangkan satu siri kejadian yang terkenal /telah diketahui– Selalunya “penaakulan menggunakan skrips” – Lebih banyak kepada skrips, kurang berfikir. – Boleh membangunkan dari kes-kes historikal. – CBR adalah gambaran bagaimana manusia

menaakul dari pengalaman.


19

Kebaikan CBR♦ Perolehan pengetahuan lebih baik, mudah

bina, senang selenggara, kurang mahal♦ Pembangunan sistem lagi cepat♦ Data dan pengetahuan yang sedia ada sentiasa

meningkat (leverage)♦ Pakar lagi sukar berbincang secara kes konkrit♦ Perolehan kes baru adalah senang♦ Pembelajaran boleh diterjadi dari kejayaan

dan kegagalan.

20

Proses CBR(Rajah 13.4)

♦ Letakkan Indeks♦ Dapat kembali♦ Kemaskini♦ Uji♦ Letakkan indeks dan simpan♦ Jelaskan, betulkan dan uji

– Pengindeksan petua

– Jenis struktur pengetahuan (Ovals)– Ingatan kes– Metriks persamaan/ Similarity Metrics– Kemaskini petua/Modification Rules– Baiki petua/ Repair Rules


21

Kegunaan, isu dan aplikasi CBR– Apabila:

• Domain adalah lemah dan tidak diketahui modelnya• Domain tidak mempunyai istilah tersendiri• Petua yang bertentangan yang digunakan dalam situasi

berbeza.– Sasaran oomain aplikasi

• Perancangan taktikal• Analysis politik• Pemantauan situasi• Perancangan undangg-2• Diagnosis• Pengecaman Ralat• Rekabentuk, configuration• Pengkelasan mesej

(Cognitive Systems, Inc.)


22

Isu dan persoalan CBR

♦ What is in a case? How can we represent case memory?♦ Automatic case-adaptation rules can be very complex♦ How is memory organized? What are the indexing rules?♦ The quality of the results is heavily dependent on the indexes

used♦ How does memory function in retrieval of relevant

information? ♦ How can we perform efficient search (knowledge navigation)

of the cases?♦ How can we organize (cluster) the cases?


Teknik Gelintaran

Bab 4Puan Siti Norul Huda Sheikh AbdullahJabatan Sains & Pengurusan SistemFTSM,UKM 2323

24

Jalan Penyelesaian ♦ Masalah: Mencari jalan dari Penang (keadaan awal) ke

Kuala Lumpur (keadaan akhir)– Mula dengan Keadaan awal– Semak sekirnaya keadaan awal merupakan keadaan akhir– Perkembangkan keadaan sekarang dengan menghasilkan set

keadaan baru– Teruskan kembangkan keadaan sehingga keadaan akhir diperolehi

♦ Proses pencarian adalah terbina dari pokok pencarian yang tertindih pada ruang keadaan.

2424

Penang

Simpang

Ipoh

Kuala Lumpur

Gerik Kulim

Kota Bahru

Kuantan

Kuala Trengganu

Baling

Raub

Sungai PetaniPenang

Simpang

Ipoh

Kuala Lumpur

Gerik Kulim

Kota Bahru

Kuantan

Kuala Trengganu

Baling

Raub

Sungai Petani

25

Pokok pencarian

25

P.Pinang(Keadaan awal)

Simpang Sungai Petani

Penang

Kulim Sungai PetaniPenang

Kulim Simpang Sungai Petani

Ipoh Baling

Penang

Kulim Simpang Sungai Petani

Ipoh Baling

Kuala Lumpur Gerik

26

Strategi Untuk Gelintar Ruang Keadaan♦ 2 cara:

– Gelintar Data Terpacu - Dari data diberi kepada gol (Data Driven Search)

• Diberi beberapa fakta dan set peraturan, oleh itu mekanisme pencarian yang menggunakan set peraturan untuk menghasilkan fakta baru yang membawa kepada jawapan (gol) Proses pencarian berjalan sehingga ia menghasilkan satu jalan dari data ke gol. Kaedah ini dipanggil ‘Rantaian Hadapan’ atau‘Forward Chaining’

– Gelintar Gol Terpacu - Dari gol patah balik ke data (Goal Driven Search)

• Diberi mekanisme pencarian gol dan ia menentukan peraturan yang betul untuk digunakan. Peraturan tersebut menjadi gol baru atau sub-gol dan mekanisme pencarian akan memenuhi sub-gol. Oleh itu, meknisme pencarian bergerak ke belakang melalui sub-gol yang berjaya dan mencari jalan balik berpandukan maklumat dari masalah tersebut. Kaedah ini dipanggil “Rantaian Belakang” atauBackward Chaining.

– Kedua-dua kaedah adalah sama kecuali cara dan bilangan keadaan mungkin berbeza. 26

27

Pemilihan strategi gelintar dalam menyelesai masalah

♦ Penyelesaian masalah yang sesuai menggunakan Pencarian gol Terpacu– Sesuatu gol atau hipotisis yang diberi mudah untuk

dikira– wujud banyak peraturan dari maklumat masalah

tersebut yang menyebabkan banyak menjanakan gol. Oleh itu, elok pilih gol dahalu dan singkirkan cabang-cabang yang boleh berlaku

• Tak semua petua dalam pembuktian teorem boleh digunakan untuk membuktikan aksiom.

– Data masalah tidak diberi tetapi penyelesai masalah diperlukan mencari data. Mekanisme pencarian akan memandu ke arah perolehan data.

• Contoh selalunya untuk mengdiagnosis sesuatu penyakit, beberapa ujian dijalankan untuk mengesahkan hipotisis tetapi doktor hanya menjalankan ujian yang perlu sahaja.

27

28

♦ Penyelesaian masalah yang sesuai menggunakan Pencarian DataTerpacu– Sekiranya semua atau kebanyakan data dinyatakan

dalam masalah tersebut– Akan terhasil potensi bilangan gol yang banyak, tetapi

hanya ada beberapa cara untuk menggunakan maklumat• contohnya kompaun organik mempunyai banyak struktur yang

boleh terjadi .Data ‘spectograpic’dalam kompaun membenarkan penyingkiran semua tetapi hanya sebahagian struktur berpontensi.

– susah untuk menjanakan gol atau hipotesis.

28

Pemilihan Strategi pencarian dalam menyelesai masalah..samb

29

Tertib gelintar ♦ Gelintar Melebar Dahulu (Breadth-First)

– Menjelajah ruang keadaan pada setiap aras. Mula, nod akar diperkembangkan, kemudian semua nod yang terjana dari nod akar akan diperkembangkan juga dan seterusnya.

– Secara amnya, semua nod pada kedalaman d akan diperkembangkan sebelum nod pada d+1

– Hanya apabila tiada keadaan untuk dijelajahi pada aras tersebut, pencarian pula bergerak pada aras yang seterusnya.

29

A

E

D

F

B

H

L

G I

K

J

S

MP

TN O Q

U

R

A,B,C,D,E,F,G,h,I,J,K,L,M,N,O,P,Q,R,S,T,U

C

30

Implimentasi Gelintar Melebar Dahulu♦ Alkhawarizmi

– buka : terdiri dai keadaan yang terjana tetapi anak-anaknya masih belum diuji

– tutup: terdiri dari keadaan yang telah diuji.Begin

buka:=[start];tutup:= [];while buka not equal [] do

begin singkirkan keadaan terkiri dari buka, panggil ia X;if X = gol then return(berjaya)else begin

janakan anak-anak X;letakkan X pada tutup;singkirkan anak-anak X pda buka atau tutup;letakkan anak-anak selebihnya ke kanan sekali pada buka;

endend

return(gagal)end. 30

31

Menjejaki Gelintar Melebar Dahulu

♦ Iterasi senarai buka senarai tutup♦ 1 [A] []♦ 2 [B,C,D] [A]♦ 3 [C,D,E,F] [B,A]♦ 4 [D,E,F,G,H] [C,B,A]♦ 5 [E,F,G,H,I,J] [D,C,B,A]♦ 6 [F,G,H,I,J,K,L] [E,D,C,B,A]♦ 7 [G,H,I,J,K,L,M] [F,E,D,C,B,A] L dah buka♦ 8 [H,I,J,K,L,M,N] [G,F,E,D,C,B,A]♦ 9 sambung sehingga terjumpa U atau buka=[]

31

U adalah gol sasaran

A

E

D

F

B

H

L

G I

K

J

S

MP

TN O Q

U

R

C

32

Gelintar Mendalam Dahulu (Depth-First)♦ Apabila satu keadaan diperiksa, setiap anak dan cucu keadaan

diperiksa terlebih dahulu sebelum keadaan lain pada aras yang sama. ♦ Gelintaran dibuat secara menegak (iaitu jauh ke dalam raung

pencarian, selagi boleh)♦ Mekanisme pencarian akan menjejak sehingga terdapat nod yang tidak

ada anak. Oleh itu, gelintar akan diteruskan kepada nod saudara kepada ibu-bapa.

♦

A

E

D

F

B

H

L

G I

K

J

S

MP

TN O Q

U

R

C

A,B,E,K,S,L,T,F,M,C,G,N,H,O,P,U,D,I,Q,J, R32

33

Implementasi Gelintar Depth-First♦ Alkhawarizmi gelintar menggunakan 2 senarai

– Buka - mengandungi keadaan yang telah dijanakan tetapi anak-anaknya belum diperiksa

– Tutup - menagndungi keadaan yang dah diperiksaBegin

buka:=[start];tutup:= [];while buka not equal [] do

beginsingkirkan keadaan terkiri dari buka, panggil ia X;if X = gol then return(berjaya)else begin

janakan anak-anak X;letakkan X pada tutup;singkirkan anak-anak X pada buka atau tutup;letakkan anak-anak selebihnya ke kiri sekali pada buka;

endend

return(gagal)end.

33

34

Menjejaki Gelintar Mendalam Dahulu (Depth-First) A

E

D

F

B

H

L

G I

K

J

S

MP

TN O Q

U

R

C

♦ Iterasi senarai buka senarai tutup♦ 1 [A] []♦ 2 [B,C,D] [A]♦ 3 [E,F,C,D] [B,A]♦ 4 [K,L,F,C,D] [E,B,A]♦ 5 [S,L,F,C,D] [K,E,B,A]♦ 6 [L,F,C,D] [S,K,E,B,A]♦ 7 [T,F,C,D] [L,S,K,E,B,A]♦ 8 [F,C,D] [T,L, S,K,E,B,A]♦ 9 [M,C,D] L tutup [F,T,L, S,K,E,B,A]♦ 10 [C,D] [M,F,T,L, S,K,E,B,A]♦ 11 [G,H,D] [C, M,F,T,L, S,K,E,B,A]♦ 12 sambung sehingga terjumpa U atau buka=[]

34

35

Perbandingan Gelintaran Melebar Dahulu & Mendalam dahulu

♦ Kebaikan– Memastikan dapat jalan

terdekat dari keadaan awal kepada gol kerana mengambil semua nod pada setiap aras sebelum pergi ke dalam.

♦ Keburukan– Memerlukan saiz ingatan

besar

♦ Kebaikan– Lagi efisen dari segi

pencarian keadaan .– Saiz ingatan kurang

♦ Keburukan– Tidak memastikan jalan

terpendek– boleh tersekat dalam

menurun ke jalan yang salah

35

36

Gelintaran Heuristik♦ Pengertian

– Merupakan satu strategi untuk mencari masalah keadaan yang dicadangkan kepada gelintaran habis-habisan (Exhaustive search)

– Satu penekaan yang diberitahu langkah yang perlu diambil dalam menyelesaikan masalah. Tekaan itu bergantung kepada pengalaman atau perasaan.

– Mengarah gelintar kepada kebarangkalian berjaya adalah tinggi

– Boleh mengarah al-khawarizmi menggelintar kepada penyelesaian sub-optimal atau gagal terus

♦ Setiap kali pakar akan selesaikan masalah, dia akan menjejaki maklumat yang diberi dan membuat keputusan. Menggunakan konsep ‘rule of thumb’ 36

37

♦ Alkharizmi heuristik mengandungi 2 bahagian– Pengukuran heuristik– alkhawarizmi yang menggunakan pengukuran heuristik untuk

mencari ruang keadaan. ♦ Panjat Bukit (Hill climbing) merupakan jalan teringkas untuk

melaksanakan gelintaran– Perkembangkan nod terkini dalam pencarian dan siasat anak-

anaknya– Anak yang terbaik dipilih untuk perkembangan yang seterusnya

(adik-beradik atau ibu-bapanya diabaikan)– Pencarian terhenti apabila mencapai keadaan yang lebih baik dari

anak-anaknya♦ contoh: Alkhawarizmi Best-First

– Menggunakan senarai untuk menyelenggarakan keadaan• Senarai buka untuk menjejaki keadaan terkini dalam pencarian• Senarai tutup untuk merekod keadaan yang telah dijelajahi.

– Heuristik juga memberitahu jarak keadaan kepada gol. Oleh itu,setiap iterasi akan mengambilkira keadaan yang paling terjamin dalam senarai buka.

Pencarian Heuristik…samb

37

38

Al-khawarizmi Best-First♦ Procedure gelintar-best-first;♦ begin

buka:=[Mula];tutup := [];while buka not equal [] do

beginalihkan keadaan ke kiri sekali dari buka, panggil ia X;if X=gol then kembali ke jalan dari Mula ke Xelse begin

janakan anak-anak X;for setiap anak X docase

anak tidak terdapat di buka atau tutup;beginJadikan anak sebagai nilai heuristik;tambah anak kepada bukaend;

anak yang terdapat di buka;if anak boleh dicapai jalan terpendek then

beri keadaan dalam buka yang jalannya terpendekanak yang terdapat di tutup;

if anak boleh dicapai jalan terpendek thenbeginsingkirkan keadaan dari tutup;tambah anak ke bukaend;

end;letak X atas tutup;susn semula keadaan dalam buka dengan merit heuristik (best leftmost)

end;return gagal

end38

39

Cara dijalankan♦ Pada setiap iterasi, Gelintaran best-first menyingkirkan

elemen pertama dari senarai terbuka. Sekiranya keadaan itu merupakan keadaan gol, al-khawarizmi akan kembali kepada jalan penyelesaian ke arah gol.

♦ Sekiranya keadaan pertama dalam buka bukan keadaan gol, alkhawarizmi akan perkembangkan keadaan anak-anak terkini.

♦ Sekiranya keadaan anak telah berada dalam buka atau tutup, al-khawarizmi akan menyemak supaya rekod keadaan adalah lebih pendek dari 2 jalan penyelesaian yang separa.

♦ Al-khawarizmi kemudian menggunakan penilaian heuristik ( semakin besar nilai semakin hampir kepada keadaan gol) pada keadaan dibuka. Senarai itu disusunmengikut nilai heuristik, di mana keadaan yang terbaik dibawa ke hadapan dalam senarai buka. 39

40

Satu Ruang Keadaan Hipotikal♦ Penilaian heuristik terdapat pada sebahagian keadaan♦ Keadaan yang dijanakan melalui gelintaran memiliki

penilaian heuristik.

♦ Keadaan yang diperkembangkan ialah garis tebal

40

A-5

D-6

F

B-4

H-3L

G I

K

J

S

M

P-3TN

O-2Q R

C-4

E -3 -5

41

Menjejaki Alkhawarizmi Gelintaran Best-First♦ Gol gelintaran Best-First ialah untuk mencari keadaan gol dengan

melihat beberapa keadaan yang wajar. Ia akan semakin wajar apabila banyak maklumat heuristik diberitahu.

P ialah keadaan golItersi Penilaian Senarai buka Senarai Tutup1 [A5] []2 A5 [B4,C4,D6] [A5]3 B4 [C4,E5,F5,D6] [B4,A5]4 C4 [H3,G4,E5,F5,D6] [C4, B4,A5]5 H3 [O2,P3,G4,E5,F5,D6] [H3, C4, B4,A5]6 O2 [P3,G4,E5,F5,D6] [O2,H3,C4,B4,A5]7 P3 PENYELESAIAN DITEMUI♦ Al-khawarizmi akan selalu memilih keadaan terbaik dalam senarai buka

untuk diperkembangkan. Namun, sekiranya heuristik membuktikan tidak benar, alkhawarizmi akan mengambil sebahagian keadaan yang ke-2 terbaik terjana dari senarai terbuka dan perkembangkan.

♦ Dalam penjejakan di atas, gelintaran mendapati bahawa anak keadaan B mempunyai penilaian yang rendah.. Oleh itu gelintaran beralih ke keadaan C.

41

42

Implimentasi fungsi Penilaian Heuristik♦ Sebahagian heuristiks wajar untuk menyelesaikan 8-puzzle

♦ Heuristik 1:Kira jubin pada setiap keadaan berbanding dengan gol. Keadaan yang mempunyai jubin keluar paling sikit adalah mungkin paling hampir kepada gol (keadaan yang terbaik untuk diperiksa selepas ini)

♦ Heuristik 2: Ambil kira jarak jubin yang mesti digerakkan unutk mencapai gol. Jumlahkan semua jarak di mana jubin berada diluar kawasan ( I untuk setiap segiempat , jubin mesti digerakkan untuk mencapai kedudukan di keadaan gol.

♦ Heuristik 3: Ambil kira situasi di mana 2 jubin perlu tukar di antara satu sama lain. Darab nombol kecil (cont 2) kali bagi setiap petukaran.

♦ Nota , lebih dari 2 pergerakan perlu dibuat . 42

2 1 387 6 5

41 2 387 6 5

4

1 2 387 6 5

4

8

2 8 317

654

2 31

76

54

2 8 317 6 5

4

2 8 317

65

4

awal akhir

43

Perbandingan Heuristik Berlainan♦ Menggunakan 3 heuristik untuk 3 keadaan anak dari mula 8-puzzle

43

2 8 317

654

82 31

76

54

2 8 317 6 5

4

2 8 317

65

4

awal5 6 0

3

5 6

4 0

0

Jubin di luar kawasan Jumlah

jarak di kawasan

22 * no apabila saling tukar

Tidak memberi ukuran tepat

Memerlukan tenaga kerja yang kurang

Gagal kerana tiada jubun yang perlu saling tukar

1 2 387 6 5

4

akhir

kiri

atas

kanan

44

♦ Kesimpulan– sukar untuk mencipta heuristik yang baik– Maklumat diberi terhad– Memperolehi corak yang baik merupakan

masalah empirikal

Perbandingan Heuristik Berlainan…samb

44

45

Mencipta Satu Fungsi Penilaian Heuristik♦ Bergantung kepada premis,

– Kalau 2 keadaan yang mempunyai penilaian heuristik yang sama, adalah lebih baik memeriksa keadaan yang hampir kepada punca graf kerana ia merupakan jalan terpendek.

– Fungsi Penilaian• f(n)=g(n) +h(n)

• di mana – g(n) mengukur panjang sesuatu jalan hakiki dari keadaan n ke

keadaan mula • setiap jarak keadaan awal dan keturunannya diambil kira

kedalamannya dengan mula kira dalam 0 dan tambah 1 bagi setiap aras ke bawah

– h(n) adalah heuristik menganggarkan jarak dari keadaan nkepada gol

• contoh: 8-puzzle h(n) boleh jadi nombor jubin di luar kawasan

45

46

Graf Pencarian Best-First bagi 8-puzzle

♦ Iterasi Senarai buka Senarai tutup♦ 1 [a4] []♦ 2 [c4,b6,d6] [a4]♦ 3 [e5,f5,g6,b6,d6] [a4,c4]♦ 4 [f5,h6,g6,b6,d6,17] [a4,c4,e5]♦ 5 [j5,h6,g6,b6,d6,k7,17] [a4,c4,e5,f5]♦ 6 [l5, h6,g6,b6,d6,k7,17] [a4,c4,e5,f5,j5]♦ 7 [m5, h6,g6,b6,d6,n7,k7,17] [a4,c4,e5,f5,j5,15]♦ 8 m = gol

8

2 8 317

654

2 31

76

54

2 8 317 6 5

4

2 8 317

65

4

awal

g(n)=0 g(n)=1

1 2 387 6 5

2

akhir6

4

6

46

47

Kesimpulan

♦ Gelintaran Best-First adalah– merupakan satu alkhawarizmi yang am untuk

pencarian heuristik pada apa-apa ruang keadaan– Sesuai untuk Gelintaran Data Terpacu dan

Terpacu gol– Membolehkan berbagai fungsi penilaian

heuristik

47

48

Analisis masalah dalam sistem cerdas

Puan Siti Norul Huda Sheikh [email protected]

49

Masalah Menara Hanoi

♦ Syarat:1. Pindah satu cakera pada satu masa2. Cakera besar tidak boleh berada di atas cakera kecilMasalah: Pindah semua cakera tiang 1 ke tiang 3

Versi mudah :

1 2 31 2 3

21 3

Keadaan awal

Keadaan akhir

49

ABC

ABC

50

Versi 2 cakera(Kedudukan tiang yg cakera A berada, kedudukan tiang yg cakera B berada)

1 2 3

BA

1 2 3 1 2 31 2 3

(11)*awal

1 2 3

A

1 2 3 1 2 3

BA

1 2 3

1 2 3

BA

1 2 3 1 2 3

B A

1 2 3

1 2 3

B A

1 2 3 1 2 3

B A

1 2 3 1 2 3

BA

1 2 3

(12)

(13)

(23)

(22)

(21)

(31) (32)

(33)akhir

A B

B

50

51

Pengoperasi

A: 1- 2 B: 1 - 2A: 1- 3 B: 1 - 3A: 2 - 1 B: 2 - 1A: 2 - 3 B: 2 - 2A: 3 - 1 B: 3 - 1A: 3 - 2 B: 3 - 2

51

52

Graf keadaan11

21 31

23

33 13

32

2212

A12

A21A31

A23

A13

A32B12

B21

A32

A23A13

A31

A12

A21

B32

B23A13

A31

A32

A23

B13

B31

A12

A21

Contoh lintasan penyelesaian 52

53

Masalah Jug-Air

♦ Diberikan 2 jug yang satu bermuatan 3-liter dan satu lagi bermuatan 4-liter. Dengan anggapan jug tidak mempunyai sebarang tanda dan air boleh dituang ke dalam/keluar jug (sumber air tidak terbatas), bagaimanakah untuk mendapati jug air 4 -liter separuh. (Berisi sebanyak 2 liter air)

– Penyelesaian:• perhatikan tindakan yang boleh membawa perubahan kandungan air

dalam jug. Penyelesaiannya melibatkan beberapa jujukan tindakan tersebut.

3-liter4-liter

53

54

No Tindakan Syarat Untuk Tindakan Petua Tindakan(x,y) : (amoun air jug 4L:3L)

1 Isi penuh J4L J4L tidak penuh {(x,y)|x<4} → (4,y)2 Isi penuh J3L J3L tidak penuh {(x,y)|y<3} → (x,3)3 Tuang sedikit air dari J4L J4L ada air {(x,y)|x>0} →(x-d,y)4 Tuang sedikit air dari J3L J3L ada air {(x,y)|y>0} →(x,y-d)5 Kosongkan J4L J4L ada air {(x,y)|x>0} →(0,y)6 Kosongkan J3L J3L ada air {(x,y)|y>0} →(x,0)7 Tuangkan air dari J3L J4L ada air dan J3L {(x,y)|x+y!4 dan y!0}

ke dlm J4L sehingga penuh ada air yg amaun cukup →(4,y)utk memenuhkan J4L

8 Tuang air dari J4L ke dlm J3L ada air dan J4L ada {(x,y)|x+y!3 dan x!0}J3L sehingga penuh air yg amaunnya cukup →(x-(3-y),3)

utk memenuhkan J3L9 Tuang semua air J3L ke J4L ada air dan J3L ada {(x,y)|x+y"4 dan y!0}

dlm J4L air yg cukup utk →(x+y,0)memenuhkan J4L

10 Tuang semua air dari J3L ada air dan J4L ada {(x,y)|x+y"3 dan x!0}J4L ke dlm J3L air yg cukup utk →(0 ,3)

memenuhkan J3L

3L 4L

Masalah Jug -Air

54

55

Masalah Jug Air …samb

(0,0)Keadaan awal1

(4,0)2

5

8

(4,3)(0,0)

(1,3)

2

(0,3)9

6

1

(3,0)(0,0)

(4,3)

Keadaan akhir (2,0)

Sebahagian ruang keadaan masalah jug air

55

56

Masalah Jug Air …samb(0,0)

(0,3)

(3,0)

(3,3)

(4,2)

(0,2)

(2,0)

Keadaan awal

Keadaan akhir 56

57

Kesimpulan♦ Memerihal masalah secara formal♦ Menakrifkan dlm bentuk perwakilan ruang

keadaan– Takrifkan persekitaran masalah sebagai

koleksi keadaan yang setiap keadaan merujuk kepada tatarajah (configuration) yang unik bagi unsur domain. Koleksi ini dipanggil Ruang Keadaan (State space).

– Takrifkan keadaan awal (mula) daripada ruang keadaan yg menggambarkan titik permulaan. Keadaan awal boleh banyak.

57

Bab 4 Puan Siti Norul Huda Sheikh Abdullah Teknik ... · ♦Slot kosong / nol boleh diisi dengan...

Documents

Transcript of Bab 4 Puan Siti Norul Huda Sheikh Abdullah Teknik ... · ♦Slot kosong / nol boleh diisi dengan...