Обработка точек для поиска в замкнутом цикле - PullRequest
Новая
       35

Обработка точек для поиска в замкнутом цикле

0 голосов
/ 27 сентября 2011

У меня есть набор отрезков. Каждый содержит только 2 узла. Я хочу найти доступные замкнутые циклы, которые производятся путем объединения отрезков. На самом деле, я ищу наименьший цикл, если существует более одного вхождения. Если можете, пожалуйста, дайте мне хорошее решение для этого. Так, например, я добавил ниже список строк вместе с их точечными индексами, чтобы получить представление о m случае. (Где первое значение = номер строки, вторые 2 значения - это индексы точек) 

0 - 9 11  
1 - 9 18  
2 - 9 16  
3 - 11 26  
4 - 11 45  
5 - 16 25
6 - 16 49  
7 - 18 26 
8 - 18 25  
9 - 18 21  
10 - 25 49  
11 - 26 45

Итак, предположим, что я начал со строки 1. То есть я начал находить связанные петли из пункта 9, 18. Затем, не могли бы вы объяснить (шаг за шагом), как я могу получить "замкнутые петли" из эта линия.

1 Ответ

1 голос
/ 27 сентября 2011

Ну, я не вижу никакого кода C ++, но я попытаюсь предложить решение C ++ (хотя я не собираюсь писать его для вас).

Если ваш граф ненаправленный (если он направлен, s / смежные / вершины вершин /), и вы хотите найти все самые короткие циклы, проходящие через некоторую вершину N, то я думаю, что вы могли бы следовать этомупроцедура: 

G <= a graph
N <= some vertex in G
P <= a path (set of vertexes/edges connecting them)
P_heap <= a priority queue, ascending by distance(P) where P is a path

for each vertex in adjacent(N):
  G' = G - edge(vertex, N)
  P = dijkstraShortestPath(vertex, N, G')
  push(P, P_heap)

Вы также можете просто выбросить все, кроме самого короткого цикла, но это не так кратко.Пока вы не разрешаете веса отрицательных ребер (что, поскольку вы будете использовать длину отрезка линии для весов, вы не разрешаете), я думаю, это должно работать.Кроме того, к счастью, Boost.Graph предоставляет все необходимые функции для этого в C ++ (вам даже не нужно реализовывать алгоритм Дейкстры)!Вы можете найти документацию по этому вопросу здесь:

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html

РЕДАКТИРОВАТЬ: вам придется создать график из тех данных, которые вы перечислили в первую очередь, прежде чем вы сможете сделать это, так что вы просто определитесоответственно, property_map вашего графа и убедитесь, что расстояние между вершиной, которую вы собираетесь вставить, и всеми вершинами в текущем графе больше нуля, потому что в противном случае вершина уже находится в графе, и вы не захотите вставлять ее снова.

Счастливого графика!

...