Próbuję rozwiązać ten problemhttp://coj.uci.cu/24h/problem.xhtml?abb=1368.

Po wielu badaniach i spędzeniu dużo czasu udało mi się zaimplementować algorytm rozgałęzienia i powiązania dla TSP, który otrzymuje ścieżkę przechodzącą przez wszystkie punkty i powracającą do rozpoczęcia.

Myślałem, że usunięcie najdłuższej krawędzi z tej ścieżki dostanę odpowiedź, ale gdy skończyłem mój algorytm, odkryłem, że nie jest to prawdą we wszystkich przypadkach, czytając to pytanie:Minimalna odległość Hamiltonian Path Javascript

Znalazłem kilka odpowiedzi mówiących, że dodanie punktu atrapy o zerowej odległości do każdego innego punktu, a następnie usunięcie go rozwiązuje problem, ale nie znam jego specyfiki. Dodałem już ten fikcyjny punkt, teraz zamiast uzyskiwać 26.01, teraz jest to 16,23 jako odpowiedź. Nie usunąłem jeszcze tego fikcyjnego punktu, ponieważ nie rozumiem „całego punktu dodawania fikcyjnego punktu”.

Czy możesz mi pomóc w rozwiązaniu tego problemu? Czy może lepiej zastosować inne podejście niż TSP?