Я новичок, пытающийся реализовать алгоритм поиска A * для практики, и мне интересно, как лучше всего это сделать. Я создал структуру графа (матрицу смежности), и мой план состоял в том, чтобы применить A * к начальной и целевой вершине. Также создавая эвристику и улучшая ее, когда я иду. Вопрос в том, может ли это даже работать? Я посмотрел на другие реализации, и они сделали это с использованием разных структур данных.Реализация алгоритма поиска A *
Это зависит от того, как вы реализовали матрицу смежности.
Одна критическая точка A * - это поиск соседей узла. Если вы реализуете матрицу как простое плотное поле бит, где у вас есть 1 для смежных узлов и 0 для несмежных, то этот поиск довольно неэффективен, потому что вы должны проверять каждый узел. Хотя это неэффективно, это не мешает вам реализовать A *.
Если у вас есть более сложная реализация матрицы смежности, например. как разреженная матрица, которая позволяет напрямую запрашивать соседей, это будет лучше подходит для A *.
Да, я реализовал его как редкую матрицу (извините, что не знал точное имя). Тем не менее, будет ли это еще неэффективная структура данных по сравнению с альтернативами? – noobatrilla
Я определяю разреженную матрицу как двойной график [] [], как бы я запросил соседей напрямую? – noobatrilla
Это не редкая матричная реализация. Это разреженная матрица, хранящаяся в плотном представлении матрицы. См. http://www.netlib.org/utk/people/JackDongarra/etemplates/node373.html. С этим представлением все соседи находятся рядом друг с другом. –
Итак, в чем вопрос? Будет ли ваша реализация работать? – enkryptor