Representasi Pengetahuan Logika Predikat

Logika Predikat adalah perluasan dari logika proposisi dimana objek yang di bicarakan dapat berupa anggota kelompok. Misalkan P(x) merupakan sebuah pernyataan yang mengandung variabel x dan D adalah sebuah himpunan. Kita sebut P sebuah fungsi proposisi (dalam D) jika untuk setiap x di D, P(x) adalah proposisi. Kita sebut D daerah asal pembicaraan (domain of discourse) dari P.

A.      FUNGSI FUNGSI LOGIKA PREDIKAT

Berikut ini beberapa contoh fungsi proposisi:

1.       n² + 2n adalah bilangan ganjil, dengan daerah asal himpunan bilangan bulat.

2.       x² – x – 6 = 0, dengan daerah asal himpunan bilangan real.

3.       Seorang pemain bisbol memukul bola melampaui 300 pada tahun 1974, dengan daerah asal himpunan pemain bisbol.

Sebuah predikat seringkali menyatakan sebuah hubungan relasional antara: konstanta, variabel dan fungsi.

B.      LOGIKA DAN SET ORDER PERTAMA

Logika Predikat Order Pertama disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form).

Logika orde pertama adalah sistem resmi yang digunakan dalam matematika , filsafat ,linguistik , dan ilmu komputer . Hal ini juga dikenal sebagai orde pertama predikat kalkulus, semakin rendah kalkulus predikat, teori kuantifikasi, dan logika predikat. Logika orde pertama dibedakan dari logika proposisional oleh penggunaan variabel terukur .

Syarat-syarat symbol dalam logika predikat :

·         himpunan huruf, baik huruf kecil maupun huruf besar dalam abjad.

·         Himpunan digit (angka) 0,1,2,…9

·         Garis bawah “_”

·         Symbol-simbol dalam logika predikat dimulai dengan sebuah huruf dan diikuti oleh sembarang rangkaian karakter-karakter yang diijinkan.

·         Symbol-simbol logika predikat dapat merepresentasikan variable, konstanta, fungsi atau predikat

Logika Predikat Order Pertama terdiri dari :

Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali dengan huruf kecil, seperti : pohon, tinggi. Konstanta true(benar) dan false(salah) adalah symbol kebenaran (truth symbol).

Variable : digunakan untuk merancang kelas objek atau sifat-sifat secara umum dalam semesta pembicaraan. Penulisannya diawali dengan huruf besar, seperti : Bill, Kate.

Fungsi : pemetaan (mapping) dari satu atau lebih elemen dalam suatu himpunan yang disebut domainfungsi ke dalam sebuah elemen unik pada himpunan lain yang disebut rangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.

Argument :elemen-elemen dari fungsi, ditulis diapit tanda kurung dan dipisahkan dengan tanda koma.

Predikat: menamai hubungan antara nol atau lebih objek dalam semesta pembicaraan. Penulisannya dimulai dengan huruf kecil, seperti : equals, sama dengan, likes, near.

Contoh kalimat dasar :

teman(george,allen)

teman(ayah_dari(david),ayah_dari(andrew))

dimana:

argument : ayah_dari(david) adalah george

argument : ayah_dari(andrew) adalah allen

predikat : teman

C.      QUANTIFIER UNIVERSAL

Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .

Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.

Contoh 1 :

(∀x) (x + x = 2x)

“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”

Contoh 2 :

(∀x) (p) (Jika x adalah seekor kelinci -> x adalah binatang).

Kebalikan kalimat “bukan kelinci adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kelinci -> ~x adalah binatang)

dan dibaca :

– “setiap kelinci adalah bukan binatang”

“semua kelinci adalah bukan binantang”

D.      QUANTIFIER EXISTENSIAL

Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .

Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.

Contoh 1 :

(∃x) (x . x = 1)

Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :

(∃x) (panda(x) ∧ nama(Clyde))

