Home

Lem-in

Цель проета найти максимальное количество не пересекающихся путей, для перемещения из точки A в точку B муравьев за наименьшее количество ходов, при условии, что за один ход муравьи могут пройти только в соседнюю вершину. Муравьи не могут передвигаться по несколько штук по одному и тому же ребру, а так же не могут находиться одновременно в одной вершине, кроме старта и финиша.

Алгоритм

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

• Первую задачу решает алгоритм Суурбалле. Для поиска кратчайшеого пути используется поиск в ширину или модефицированный алгоритм Дейкстры.
• А для распределния муравьев оптимальным образом можно применить подход предложенный sergeresko.

При поиске решения алгоритм Суурбалле используется в цикле по следующему принципу:
Сначала находим первый путь. Расчитываем сколько ходов потребуется чтобы провести всех муравьев через этот путь. Запоминаем количество ходов.Пытаемся найти очередной путь. Тут существует 4 варианта:

1. Еще один путь не найден. В этом случае мы нашли все существующие пути между стартом и финишем, и оптимально использовать все найденные пути.
2. Путь найден, но рассчитанное количество ходов больше чем при использовании меньшего количества путей. Ищем пока алгоритм находит пути.
3. Путь найден, но количество путей превышает количество муравьев. В этом случае прекращаем дальнейший поиск и используем пути, найденные в предыдущей итерации.
4. Путь найден, и расчитанное количество ходов не больше, чем при использовании меньшего количества путей. Ищем пока алгоритм находит пути.

По выходу из цикла у нас будет оптимальное решение.

`