10 October 2003 Path planning problem on weighted graph with prizes
Author Affiliations +
Proceedings Volume 5127, Sixth International Workshop on Nondestructive Testing and Computer Simulations in Science and Engineering; (2003) https://doi.org/10.1117/12.518099
Event: Sixth International Workshop on Nondestructive Testing and Computer Simulations in Science and Engineering, 2002, St. Petersburg, Russian Federation
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.
© (2003) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Sergey Zhukov, Sergey Zhukov, Mikhail Glazyrin, Mikhail Glazyrin, Pavel Kuznetsov, Pavel Kuznetsov, } "Path planning problem on weighted graph with prizes", Proc. SPIE 5127, Sixth International Workshop on Nondestructive Testing and Computer Simulations in Science and Engineering, (10 October 2003); doi: 10.1117/12.518099; https://doi.org/10.1117/12.518099
PROCEEDINGS
5 PAGES


SHARE
Back to Top