Вершинный тур по взвешенному неориентированному графику с максимальной стоимостью?

Question

Каковы эффективные алгоритмы поиска обхода вершины во взвешенном неориентированном графе с максимальной стоимостью, если нам нужно начать с определенной вершины?

Answer 1

Поскольку проблема NP-трудна, вы вряд ли найдете эффективный алгоритм, который решает проблему точно для всех возможных взвешенных входных графов.

Однако могут существовать эффективные алгоритмы, которые гарантированно найдутответ, который находится не более чем в постоянные моменты времени от наилучшего возможного ответа, например, может существовать эффективный алгоритм, который гарантированно найдет путь, вес которого не менее 1/2 от пути максимального веса.

Если вы заинтересованы в поиске таких алгоритмов, вы можете попробовать поискать в Google «алгоритм аппроксимации взвешенных гамильтоновых путей», который близок, но не идентичен вашей проблеме.Это не то же самое, потому что гамильтоновы пути должны включать все вершины.Вот одна исследовательская работа, которая может содержать или иметь идеи, которые приводят к алгоритму аппроксимации для вашей задачи:

http://portal.acm.org/citation.cfm?id=139404.139468

«Общая методика аппроксимации для задач с ограниченным лесом»Мишель X. Гоманс и Дэвид П. Уильямс.

Конечно, если ваши графы достаточно малы, чтобы вы могли перечислить все возможные пути, содержащие желаемую вершину, «достаточно быстро для ваших целей», то вы можете точно ее решить..

Answer 2

Это NPC, потому что если вы установите веса равными 1 для всех ребер, если HC существует, это будет вашим ответом, и поэтому Во всех вы можете найти существование HC из одного источника, который является NPC, решая эту проблему, поэтому ваша проблема - NPC , но есть некоторые алгоритмы полиномиальной аппроксимации.