Есть неориентированный полный граф. Значения длины всех ребер заданы. Необходимо добавить вершину к графу или использовать уже существующую. Причем эта вершина должна иметь такое значение ребер, что бы начиная обход графа с нее, можно было обойти все вершины графа и длина пути обхода - минимальная.
Прошу, помогите ответом. Мне подойдет как полностью раскрытый ответ, так и ссылка на источник с материалом по вышеописанной теме или даже небольшой намек: "в какую сторону копать"...
Ответ
Это задача о поиске кратчайшего гамильтонова пути. Так как граф полный, то очевидно не имеет смысла добавлять новую вершину - она только увеличит длину пути, также очевидно что такой путь всегда существует. Решение с помощью обхода в глубину будет давать неполиномиальную асимптотику. Посмотри в сторону переборов с отсечениями ...
Комментариев нет:
Отправить комментарий