Share Email Print
cover

Proceedings Paper

Path planning problem on weighted graph with prizes
Author(s): Sergey Zhukov; Mikhail Glazyrin; Pavel Kuznetsov
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

In this article we formalize and consider the path-planning problem on the weighted graph with prizes (PCPP - prize collecting path-planning). It is generalized travel salesman problem on graph with prizes. We give the formal statement of the PCPP problem and prove that it is NP-hard. We developed the algorihtm to resolve the PCPP problem exactly if graph is a tree and proposed several heuristics based on this algorithm to resolve the problem in common case.

Paper Details

Date Published: 10 October 2003
PDF: 5 pages
Proc. SPIE 5127, Sixth International Workshop on Nondestructive Testing and Computer Simulations in Science and Engineering, (10 October 2003); doi: 10.1117/12.518099
Show Author Affiliations
Sergey Zhukov, St. Petersburg State Technical Univ. (Russia)
Mikhail Glazyrin, St. Petersburg State Technical Univ. (Russia)
Pavel Kuznetsov, St. Petersburg State Technical Univ. (Russia)


Published in SPIE Proceedings Vol. 5127:
Sixth International Workshop on Nondestructive Testing and Computer Simulations in Science and Engineering
Alexander I. Melker, Editor(s)

© SPIE. Terms of Use
Back to Top