как подключить набор изолированных вершин

задан набор вершин в плоскости, выбирая точку входа, точку возле входа как выход, как я должен соединить их, чтобы край любых двух последовательных точек не был больше чем определенное максимальное значение? , например ниже, * подставка для вершин, заданная точкой как In, чем выход из точки возле входа, есть ли какой-либо алгоритм для этого ???? Помогите?как подключить набор изолированных вершин

* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * <------ in 
* * * * * * * * * * 
* * * * * * * * * * <------- out 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * 
* * * * * * * * *

источник

2015-07-13 Mingguo Peng

Вы пробовали грубую силу? Кроме того, ваша проблема неясна. Являются ли точки на регулярной сетке или распределены случайным образом? Вы хотите соединить все точки? Разрешены ли края? Доступны ли вход и/или выход или должен ли алгоритм выбрать их? И, наконец, этот вопрос действительно является вопросом программирования? – kazemakase

@kazemakase, извините за мой вводящий в заблуждение, да, точки на регулярной сетке, и я должен соединить все точки. края разрешены. входная точка выбирается вручную и точка выхода должна быть выбрана рядом с входом по алгоритму. На самом деле, я инженер по физическому проектированию ИС, у меня много ячеек в макете, я хочу соединить их по металлическим слоям. определенно это вопрос программирования –

Используйте breadth first search:

# Input: G (set of vertices), v (entry vertex) 
    procedure BFS(G,v) is 
     let Q be a queue 
     Q.enqueue(v) 
     label v as discovered 
     while Q is not empty 
     v ← Q.dequeue() 
     process(v) 
     for all edges from v to w in G.adjacentEdges(v) do 
      if w is not labeled as discovered 
       Q.enqueue(w) 
       label w as discovered

G.adjacentEdges(v) будет искать вершины, которые достаточно близко, но до сих пор не обнаружены. process(v) будет проверять, является ли v конечной вершиной. Каждая вершина также должна была бы помнить, как она была достигнута из входной вершины.

источник

2015-07-13 09:22:30 Oswald

спасибо за ваш совет, но все вершины изолированы, у них нет связи, и я хочу последовательно их подключать, чтобы генерировать строку, изнутри в выход. есть ли у вас предложения? @Oswald –

У них может быть не соединение, но у них есть расстояние (как подразумевается вашим утверждением, что * край любых двух последовательных точек не превышает некоторого максимального значения *). Для целей поиска по ширине это можно интерпретировать как * с соединением *. – Oswald

В любом случае, поскольку вы уточнили, что вам нужно соединить ** все ** вершины, вы должны пойти с решением kazemakase. – Oswald

Если точки размещены на обычной сетке и отсутствуют точки, решение относительно просто (A, B, C). Проблема может возникнуть в случае, если в таблице есть как нечетное число строк, так и нечетное число столбцов, и если диагональное расстояние между точками больше вашего максимального разрешенного расстояния (D).

enter image description here

Вы также можете проверить Moore curve space-filling curves или вообще, если вы заинтересованы в теоретических свойств возможных решений.

Я думаю, что проблемы становятся довольно сложными, если точки не равномерно распределены, или не все позиции на сетке заняты.

источник

2015-07-13 11:16:16 kazemakase

Вау, спасибо @kazemakase: «Я думаю, что проблемы становятся довольно сложными, если точки не равномерно распределены, или не все позиции на сетке заняты». Ну, это тот случай, какая-то позиция может открыться, спасибо за вашу информацию, у меня будет попытка, –

@MingguoPeng Вы можете просто притворяться, что позиции не открыты, но это может нарушить максимальное ограничение расстояния. – kazemakase

как подключить набор изолированных вершин

ответ

Смежные вопросы