Dibaca : “beberapa panda bernama Clyde”.

Contoh 3 :

(∀x) (jerapah(x) -> berkaki empat(x))

Dibaca : “semua jerapah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (jerapahh(x) ∧ berkaki tiga(x))

Dibaca : “ada jerapah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

E.       RESOLUSI LOGIKA PREDIKAT

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :

1.       Konversikan semua proposisi F ke bentuk klausa

2.       Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan   kehimpunan klausa yang telah ada pada langkah

3.       Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :

Seleksi 2 klausa sebagai klausa parent

Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut  resolvent. Jika ada pasangan literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent

Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada

Contoh kasus :

Misalkan terdapat pernyataan-pernyataan sebagai berikut :

1.       Fajar adalah seorang mahasiswa

2.       Fajar masuk Jurusan Elektro

3.       Setiap mahasiswa elektro pasti mahasiswa Teknik

4.       Kalkulus adalah matakuliah yang sulit

5.       Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya

6.       Setiap mahasiswa pasti akan suka terhadap suatu matakuliah

7.       Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut

8.       Fajar tidak pernah hadir kuliah matakuliah kalkulus

Maka harus terlebih dahulu diubah ke dalam bentuk klausa sebagai berikut :

1.       Mahasiswa (Fajar)

2.       Elektro (Fajar)

3.       Elektro (x1) v Teknik (v1)

4.       Sulit (Kalkulus)

5.       Teknik (x2) v suka (x2, Kalkulus) v benci (x2, Kalkulus)

6.       Suka (x3, f1 (x3))

7.       Mahasiswa (x4) v ¬ sulit (y1) v hadir (x4, y1) v ¬ suka (x4, y1)

8.       Hadir (Fajar, Kalkulus)

Referensi

https://ismailakbar12.wordpress.com/2015/06/25/makalah-artifical-intellegent-representasi-pengetahuan/

http://pakarbelajar.blogspot.co.id/2009/08/5-fungsi-predikat-dan-kalimat.html

http://afifrahma.blogspot.co.id/2013/01/resolusi-untuk-logika-predikat.html

Read More

Representasi Pengetahuan Logika Proporsi

Logika dan Set

Representasi pengetahuan dengan symbol logika merupakan bagian dari penalaran eksak.

Bagian yang paling penting dalam penalaran adalah mengambil kesimpulan dari premis.

Logika dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premisdan satu konklusi.

Contoh :

Premis : Semua laki-laki adalah makhluk hidup

Premis : Socrates adalah laki-laki

Konklusi : Socrates adalah makhluk hidup

Cara lain merepresentasikan pengetahuan adalah dengan Diagram Venn. 

 

Diagram Venn merepresentasikan sebuah himpunan yang merupakan kumpulan objek.

Objek dalam himpunan disebut elemen.

A ={1,3,5,7}

B = {….,-4,-2,0,2,4,…..}

C = {pesawat, balon}

Symbol epsilon εmenunjukkan bahwa suatu elemen merupakan anggota dari suatu himpunan, contoh : 1 εA . Jika suatu elemen bukan anggota dari suatu himpunan maka symbol yang digunakan ∉, contoh : 2 ∉A.

Jika suatu himpunan sembarang, misal X dan Y didefinisikan bahwa setiap elemen X merupakan elemen Y, maka X adalah subset dari Y, dituliskan : X ⊂ Y atau Y ⊃ X.

Operasi-operasi Dasar dalam Diagram Venn:

Interseksi (Irisan)

 

C = A ∩B

C = {x ∈ U | (x ∈ A) ∧(x ∈ B)}

Dimana : ∩ menyatakan irisan himpunan| dibaca “sedemikian hingga”∧operator logika AND

Union (Gabungan) 

 

C = A ∪ B

C = {x ∈ U | (x ∈ A) ∨(x ∈ B)} 

Dimana : ∪ menyatakan gabungan himpunan∨operator logika OR

