Как получить все возможные пути, найденный Волновым алгоритмом поиска вместо одного?
Я реализовал поиск пути по Волновому алгоритму. Кратчайший путь успешно находился, однако, хоть он и был минимально длинным, он не являлся оптимальным при учете ряда других факторов. В процессе прочтения статьи на Википедии я наткнулся на такой отрывок текста:
Трасс с минимальной числовой длиной пути [...] может существовать несколько. Выбор окончательного пути в приложениях диктуется другими соображениями, находящимися вне этого алгоритма.
Получение списка всех возможных путей вполне решило бы проблему, однако я ума не приложу какой алгоритм для этого стоит применить. Уже имеется рабочее поле со всеми расставленными числовыми отметками (как на рисунке), однако без найденного пути.
Каким образом я могу получить все возможные варианты вместо одного?
Ответы (1 шт):
Для того, что бы при использовании Волнового алгоритма получить все кратчайшие пути, а не только один, можно построить дерево, корнем которого будет клетка места назначения. Дочерними вершинами каждой вершины будут клетки вокруг нее, пометка на которых на один меньше чем пометка на корне. Таким образом, мы получим дерево, в котором количество листьев будет равняться количеству путей, и каждому листку будет соответствовать свой путь. Стоит учесть, что в таком дереве некоторые вершины будут иметь в себе одинаковые клетки. Пример:
Для этого изображения дерево будет выглядеть так (Дерево не полное, однако каждый лист этого дерева в дальнейшем будет иметь идентичных детей):
