T*: a weighted double-heuristic search algorithm to find the shortest path (Q2224337)

Summary: 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) = \alpha \times t(x) + \beta \times h1(x) + \gamma \times 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, \(\alpha, \beta\), and \(\gamma\) 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.