Как сохранить карту и сгенерировать граф с BFS в Ruby - PullRequest
Новая
       15

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

3 голосов
/ 23 декабря 2010

Так что я думаю, что это классический вопрос для кого-то с 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 может подойти для этого.Ссылка на документацию на английском хорошая, даже книги на Амазоне ...

Ответы [ 2 ]

4 голосов
/ 24 декабря 2010

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

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

В 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
0 голосов
/ 23 декабря 2010

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

...