Восстановление вложения точек из графа с ребрами, взвешенными по расстоянию между точками

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

Ваша цель - восстановить относительные положения точек, учитывая только доступные расстояния (представленные весами ребер). Например, если бы я дал вам тогда вы знаете, что точки - это вершины тетраэдра. Вы не знаете, где он находится относительно источника, его ориентации или зеркального отражения, но вы можете сказать, что это тетраэдр.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

В общем, проблема проста, если я дам вам все длины ребер. Просто произвольно выберите точку которая будет в , затем выберите соседнюю точку и поместите ее в , тогда общий сосед триангулируется на XY плоскости, то конечный общий сосед триангулируется в полупространство и нарушает оставшуюся симметрию (при условии, что вы не выбрали вырожденные точки). Вы можете использовать эти четыре точки для триангуляции всех оставшихся. ( 0 , 0 , 0 ) p 1 ( d 0 , 1 , 0 , 0 ) p 2 p 3 z > $p_0$$(0,0,0)$$p_1$$(d_{0,1},0,0)$$p_2$$p_3$$z > 0$

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

Что вызывает вопросы:

• Насколько дорого найти решение?
• Как вы определяете, является ли решение уникальным, вплоть до перевода / вращения / зеркального отображения? Достаточно ли 3-связности? Нужно?
• Какие условия делают проблему тривиальной?
• Если я не обещаю, что веса ребер на самом деле соответствуют расстоянию до точки sin 3d, насколько дорогой будет определить, возможно ли вложение вообще?

Один из алгоритмических подходов к решению этой проблемы: рассматривайте это как набор узлов, соединенных пружинами, а затем позволяйте им приходить в форму.

Каждое ребро соответствует пружине; если расстояние между точками и предполагается равным , то пружина выбирается таким образом, что в идеале она должна иметь длину (она может быть больше или короче, но это стоит энергии ). Теперь мы хотим найти набор позиций, которые минимизируют общую энергию. Предположим, что каждая вершина находится в точке . Тогда полная энергия этой договоренности будетv w d v , w d v , w v x v ∈ R$(v,w)$$v$$w$$d_{v,w}$$d_{v,w}$$v$$x_v \in \mathbb{R}^3$

Здесь даны (они являются весами по краям), и мы хотим (они являются координатами точек). x $d_{v,w}$$x_v$

Мы можем решить для договоренности которая минимизирует эту полную энергию. Эта договоренность тогда обеспечивает разумного кандидата на позиции пунктов. Это проблема оптимизации, и для решения такого рода задач оптимизации существуют стандартные методы. См., Например, статью « Сетевые решения » Эрики Кларрайх.$x$

Я не думаю, что есть какая-либо гарантия, что это даст правильное желаемое решение. Возможно, что проблема оптимизации может прийти к другому оптимуму, который не отражает фактическое расположение точек, которые вы искали. Однако, если ваш график достаточно плотный, я подозреваю, что он часто может работать и дать вам желаемое решение.

Сноска. Конечно, даже в лучшем случае мы можем решить эту проблему только до перемещения, поворота и отражения, поскольку эти преобразования сохраняют все расстояния. Таким образом, вы не можете ожидать уникального решения - но вы можете надеяться, что решение является уникальным вплоть до перевода, поворота и отражения.

Наконец, есть много работы по встраиванию графов в пространство , минимизируя искажение встраивания. Это очень связано; вы в основном просите вложение с нулевым искажением в . Таким образом, методы, разработанные в этом контексте, могут быть полезны и для вашей проблемы. Как правило, эта работа фокусируется на поиске вложения с низким искажением, потому что эта работа фокусируется на случае, когда не существует идеального встраивания, при котором все расстояния точно совпадают, поэтому вместо этого она ищет решение с низким искажением (то, где большинство краевых расстояний соответствовать очень хорошо) - так что работа сосредоточена на немного другой проблеме. Однако, возможно, что их методы могут быть эффективными и в вашей ситуации. Стоит попробовать.ℓ $\ell_2$$\ell_2$

Проблема в NP-Complete . Расположение точек - это хороший сертификат, так что оно в NP, и вы можете кодировать схемы в «есть ли удовлетворительный набор точек?» проблема.

Сокращение от оценки схемы до внедрения расстояния

Мы собираемся свести оценку схемы к проблеме внедрения расстояний, создав систему координат, поместив в нее логические биты, установив одинаковые биты и создав виджеты для вентилей NOT и AND.

1. Координаты . Нам нужна какая-то система координат, с которой мы можем позиционировать точки. Сделайте это, создав «базовый» тетраэдр из точек. Добавьте четыре точки, все из которых объявлены на расстоянии друг от друга. Это заставляет форму этих четырех точек в тетраэдр. Мы можем расположить другие точки относительно нашей системы координат тетраэдра, указав их расстояние до каждого из четырех углов основания. Тетраэдр можно перевести, повернуть и отразить, но то же самое произойдет и со всеми остальными точками.$1$

