Алгоритм 1

Работу над проектом я начал с попытки придумать решение самостоятельно, используя только те подходы, которые мне уже были знакомы по прошлым проектам, в частности мне пришло в голову взять за основу бэктрекинговый “Алгоритм Икс”, который я успешно применил в fillit‘е.

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

Во время проверки hwolf‘а в Школе 21 я попросил его набросать мне какие-то ключевые слова, которые нужно было гуглить, чтобы решить задачу, и он назвал алгоритм Форда-Фалкерсона - с этого началось моё погружение в теорию графов.

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

Очень полезным для меня оказался канал на Ютубе за авторством Willian Fiset, где он очень хорошо объясняет теорию графов. Оттуда я узнал что такое очередь, наконец-то понял как работает поиск в ширину и, в итоге, добрался до алгоритмов Форда-Фалкерсона и Эдмондса-Карпа.

Я не сразу понял, как применить все новые знания к моей задаче, так что из наших кухонных обсуждений с krvkir на улицы 1905-го года сперва родился очень несовершенный алгоритм, основанный только на поиске в ширину. Однако, уже на том этапе был предложен хороший способ перемещения муравьёв по найденным путям.

Тогда у меня получилось добиться работы программы на некоторых картах, но меня остановило то, что я не мог прогнать свою программу через полноценный чекер из-за не совсем корректного аутпута. В конечно счёте я разозлился, плюнул, и где-то на месяц забыл про проект.

Вернувшись к нему, я быстро добился корректного вывода, но тут же встретился лицом к лицу с несовершенствами самого алгоритма.