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
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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** |
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 |
Karena Goal K ditemukan di database, maka proses pencarian dihentikan. Disini terbukti bahwa K bernilai benar