lem-in

Программе на вход подается информация о муравейнике (количество муравьев, название комнат + их координаты + комнаты-старт(откуда все муравьи стартуют) и комната финиш (куда все муравьи должны придти), какие комнаты соединены). От нее требуется найти наиболее оптимальный путь (с наименьшим количеством ходов), при условии что за один ход муравьи могут пройти в соседнюю комнату, но муравьи не могут идти по несколько штук по одному и тому же переходу + они не могут находиться одновременно больше одного муравья в одной комнате (за исключением комнаты-старт и комнаты-финиш)

Входные данные

Файл с входными данными подается через терминал следующим образом: ./lem-in < 'map_file'. Файл с картой выглядит следующим образом:

100
##start
A 0 2
B 1 0
#comment
C 3 0
D 4 2
E 2 2
F 3 4
G 5 4
#another comment
##end
H 6 2
A-B
A-E
B-C
C-D
D-E
#comment №3
D-H
D-F
E-F
F-G
G-H

Сначала идет количество муравьев (в приведенном примере 100). Далее идет описание комнат (ее название + ее координаты (х и у)). Команды ##start и ##end означают, что после них будет дана комната-старт и комната-финиш соответственно. После комнат идет информация о том, какие комнаты соединены, в виде 'комната 1' - 'комната 2'. На этом обязательная информации по карте заканчивается. В файле на любой строчке могу располагаться комментарии (строка с комментарием обязана начинаться с '#', не валидные команды наподобие ##falseCommand тоже должны восприниматься как комментарии).
Карта может содержать до 4000 комнат и 10000 переходов (в принципе ничего не запрещает подать и карту большего размера, просто скорость алгоритма замерялась на карте именно такого размера и к тому же при увеличении карты время для поиска решения растет в геометрической прогрессии).

Валидация карты

На этапе валидации карты проверяются следующие условия:

1. Количество муравьев не отрицательное.
2. Ровно по одной комнате обознаены как старт и как финиш.
3. Есть хотя бы один путь соединяющий старт и финиш.
4. нет комнат с одинаковыми названиями.
5. Нет комнат с одинаковыми координатами (одинаковые и х и у).
6. Переходы соединяют только существующие комнаты.
7. Нет комнат, начинающихся с 'L' и содержащих дефис (такие комнаты затрудняют просмотр решения).
   Карта может иметь мульти-ребра (2 комнаты могут быть соединены более чем 1 переходом) и петли (ребра, соединяющие комнату саму с собой). Ошибок в работе алгоритма данные ребра не вызовут.

Алгоритм

Задача сводится к поиску вершинно-непересекающихся путей между стартом и финишем. Для поиска таких путей используется алгоритм Суурбалле. Более подробно о данном алгоритме можно прочесть по ссылке. небольшие изменения в работе алгоритма:

1. Для поиска кротчайшеого пути используется не алгоритм Дейкстры, а поиск в ширину (что в принципе одно и то же для невзвешенного графа).
2. Вместо физического разделения вершин, учавствующих в пути, на vertex-in и vertex-out, используется пометка данных вершин флагом с соответствующим изменением поведения алгоритма при поиске пути помеченной данным флагом. При поиске решения алгоритм Суурбалле используется в цикле по следующему принципу:
3. Сначала находим первый путь(он существует всегда, так как мы предварительно проверили существование пути между стартом и финишем). Расчитываем сколько ходов потребуется чтобы провести всех муравьев через этот путь. Запоминаем количество ходов.
4. Пытаемся найти очередной путь. Тут существует 4 варианта:
   а) Еще один путь не найден. В этом случае мы нашли все существующие пути между стартом и финишем, и оптимально использовать все найденные пути.
   б) Путь найден, но рассчитанное количество ходов больше чем при использовании меньшего количества пути. В этом случае прекращаем дальнейший поиск и используем пути, найденные в предыдущей итерации.
   в) Путь найден, но косичество путей превышает количество муравьев. В этом случае прекращаем дальнейший поиск и используем пути, найденные в предыдущей итерации.
   г) Путь найден, и расчитанное количество ходов не больше, чем при использовании меньшего количества путей. В этом случае запоминаем пути и количество требуемых для прохождения по данным путям всех муравьев шагов и еще раз повторяем шаг (2).
   По выходу из цикла у нас будет оптимальное решение.

Вывод

Перед решением необходимо вывести карту, полученную на вход (без комментариев). Решение выводится в следующем формате:

L1-2
L1-3 L2-2
L1-1 L2-3 L3-2
L2-1 L3-3
L3-1

где каждая новая строка - новый ход, после 'L' идет номер муравья, а после тире - название комеаты, куда муравей пошел в этом ходу. Муравьи, дошедшие до финиша пропадают из вывода со следующего хода.

Флаги

в программе реализованы следующие флаги:

Usage:
./lem-int [-m, -v, -d] < map
    [-m] - print decision without input map
    [-v] - turn on visualisation
    [-d] - design map

-m - распечатывает решение без печати карты, поступившей на вход.
-v - визуализация. Визуализация реализована с помощью графической библиотеки SDL2. Для корректной работы в UNIX-подобных системах необходимо установить фраемворк библиотеки в директории /etc/Library/. Необходимо установить следующие библиотеки:

SDL2
SDL2_ttf
SDL2_gfx

-d - дизайн карты. Чаще всего нужен для корректного отображения карт очень больших размеров, карт, где координаты комнат имеют очень большой разброс, или же назначены случайным образом и отрисовке по координатам сливаются во что-то неудобное для визуального восприятия. Данный режим принудительно назначает всем комнатам координаты по порядку, чтобы они вписались в квадрат. Старт и финиш выносятся сверхк и снизу данного квадрата.

Компиляция

Проект снабжен Makefile.