Pengaruh Fungsi Heuristik Terhadap Nilai Optimum Global pada Pencarian Jalur Terpendek

Abstract

Determination of optimum routes often result different values. This is caused by the methods used have different calculations. The purpose of the optimum route itself is to find the best trajectory of the two pairs of vertices contained in a map or graph. We have applied A* algorithm for the test. This algorithm has the evaluation function to assist the search. The function is called heuristic. Two methods which have been introduced as a step to obtain the value of heuristic function are by using Euclidean and Manhattan distance. Both of these methods has resulted the optimum distance in shortest path problem, but these functions gain the different results. So we have develoved a research on the heuristic function using Euclidean, Manhattan, Euclidean Square and using a new method (ANDYSAH) to compare the results.

Penentuan rute optimum sering menghasilkan nilai yang berbeda. Ini disebabkan oleh metode yang digunakan mempunyai perhitungan yang berbeda-beda. Tujuan dari rute optimum itu sendiri adalah untuk mencari lintasan terbaik dari 2 pasang verteks yang terdapat pada suatu peta atau graph. Algoritma pencarian yang diterapkan pada pengujian adalah A*. Algoritma ini mempunyai fungsi evaluasi yang berfungsi untuk membantu pencarian, yaitu fungsi heuristik. Untuk mendapatkan nilai optimum global bergantung pada kinerja fungsi. Dua buah metode yang telah diperkenalkan sebagai langkah untuk mendapatkan nilai fungsi heuristik, antara lain dengan menggunakan jarak Euclidean dan jarak Manhattan. Kedua metode ini telah menghasilkan jarak yang optimum pada permasalahan shoretest path, tetapi kedua fungsi ini menghasilkan jarak yang berbeda. Dengan itu, telah dilakukan penelitian terhadap fungsi heuristik dengan menggunakan metode Euclidean, Manhattan, Euclidean Kuadrat dan dengan menggunakan metode yang baru (ANDYSAH).