Research on Optimal Path Finding Algorithm

Han Wang; Yan Piao

doi:10.4028/www.scientific.net/AMM.427-429.1883

Paper Titles

Simulation of the Underwater Target Sound Image
p.1866

CORDIC Based Fast Algorithm for Power of Two Point DCT
p.1870

Wear Particles Recognition Based on Improved LBP
p.1874

The Algorithm of Sense Disambiguation Based on Bayesian Model
p.1879

Research on Optimal Path Finding Algorithm
p.1883

TOPSIS Method for Multiple Attribute Decision Making Problem in Intuitionistic Fuzzy Setting
p.1888

Harmonic Detection Based on Genetic BP Neural Network
p.1892

Improved Isomap Algorithm Based on Supervision
p.1896

Improved LLE Algorithm Based on Supervision
p.1900

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 427-429Research on Optimal Path Finding Algorithm

Research on Optimal Path Finding Algorithm

Abstract:

Optimal path finding algorithm is a very important research direction in computer science. It is a node search method based on graph theory. This paper focus on the fundamental researches of the optimal path finding algorithm. By comparing various path finding algorithms, this paper implement the A* algorithm and present a variant strategy of A* which is named Turning Point A*(TPA*). The experiment shows that searching with TPA* can speed up A* by an order of magnitude and more and report significant improvement.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 427-429)

Pages:

1883-1887

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.427-429.1883

Citation:

Cite this paper

Online since:

September 2013

Authors:

Han Wang*, Yan Piao

Keywords:

A* Algorithm, Optimal Path Finding, TPA, Turning Point

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] Dijkstra, Edsger W. A note on two problems in connexion with graphs., Numerische mathematik 1, no. 1 (1959): 269-271.

DOI: 10.1007/bf01386390

Google Scholar

[2] Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths., Systems Science and Cybernetics, IEEE Transactions on 4, no. 2 (1968): 100-107.

DOI: 10.1109/tssc.1968.300136

Google Scholar

[3] Botea, Adi, Martin Müller, and Jonathan Schaeffer. Near optimal hierarchical path-finding., Journal of game development 1, no. 1 (2004): 7-28.

Google Scholar

[4] Pochter, Nir, Aviv Zohar, Jeffrey S. Rosenschein, and Ariel Felner. Search space reduction using swamp hierarchies., In Third Annual Symposium on Combinatorial Search. (2010).

DOI: 10.1609/socs.v1i1.18156

Google Scholar

[5] Yap, Peter, Neil Burch, Rob Holte, and Jonathan Schaeffer. Block A*: Database-driven search with applications in any-angle path-planning., InProceedings of the AAAI Conference on Artificial Intelligence. (2011).

DOI: 10.1609/aaai.v25i1.7813

Google Scholar

[6] Pearl, Judea. Heuristics: intelligent search strategies for computer problem solving., (1984).

Google Scholar