Алгоритм грубой силы для задачи коммивояжера в Java

Я работаю над проектом для урока математики в школе, и я решил решить задачу о коммивояжере, которую всегда хотел изучить подробнее. Однако у меня проблемы с моим алгоритмом решения грубой силы.

*Перейдите к обновлению внизу, чтобы просмотреть самую последнюю версию кода

. ПРОПУСТИТЕ ЭТОТ ПАРАГРАФ, ЕСЛИ ВЫ ЗНАЕТЕ, ЧТО ТАКОЕ ПРОБЛЕМА КОММЕРСАЖНИКА: Подводя итог, можно сказать, что TSP выглядит следующим образом :Вы — продавец, который хочет посетить каждый город в регионе (город — это, по сути, точка на карте ). В ограниченной области x и y есть 'n' городов, и каждый город соединен с каждым городом (предполагаемой прямой дорогой ). Вам нужно найти кратчайший маршрут среди городов, который позволит вам посетить каждый город. Один из алгоритмов, который я хочу использовать (и мне нужно будет протестировать другие алгоритмы ), — это грубая сила, которая проверяет все возможные маршруты. и возвращает кратчайший маршрут. Причина, по которой это не всегда используется, заключается в том, что это требует от нас проверки (n -1 )! возможных маршрутов, и это число становится огромным по мере увеличения «n» -, на самом деле всего с 50 городами это будет 608281864034267560872252163321295376887552831379210240000000000 маршрутов для проверки.

ПРЕДПОЛОЖИМ ДЛЯ ВСЕХ ПРИМЕРОВ, РАССМОТРЕННЫХ В ЭТОМ ПОСТЕ, ЧТО МЫ БУДЕМ ИСПОЛЬЗОВАТЬ ПРОИЗВОЛЬНЫЙ РЕГИОН С 4 ГОРОДАМИ(хотя алгоритм может обрабатывать n городов. также мы не заботимся о расстояниях -мы хотим пройтись по всем возможным маршрутам грубой силой ).

Вот простая картинка, демонстрирующая то, о чем я говорю (4 города — это то, с чего я начинаю, чтобы проверить, правильно ли работает процесс)

картинка карты с городами

Вот алгоритм грубой силы (предполагает, что все другие вызываемые методы работают правильно, потому что они):

(проверьте ниже немного больше пояснений )

[код]

public void BruteForceFindBestRoute(Route r) //Must start r having 1 unflagged city to begin with
    {
        if(!r.allFlagged() && r.route.size() != m.cities.size())
        {
            /*STEP 1 Begin with last unflagged city*/
            City pivot = r.lastCityAdded();
            /*STEP 2: Flag city*/
            pivot.visited = true;
            /*STEP 3: Find cities "NOT IN ROUTE"*/
            ArrayList citiesNotInRoute = new ArrayList();
            for(int i = 0; i

Вот моя логика: (Обратите внимание, :у объекта города есть логическая переменная «флаг», называемая «посещенная» )

(. если не отмечены все маршруты и если маршрут не содержит всех возможных городов)

• начните с маршрута с 1 не отмеченным городом.
• отметьте «последний не отмеченный флагом» город (этот город является «стержнем»)
• Найдите каждый город, который НЕ ВХОДИТ В МАРШРУТ R, и добавьте его в новый маршрут.
• рекурсивно вызывать метод BruteForce на каждом из этих маршрутов.

(если не отмечены все маршруты, но маршрут содержит каждый город)

• флаг последнего города

(иначе... это означает, что в маршруте отмечены все города, и он содержит все возможные города)

• посмотрите, является ли это кратчайшим маршрутом -, если да, сохраните его в глобальной переменной

Это изображение поможет мне объяснить проблему... Так что программа правильно идет по левой стороне. Однако после того, как он дойдет до конца, можно ожидать, что рекурсия вернется к шагу 4, что она и делает. Однако вместо того, чтобы R помечал город A, а город B не помечал, а затем рекурсивно вызывал себя на «новом маршруте», содержащем Aflag и B, R теперь включает все 4 города, и все 4 помечены. Это не удается, потому что он снова добавляет город D в «newRoute», рекурсивно вызывает себя снова, а в другом методе мы получаем ошибку массива за пределами границ, потому что в моем регионе нет 5 городов, но в маршруте r неправильно указаны 5 городов. (А,В,С,D,D ).

Полезное изображение рекурсивной древовидной структуры

Проблема как-то связана с вызовом рекурсии в цикле или с ссылкой на маршрут 'r' в рекурсивном вызове.

Если у вас есть идеи, что мне нужно сделать, я был бы СЕРЬЕЗНО признателен за помощь.

Спасибо всем, кто поможет мне. Я отправлю весь проект всем, кто готов помочь.

ОБНОВЛЕНИЕ

Итак, я попытался сократить и упростить свой первоначальный метод, и вот что у меня получилось:

public void BruteForceFindBestRoute(Route r, ArrayList citiesNotInRoute)
    {
        if(!citiesNotInRoute.isEmpty())
        {
            for(int i = 0; i

Проблема в том, что переменная i внутри цикла for, кажется, теряет свое значение, когда мы выходим из рекурсии, и цикл не продолжается. Идеи?