Welcome to the InfoSci Platform
Reference Hub1
A Note on the Connection Between the Primal-Dual and the A* Algorithm

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

Xugang Ye, Shih-Ping Han, Anhua Lin
Copyright: © 2012 |Pages: 12
ISBN13: 9781466609334|ISBN10: 1466609338|EISBN13: 9781466609341
DOI: 10.4018/978-1-4666-0933-4.ch010
Cite Chapter Cite Chapter

MLA

Ye, Xugang, et al. "A Note on the Connection Between the Primal-Dual and the A* Algorithm." Innovations in Information Systems for Business Functionality and Operations Management, edited by John Wang, IGI Global, 2012, pp. 170-181. https://doi.org/10.4018/978-1-4666-0933-4.ch010

APA

Ye, X., Han, S., & Lin, A. (2012). A Note on the Connection Between the Primal-Dual and the A* Algorithm. In J. Wang (Ed.), Innovations in Information Systems for Business Functionality and Operations Management (pp. 170-181). IGI Global. https://doi.org/10.4018/978-1-4666-0933-4.ch010

Chicago

Ye, Xugang, Shih-Ping Han, and Anhua Lin. "A Note on the Connection Between the Primal-Dual and the A* Algorithm." In Innovations in Information Systems for Business Functionality and Operations Management, edited by John Wang, 170-181. Hershey, PA: IGI Global, 2012. https://doi.org/10.4018/978-1-4666-0933-4.ch010

Export Reference

Mendeley
Favorite

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.