Komplemen

 

A’ = {x ∈ U | ~ (x ∈ A) } 

Dimana : ’ menyatakan komplemen himpunan

~ operator logika NOT

Operator Logika

Operator logika yang digunakan :

 

Kondisional merupakan operator yang analog dengan production rule.

Contoh 1 :

“ Jika hujan turun sekarang maka saya tidak pergi ke pasar”

Kalimat di atas dapat ditulis : p → q

Dimana : p = hujan turun

q = saya tidak pergi ke pasar

Contoh 2 :

p = “Anda berusia 21 atau sudah tua”

q = “Anda mempunyai hak pilih”

Kondisional p → q dapat ditulis/berarti :

 

Tautologi, Kontradiksi dan Contingent

Tautologi : pernyataan gabungan yang selalu bernilai benar.

Kontradiksi : pernyataan gabungan yang selalu bernilai salah.

Contingent : pernyataan yang bukan tautology ataupun kontradiksi.

Tabel Kebenaran untuk logika konektif :

 

Tabel kebenaran untuk negasi konektif : 

 

Resolusi Logika Proposisi

Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.

Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.

Algoritma resolusi :

(1) Konversikan semua proposisi F ke bentuk CNF.

(2) Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.

(3) Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :

a. Seleksi 2 klausa sebagai klausa parent.

b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.

c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.

Contoh :

Diketahui basis pengetahuan (fakta-fakta yang bernilai benar) sebagai berikut:

1. P

2. (P ∧ Q) → R

3. (S ∨ T) → Q

4. T

Buktikanlah kebenaran R!

Pertama-tama kita harus ubah dulu keempat fakta di atas menjadi bentuk CNF. Konversi ke CNF dapat dilakukan sebagai berikut:

 

Kemudian kita tambahkan kontradiksi pada tujuannya, R menjadi ￢R sehingga fakta-fakta (dalam bentuk CNF) dapat disusun menjadi:

1. P

2. ￢P ∨ ￢Q ∨ R

3. ￢S ∨ Q

4. ￢T ∨ Q

5. T

6. ￢R

Dengan demikian resolusi dapat dilakukan untuk membuktikan R sebagaimana terlihat pada Gambar berikut: 

  

Contoh apabila diterapkan dalam kalimat:

P : Andi anak yang cerdas.

Q : Andi rajin belajar.

R : Andi akan menjadi juara kelas.

S : Andi makannya banyak.

T : Andi istirahatnya cukup.

Kalimat yang terbentuk (basis pengetahuan) menjadi :

1. P : Andi anak yang cerdas.

2. (P ∧ Q) → R : Jika Andi anak yang cerdas dan Andi rajin belajar, maka Andi akan menjadi juara kelas.

3. (S ∨ T) → Q : Jika Andi makannya banyak atau Andi istirahatnya cukup, maka Andi rajin belajar.

4. T : Andi istirahatnya cukup.

Setelah dilakukan konversi ke bentuk CNF, didapat:

1. P : Andi anak yang cerdas.

2. ￢P ∨ ￢Q ∨ R : Andi tidak cerdas atau Andi tidak rajin belajar atau Andi akan menjadi juara kelas.

3. ￢S ∨ Q : Andi tidak makan banyak atau Andi rajin belajar.

4. ￢T ∨ Q : Andi tidak cukup istirahat atau Andi rajin belajar.

5. T : Andi istirahatnya cukup.

6. ￢R : Andi tidak akan menjadi juara kelas.

Pohon aplikasi resolusi untuk kejadian di atas sebagai berikut :

  

Referensi

https://www.google.com/urlsa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwiXmuvjqq3QAhXKvY8KHeS_DkIQFgggMAE&url=http%3A%2F%2Fsupriyan.staff.gunadarma.ac.id%2FDownloads%2Ffiles%2F11876%2F5RepresentasiPengetahuanLOGIKA.pdf&usg=AFQjCNGz5Owl96L1dlKqejEc6y8TDVqwow&sig2=gRnlDxO13L9iVOCNTbmG3g&cad=rjaslametgo-blog.blogspot.com/2016/01/resolusi-logika-proposisi.html

