Traveling tourist problem: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Traveling tourist problem''' --- задача о туристе. Given a graph <math>G = (V,E)</math>, find the shortest walk visiting a subset of vertices, suc…») |
(нет различий)
|
Текущая версия от 17:07, 16 августа 2011
Traveling tourist problem --- задача о туристе.
Given a graph [math]\displaystyle{ G = (V,E) }[/math], find the shortest walk visiting a subset of vertices, such that each vertex is either visited, or has at least one of its neighbors visited. The vertices of the graph correspond to monuments the tourist would like to see, and an edge between two vertices denotes visibility of one monument from another. The shortest such walk would guarantee that the tourist sees all monuments of interest.