Я пытаюсь решить эту проблему http://coj.uci.cu/24h/problem.xhtml?abb=1368.
После большого количества исследований и потраченного времени я смог реализовать алгоритм Branch and Bound для TSP, который получает путь, проходящий все точки и возвращающийся в начало.
Я думал, что удалив самый длинный край этого пути, я получу ответ, но когда я закончил свой алгоритм, я обнаружил, что это не во всех случаях, прочитав этот вопрос: Гамильтониан пути минимального расстояния Javascript
Я нашел несколько ответов, в которых говорится, что добавление фиктивной точки с нулевым расстоянием к каждой другой точке, а затем ее удаление решает проблему, но я не знаю подробностей этого. Я уже добавил эту фиктивную точку, теперь вместо 26.01 теперь это 16.23 в качестве ответа. Я еще не удалил фиктивную точку, потому что не понимаю «весь смысл добавления фиктивной точки».
Можете ли вы помочь мне решить эту проблему? Или лучше использовать другой подход вместо TSP?
