У меня есть пространственная карта США, соединяющая города с весами (расстояниями). Я хотел бы найти самую длинную (наиболее взвешенную) трассу на этой карте.
НЕТ требования, чтобы все узлы или ребра были посещены.
Предложения ресурсов метода и пролога будут в порядке.
Я не знаю, прав ли я, но вы можете попробовать следующее:
Вы можете проверить, является ли граф эйлеровым. Если это так, ваша проблема состоит в том, чтобы найти схему Эйлера, которая может быть выполнена за полиномиальное время.
В противном случае у вас возникнет проблема, потому что, если я не ошибаюсь, вам нужно найти максимальный (возможно, индуцированный) эйлеров подграф, который является NP-трудным.
Конечно, предполагается, что все веса неотрицательны.