2. Биты . Чтобы сделать немного, мы помещаем треугольник точек относительно основного тетраэдра. Нормаль треугольника должна указывать вверх вдоль оси Z, чтобы треугольник был параллелен плоскости XY (в координатах тетраэдра). Также его края должны иметь длину . Сделав это, мы добавляем точку «значения» , заданную как расстояние от остальных трех. Мы не подключаем к базовой системе координат. Это дает ему две возможные позиции: по центру выше или ниже треугольника, как последний угол тетраэдра. Бит включен, если точка выше треугольника, и выключен, если ниже.в 1 в $1$$v$$1$$v$$\frac{1}{\sqrt{3}}$

3. Провода . Мы можем заставить два бита быть равными, сказав, что расстояние между их точками значений равно расстоянию между центрами их треугольников. Есть одно исключение: когда верхний или нижний угол одного из битов точно совпадает с центральной плоскостью другого. В этом случае мы сначала используем провод для перемещения одного из битов по вертикали.

4. НЕ . Мы можем получить отрицание бита, добавив вторую точку значения к тому же треугольнику, но требуя, чтобы было расстоянием от . Это заставляет занять позицию, противоположную , по отношению к треугольнику, давая нам немного с противоположным значением.$w$$w$$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. ПОДРАЗУМЕВАЕТ . Эквидистантная проблема, с которой нам пришлось обходиться с проводами, на самом деле весьма полезна. Когда биты выстраиваются в линию таким образом, который мы можем заставить вертикальным проводом, более высокий подразумевает более низкий. Если верхний верный, только вершина нижнего находится на правильном расстоянии. Если верхнее значение ложно, верх и низ находятся на правильном расстоянии.

6. И . Чтобы бит был равен и , нам нужны два значения и виджет для принудительного равенства, когда и согласуются. Последствия лишь и . Чтобы создать виджет, мы перемещаем и вертикали, чтобы они находились на одном уровне и на расстоянии , затем мы перемещаем чтобы быть равноудаленными между ними. Затем мы добавим баллы и расстояние из и$C$$A$$B$$A$$B$$C \implies A$$C \implies B$$A$$B$$\frac{2}{\sqrt 3}$$C$$S_A$$S_B$$\frac{\sqrt 2 - 1}{2 \sqrt 3}$$A$$B$«с точки значений соответственно, и заставить расстояние между и быть . Мы также добавить точку расстояние от обоих и . Это создает цепочку между точками значений и , с в центре цепочки. Когда , цепочка растягивается до предела, и находится в центре треугольникаКогда звенья цепей вынуждены идти в совершенно противоположных направлениях, толкая$S_A$$S_B$$\frac{\sqrt 2 + 1}{\sqrt 3}$$S_C$ SASBABSCA≠BSCCA=BSCCACSD$\frac{\sqrt 2 + 1}{2 \sqrt 3}$$S_A$$S_B$$A$$B$$S_C$$A \neq B$$S_C$$C$$A = B$это до предела и размещения на точки значения «ы равняться . Чтобы форсировать точку значения , мы вставляем точку на расстоянии от точки значения иЭто не ограничивает точки значение «х , когда , но силы , когда .$S_C$$C$$A$$C$$S_D$ SCCCA≠BA=B=CA=$\frac{1}{2 \sqrt 3}$$S_C$$C$$C$$A \neq B$$A=B=C$$A=B$

С этими элементами вы можете закодировать любую схему в вложение на расстоянии. Входы становятся битами, логические элементы разлагаются на NOT и AND, вводя новые биты по мере необходимости, и все. Заставьте положение вывода быть истинным, и вы получите свою проблему удовлетворенности.

Частичный ответ на уникальность : 3-связанности не достаточно.

Пример минимального счетчика: граф куба ( семейства графов гиперкуба )$Q_3$

Чтобы увидеть, как фиксация длины всех ребер в не дает положения вершинам в пространстве, которое является уникальным вплоть до / вращения / зеркального отображения, посмотрите, как можно сгладить картонную коробку (с удалением 2 противоположных граней) .$Q_3$

Возьмите углы картонной коробки, чтобы быть интересующими вершинами. Каждый угол картонной коробки имеет фиксированное расстояние от других углов, с которыми он разделяет лицо коробки.

Несмотря на то, что результирующий граф имеет даже больше ребер, чем , он все же позволяет картонную коробку - преобразование, которое не может быть произведено / вращением / зеркальным отображением.$Q_3$

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

Евклидово восстановление расстояния от информации о частичном расстоянии Сюй, Чен