Read More

Representasi Pengetahuan

Representasi pengetahuan adalah cara untuk menyajikan pengetahuan yang diperoleh ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi antara suatu pengetahuan dengan pengetahuan yang lain dan dapat dipakai untuk menguji kebenaran penalarannya.

Secara teknik kita akan membahas representasi pengetahuan menjadi lima kelompok:

1.       Representasi Logika

2.       Jaringan Semantik

3.       Frame

4.       Script (Naskah)

5.       Aturan Produksi (Kaidah Produksi)

A.      Representasi Logika

Logika didefinisikan sebagai ilmu untuk berpikir dan menalar dengan benar sehingga didapatkan kesimpulan yang absah.

Tujuan dari logika: memberikan aturan-aturan penalaran sehingga orang dapat menentukan apakah suatu kalimat bernilai benar atau salah.

Representasi Logika dibagi menjadi dua:

a.       Propositional Logic (Logika Proposisi)

Suatu Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE). Dalam Propositional Logic fakta dilambangkan dengan simbol misalnya P, Q dan R. Lambang-lambang tersebut dihubungkan dengan relasi-relasi logika

Dengan menggunakan operator logika:

Tabel Kebenaran Logika

b.      Predicate Logic (Logika Predikat)

Pada logika predikat proposisi dibedakan menjadi argumen (obyek) dan predikat (keterangan). Secara umum penulisan proposisi dalam logika predikat dapat dinyatakan sebagai berikut:

Predikat (argumen-1, argumen-2,..., argumen-3)

Contoh:

Proposisi: “Bu Atika mencintai Pak Agus Setiawan”

Dalam logika predikat disajikan dalam bentuk:

Mencintai (Bu Atika, Pak Agus Setiawan)

      P         Argumen-1            Argumen-2

Contoh Silsilah Keluarga yang dipresentasikan dalam Prolog

Jika silsilah di atas dibentuk dalam Representasi Logika, sebagai berikut:

Orangtua (Komarudin, Andika)

Orangtua (Komarudin, Atika)

Orangtua (Komarudin, Agus)

Orangtua (Andika, Rika)

Orangtua (Atika, Anjar)

B.      Jaringan Semantik

Pengetahuan disusun dalam sebuah jaringan yang memiliki komponen utama:

-            Node: menyatakan obyek, konsep, atau situasi. Dinyatakan dengan kotak atau lingkaran

-            Arcs/Link: Menyatakan hubungan antar node. Dinyatakan dengan tanda panah.

C.      Frame

Frames: merupakan semantic net dilengkapi dengan properties. Suatu Frame menggambarkan entitas sebagai set dari attribute dan nilai yang bersesuaian. Suatu frame dapat berelasi dengan frame yang lainnya.

Tiga komponen utama dari frame

•         frame name

•         attributes (slots)

•         values (subslots)

Book Frame

Slot -> Subslots

Title     -> AI. A modern Approach Author -> Russell & Norvig Year   ->  2003

Contoh di atas dibentuk dalam Frame:

Nama Frame: Burung
Orangtua	Hewan
Anak	Kenari, Pipir
Mempunyai	Saya
Cara Berpindah Tempat	Terbang

D.      Script (Naskah)

Conceptual Dependency (ketergantungan konseptual) adalah teori tentang bagaimana mempresentasikan pengetahuan tentang event (kejadian) yang biasanya terkandung dalam kalimat bahasa natural.

Contoh: representasi Conceptual Dependency

“Budi memberi Atika sebuah buku”

Script adalah skema representasi pengetahuan yang menggambarkan urutan-urutan kejadian (sequence of events). Script dilengkapi dengan elemen-elemen agar lebih memudahkan dalam memahami urutan kejadian.

