6. pencarian heuristik-a

Fungsi Heuristic:

• Suatu fungsi heuristic dikatakan baik jika bisamemberikan biaya perkiraan yang mendekatibiaya sebenarnya.

• Semakin mendekati biaya sebenarnya, fungsiheuristic tersebut semakin baik.

Ada 2 jenis pencarian terbaik pertama(Best First Search), yaitu:

1. Greedy Best First Search2. Algoritma A*

Greedy Best First Search

• Algoritma ini merupakan jenis algoritma Best First Search yang paling sederhana. Algoritmaini hanya memperhitungkan biaya perkiraansaja,

• Karena hanya memperhitungkan biayaperkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.

CONTOH

Kesimpulan:

• Dari contoh di atas, Greedy akan menemukansolusi S-B-K-G dengan total jarak = 105

• Padahal ada solusi lain yang lebih optimal yakni: S-A-B-F-K-G dengan total jarak hanya 95

Algoritma A*

• Berbeda dengan Greedy, algoritma ini akanmenghitung fungsi heuristic dengan caramenambahkan biaya sebenarnya denganbiaya perkiraan. Sehingga didapatkan rumus:

• g(n) = biaya sebenarnya dari Node awal kenode n

• h’(n) = biaya perkiraan dari Node n ke node tujuan

Contoh

Perbandingan Greedy Best First Search dengan Algoritma A*

• Greedy tidak bisa menemukan solusi yang optimal

• Algoritma A* dapat menemukan solusi yang optimal

• Algiritma A* lebih baik dalam melakukanpencarian heuristic daripada Greedy Best First Search karena dapat mendapatkan solusi yang optimal.

Contoh terdapat dalam file lain