Как работает алгоритм - sergeresko/Lem_in-explanation GitHub Wiki
Даёшь алгоритму Бхандари исходный граф, в котором пока нет никаких отмеченных путей (т.е. все pred
и succ
равны NULL
). Он найдёт кратчайший путь и сохранит его в графе (поменяет значения pred
и succ
). Ты вычисляешь, сколько строчек решения потребуется, если все муравьи пойдут по этому пути, и запоминаешь это число и путь (условно mem = (n, paths)
).
Запускаешь алгоритм Бхандари ещё раз. Теперь, поскольку в графе уже есть один путь, он найдёт два пути с минимальной суммарной длиной и сохранит их в графе. Снова вычисляешь, сколько строчек займёт решение, если распределить муравьёв по этим двум путям оптимальным способом. Если число вышло меньше, чем то, которое находили раньше, забываешь всё, что было в mem
, и запоминаешь новое число и новые пути.
Аналогично дальше делаешь всё это в цикле. Каждый раз алгоритм Бхандари будет давать набор путей, в котором их на один больше, чем при предыдущем запуске. Прекратить нужно, когда он больше не сможет найти путей (или можно придумать более умное условие). То, что будет в этот момент в mem
, и есть решение.
Дальше: Алгоритм Бхандари