Я работаю над проектом для математического класса в школе и решил заняться проблемой коммивояжера, которую я всегда хотел исследовать подробнее. Однако у меня проблемы с алгоритмом решения методом грубой силы.
* Перейдите к обновлению внизу, чтобы просмотреть самую последнюю версию кода
ПРОПУСТИТЕ ЭТОТ ПАРАГРАФ, ЕСЛИ ВЫ ЗНАЕТЕ, ЧТО ТАКОЕ ПРОБЛЕМА ПРОДАВЦА-ПУТЕШЕСТВЕННИКА: Если кратко, то ЦП выглядит следующим образом: вы - продавец, который хочет посетить каждый город в регионе (город - это по сути точка на карте). В ограниченной области 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<City> citiesNotInRoute = new ArrayList<City>();
for(int i = 0; i<m.cities.size(); i++)
{
if(!r.isCityInRoute(m.cities.get(i).name))
{
citiesNotInRoute.add(m.cities.get(i));
}
}
/*STEP 4: Recursively call BruteForceFindBestRoute() using these cities added to the end of our original route*/
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
Route newRoute = r;
newRoute.addToRoute(citiesNotInRoute.get(i));
BruteForceFindBestRoute(newRoute);
}
}
/*STEP 5: If the route is full but the last city isn't flagged, then flag it call BruteForceFindBestRoute() again, with the last city flagged*/
else if(!r.allFlagged() && r.route.size() == m.cities.size())
{
if(r.allFlaggedButLast())
{
Route x = r;
x.flagLastCity();
BruteForceFindBestRoute(x);
}
}
/*STEP 6: If all cities are flagged, the route is full. Check to see if it's the best route.*/
else if(r.allFlagged())
{
if(IsBestRoute(r))
bestRoute = r;
}
else
System.err.println("Error: somehow all cities got flagged, but the route isn't full");
}
Вот моя логика: (Примечание: у объекта города есть логическая переменная «флаг», называемая «посетил»)
(если не отмечены все маршруты и не указаны все возможные города)
- Начнем с маршрута с 1 непомеченным городом.
- отметьте "последний непомеченный" город (этот город является "пивотом")
- Найдите каждый город, который НЕ В МАРШРУТЕ R, и добавьте его в новый маршрут.
- рекурсивно вызвать метод BruteForce на каждом из этих маршрутов.
(если не отмечены все маршруты, но маршрут содержит каждый город)
- флаг последний город
(иначе ... это означает, что на маршруте отмечены все города и указаны все возможные города)
- посмотрите, является ли это кратчайшим путем - если это так, сохраните его в глобальной переменной
Это изображение поможет мне объяснить проблему ... Итак, программа правильно спускается по левой стороне. Однако после того, как он дойдет до конца, можно было бы ожидать, что рекурсия вернется к шагу 4, что она и делает. Однако вместо того, чтобы иметь в R город A помеченного флага и город B без флага, а затем рекурсивно вызывать себя на «новом маршруте», содержащем Aflag и B, R теперь включает все 4 города, и все 4 помечены. Это не удается, потому что он снова добавляет город D в "newRoute", снова рекурсивно вызывает себя, а в другом методе мы получаем ошибку массива вне границ, потому что в моем регионе нет 5 городов, но есть 5 городов на маршруте r по ошибке. (A, B, C, D, D).
Полезное изображение рекурсивной древовидной структуры
Проблема как-то связана с вызовом рекурсии в цикле или с маршрутом 'r', на который ссылается рекурсивный вызов.
Если у вас есть идеи, что мне нужно сделать, я был бы СЕРЬЕЗНО признателен за помощь.
Спасибо всем, кто мне поможет. Я отправлю весь проект всем, кто тоже захочет помочь.
ОБНОВЛЕНИЕ
Хорошо, поэтому я попытался сократить и упростить свой исходный метод, и вот что у меня есть:
public void BruteForceFindBestRoute(Route r, ArrayList<City> citiesNotInRoute)
{
if(!citiesNotInRoute.isEmpty())
{
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
City justRemoved = (City) citiesNotInRoute.remove(0).clone();
Route newRoute = (Route) r.clone();
newRoute.addToRoute(justRemoved);
BruteForceFindBestRoute(newRoute, citiesNotInRoute);
citiesNotInRoute.add(justRemoved);
}
}
else //if(citiesNotInRoute.isEmpty())
{
if(IsBestRoute(r))
bestRoute = r;
}
}
Проблема в том, что переменная i внутри цикла for, кажется, теряет смысл, когда мы прерываем рекурсию, и цикл не продолжается. Идеи?