1.       Track/Jalur: variasi yang mungkin terjadi dalam script

2.       Kondisi Input: situasi yang harus dipenuhi sebelum sesuatu kejadian terjadi

3.       Prop/Pendukung: objek pendukung yang digunakan dalam urutan peristiwa yang  terjadi

4.       Role/Peran: orang-orang yang terlibat dalam suatu peran

5.       Scene/Adegan: urutan peristiwa aktual

6.       Hasil: kondisi akhir yang terjadi setelah urutan peristiwa dalam script terjadi

E.       Aturan Produksi (Kaidah Produksi)

Pengetahuan dalam kaidah produksi direpresentasikan dalam bentuk

       JIKA [kondisi] MAKA [Aksi]

       JIKA [premis] MAKA [Konklusi]

Aturan Produksi (kaidah produksi) adalah salah satu representasi pengetahuan yang menghubungkan premis dengan konklusi.

Bentuknya: If Premis Then Konklusi

Konklusi pada bagian then bernilai benar jika premis pada bagian if bernilai benar.

Contoh:

If  hari ini hujan then saya tidak kuliah.

Materi ini saya dapatkan  dari Dosen mata kuliah Kecerdasan Buatan

Referensi:

http://lutfiatulm.blogspot.co.id/2013/03/representasi-pengetahuan.html

Read More

Metode Pencarian dan Pelacakan 2 (Heuristik)

·     Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan(completeness).

·  Fungsi heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

·        Jenis-jenisHeuristic Searching:

§                            -Generate and Test.

§                            - Hill Climbing.

§                            -Best First Search.

§                            -Alpha Beta Prunning,Means-End-Anlysis,ConstraintSatisfaction, Simulated Annealing, dll.

Pembangkitan dan Pengujian (Generate and Test)

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu ke adaan awal.

Algoritma:

1.       Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

2.       Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

3.       Jika solusi ditemukan, keluar. Jikatidak, ulangi kembali langkah pertama.

Contoh : “Travelling Salesman Problem (TSP)”.Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :Pencarianke-Lintasan-PanjangLintasan-LintasanTerpilih-PanjangLintasanTerpilih

ReduksiMasalah

·         Kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awa lsampai tujuan tidak terletak pada satu cabang.

·         Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

·         Graf AND-OR

·         Graf AO*

A.      Graf AND-OR

·         Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND.

·         Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.

·         Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi Goal.

B.      AlgoritmaAND-OR

1.       Inisialisasi graf ke node awal.

2.       Kerjakan langkah2 berikut hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY :

·         Telusuri graf mulai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tsb. dan belum pernah diekspansi atau diberilabel SOLVED.

·         Ambil satu node dan ekspansi node tsb. Jika tidak ada successor maka set F_UTILITY sebaga i nilai dari node tsb. Bila tidak demikian, tambahkans uccessor dari node tsb ke graf dan hitung nilai setiap f’(hanya gunakan h’dan abaikang). Jika f’=0 tandai node tsb dengan SOLVED.

·         Ubah f’ harapan dari node baru yang diekspansi. Kirim kan perubahan ini secara backward sepanjang graf. Jika node berisi suatu arc successor yang semua descendantnya berlabel SOLVED maka tandai node itudenganSOLVED.

Pencarian Terbaik Pertama (Best-First Search)

Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Pada metodebest-first search, pencarian diperbolehkan mengunjungi node yang ada dilevel yang lebih rendah, jika ternyat anode pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristikyang digunakanmerupakanprakiraan(estimasi) cost dariinitial statekegoal state, yang dinyatakandengan:

f’(n) = g(n) + h’(n)

dimanaf’= Fungsievaluasi

g = cost dariinitial statekecurrent state

h’= prakiraancost daricurrent stateke

goal state

https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/

hendrik.staff.gunadarma.ac.id/.../teknik-pencarian-heuristik.pdf

Read More