Project Euler, problem 107 - переизобретая алгоритмы на графах...
Интересная задача, особенно для тех кто не знает изначальный алгоритм. Собственно для таковых состоять она будет в том чтобы (пере)изобрести нужный алгоритм.
Мой первый вариант был очень похож на Prim's algorithm, но я просто не поверил(и не смог доказать) что он ведет к верному результату.
Финальный вариант больше подходил на алгоритм Дейкстры.
А в целом данная задача называется задачей нахождения Minimum spanning tree и решается с помощью алгоритмов Prim's algorithm и Kruskal's algorithm. Первоначальным же алгоритмом для этого класса задач является Borůvka's algorithm. Что характерно - все три алгоритма принадлежат к классу "жадных" алгоритмов.
Комментариев нет:
Отправить комментарий