Algoritma backward chaining atau runut balik adalah salah satu algoritma pada sistem pakar.

Menurut saya cukup membingungkan apabila dibandingkan dengan algoritma forward chaining / runut maju, namun saya yakin dengan memperhatikan pola pengerjaan, algoritma ini cukup mudah dipahami.

Kunci algoritma ini adalah pada premis dan konklusi, layaknya forward chaining, perbedaanya adalah algoritma backward chaining memeriksa konklusi (THEN ..) terlebih dahulu, yang kemudian dicari premisnya (IF ..). Dan tidak lupa, algoritma backward chaining menggunakan stack untuk penyimpanan memori sementara.

Contoh Kasus

## Aturan/rules basis pengetahuannya

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K

Fakta awal yang diberikan adalah A dan F, buktikan apakah K bernilai benar apabila proses inferensi dilakukan dengan cara backward chaining?

Jawab

Langkah 1

Database: A F
Stack: K

Goal: K (sebagai isi awal dari stack). J tidak ada di database, simpan di stack.

Langkah 2

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN **J**
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F
Stack: K J

Sub goal: J

A ada di Database. I tidak ada di Database (simpan di stack).

Langkah 3

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN **I**
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F
Stack: K J I

Sub goal: I

C tidak ada di database (simpan di stack). H tidak ada di database (simpan di stack).

Langkah 4

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN **H**
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F
Stack: K J I C H

Sub goal: H

G tidak ada di database (simpan di stack). E tidak ada di database (simpan di stack).

Langkah 5

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F
Stack: K J I C H G E

Sub goal: E

Aturan dengan konklusi E tidak ada (yang berarti gagal), maka kembali ke langkah ke 2 (namun kita akan memakai R9 dari pada R8).

Langkah 6 (perulangan dari langkah 2)

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN **J**
R10 : IF J THEN K
Database: A F
Stack: K J

Sub goal: J

G tidak ada di database (simpan di stack).

Langkah 7

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN **G**
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F
Stack: K J G

Sub goal: G

A ada di database. G masukkan ke database.

Langkah 8

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN **J**
R10 : IF J THEN K
Database: A F G
Stack: K J

Sub goal: J

G ada di database. J masukkan ke database.

Langkah 9

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN **K**
Database: A F G J
Stack: K

Sub goal: K

J ada di database. K masukkan ke database.

Langkah 10

R1 : IF ( A AND B) THEN C
R2 : IF C THEN D
R3 : IF (A AND E) THEN F
R4 : IF A THEN G
R5 : IF (F AND G) THEN D
R6 : IF (G AND E) THEN H
R7 : IF (C AND H) THEN I
R8 : IF (I AND A) THEN J
R9 : IF G THEN J
R10 : IF J THEN K
Database: A F G J K
Stack: (kosong)

Karena Goal K ditemukan di database, maka proses pencarian dihentikan. Disini terbukti bahwa K bernilai benar

comments powered by Disqus

Ubah CapsLock Jadi ESC dan Sekaligus Ctrl

Saya adalah pengguna Vim. Bila ada perang sipil antara Vim dan Emacs, secara otomatis saya akan jadi salah satu tentara Vim, anak buah om...… Continue reading

Ketika Mount Gagal dan Masuk Mode Read-Only

Published on March 26, 2016

Cara Install Gentoo

Published on March 04, 2016