Как хранить карту и генерировать график с BFS в Ruby

Question

Так что я думаю, это классический вопрос для кого -то с MSC в CS.

У меня есть n -элемент, и у меня тоже есть расстояния. Допустим, у меня есть 3 элемента со следующими расстояниями. Это симметрично, так что

A -> B == B -> A

Это похоже на матрицу:

   A,  B,  C,  
A  0, 10,  20 
B 10,  0,  30
C 20, 30,   0

Мой вопрос был бы:

• Как я могу сохранить это эффективно (какая структура данных)
• Какой самый эффективный способ получить связанный список, где сумма расстояния минимальна

В этом случае лучшее

B -> A -> C = 30 which equals to C -> A -> B

Другой случай:

A -> B -> C = 40 which equals to C -> B -> A

У меня сложилось впечатление, что BFS может подходить для этого. Ссылка на документацию на английском языке хороша, даже книги на Amazon ...

Answer 1

Идеальным решением для вашей структуры данных является Список смежности.

Список смежности - это просто список объектов (представляющий вершины на вашем графике). У каждого объекта есть список, содержащий все вершины, которые он имеет смежный край и соответствующий вес.

В Ruby простая реализация может выглядеть как -то вроде:

vertices = {}
a = Vertex.new
b = Vertex.new

a.add(b, 10)
b.add(a, 10)

vertices[a] = a
vertices[b] = b

Алгоритм, чтобы найти самый короткий взвешенный путь, называется Дейкстра.

Если вы хотите пройти самый короткий путь после запуска алгоритма, вы можете сделать трассировку. Это делается путем хранения (оптимального) родителя каждого узла по мере достижения его. Чтобы сделать это, у вас может быть хэш для каждого посещаемого узла, который отображается на узел, который ведут к нему с наименьшими затратами.

После того, как вы закончите алгоритм, ваш рекурсивный отслеживание может выглядеть примерно так:

def traceback(parent, start, node, path)
  if(start == node)
     (path + start.to_s).reverse
  else
     path += node.to_s + " "
     traceback(parent, start, parent[node], path)
  end
end

Answer 2

я слышу Дейкстра имеет алгоритм для навигации по взветственному графику.