Title: T*: a weighted double-heuristic search algorithm to find the shortest path

Authors: Mohammad Samadi Gharajeh

Addresses: Young Researchers and Elite Club, Tabriz Branch, Islamic Azad University, Tabriz, Iran

Abstract: This paper proposes a weighted double-heuristic search algorithm to find the shortest path between two points. It can be used in numerous fields such as graph theory, game theory, and network. This algorithm, called T*, uses a weighted and heuristic function as f(x) = α × t(x) + β × h1(x) + γ × h2(x). It selects the path which minimises f(x) where x is a current node on the path, t(x) is cost of the path from start to x, h1(x) is a heuristic to estimate the cost from x to the straight line passing through start and target, and h2(x) is a heuristic to estimate cost of the cheapest path from x to target. Furthermore, α, β, and γ indicate effective weights of each sub-function on f(x). T* algorithm is compared to the Greedy and A* algorithms in terms of hit rate and the number of processed nodes. Comparison results show that the proposed algorithm has a high efficiency compared to other algorithms.

Keywords: shortest path; search algorithm; weighted strategy; double-heuristic function; graph theory.

DOI: 10.1504/IJCSM.2019.097636

International Journal of Computing Science and Mathematics, 2019 Vol.10 No.1, pp.58 - 70

Accepted: 19 Jul 2017
Published online: 04 Feb 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article