T*: a weighted double-heuristic search algorithm to find the shortest path Online publication date: Wed, 30-Jan-2019
by Mohammad Samadi Gharajeh
International Journal of Computing Science and Mathematics (IJCSM), Vol. 10, No. 1, 2019
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.
Online publication date: Wed, 30-Jan-2019
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computing Science and Mathematics (IJCSM):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email firstname.lastname@example.org