A Note on the Connection Between the Primal-Dual and the A* Algorithm

Xugang Ye (Johns Hopkins University, USA), Shih-Ping Han (Johns Hopkins University, USA) and Anhua Lin (Middle Tennessee State University, USA)
DOI: 10.4018/978-1-4666-0933-4.ch010
Available
\$37.50
No Current Special Offers

Abstract

The primal-dual algorithm for linear programming is very effective for solving network flow problems. For the method to work, an initial feasible solution to the dual is required. In this article, we show that, for the shortest path problem in a positively weighted graph equipped with a consistent heuristic function, the primal-dual algorithm will become the well-known A* algorithm if a special initial feasible solution to the dual is chosen. We also show how the improvements of the dual objective are related to the A* iterations.
Chapter Preview
Top

Background

We consider a directed, positively weighted simple graph denoted as G = (V, A, W, δ, b), where V is the set of nodes, A is the set of arcs, W: AR is the weight function, δ > 0 is a constant such that δW(a) < +∞ for all aA, and finally b is a constant integer such that 0 < b < |V| and |{v | (u, v) ∈ A or (v, u) ∈ A}| ≤ b for all uV. Suppose we want to find a shortest s-t (directed) path in G, where sV is a specified starting node and tV is a specified terminal node. Further suppose a heuristic function exists h: VR such that h(v) ≥ 0 for all vV, h(t) = 0, and W(u, v) + h(v) ≥ h(u) for all (u, v) ∈ A. h is called consistent heuristic. According to Hart et al. (1968), Hart et al. (1972), Nilsson (1980), and Pearl (1984), the A* algorithm that uses such h is complete, that is, it can find a shortest s-t path in G as long as there exists an s-t path in G. The algorithm can be stated as follows. It searches from s to t.

Complete Chapter List

Search this Book:
Reset