Лучший способ определить минимальный размер конструкции с учетом только расстояний между точками

13

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

Представьте, что вам дан набор точек и список некоторых расстояний между точками d i j . Как наиболее эффективно определить минимальную размерность пространства, в которое нужно вложить эти точки? Другими словами, что является наименьшим k таким, что в R k существует множество точек, удовлетворяющих ограничениям на расстояние d i j . Я был бы одинаково счастлив с ответом для{vi}i=1ndijkRkdij , но это кажется более трудным.Ck

Я счастлив сказать, что расстояния должны соответствовать dij только с точностью до некоторой постоянной и иметь точки ограничены точки на некоторой решетке постоянного расстояниятого, чтобы вопросыИЗБЕЖАТЬ вычислительный с реалом.ϵ

Действительно, я был бы весьма доволен решением для версии решения этой проблемы, где при заданных и k вас спрашивают, существует ли такой набор вершин { v i } . Тривиально проблема в NP, так как задан набор точек в R kdijk{vi}Rk легко проверить, что они удовлетворяют требованиям к расстоянию, но кажется, что для этой конкретной задачи должны быть субэкспоненциальные алгоритмы времени.

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

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

Джо Фитцсимонс
источник
1
Я полагаю, вы хотите вложение в ? 2
Суреш Венкат
@Suresh: Да, извините, я хотел добавить это.
Джо Фицсимонс
1
Кстати, из какой области физики это происходит?
Винаяк Патхак
@Vinayak: я только сталкивался с этим, пытаясь вычислить что-то в квантовой механике.
Джо Фицсимонс

Ответы:

13

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

Сакс [Sax79] и Йемини [Yem79] независимо показали простым сокращением проблемы разбиения, что эта задача NP-полна даже в случае одного измерения; то есть следующая задача является NP-полной при k = 1:

Завершение k- мерной евклидовой матрицы расстояний / k- мерное евклидово вложение взвешенного графа
Экземпляр : Симметричная матрица M , элементы которой являются либо положительными целыми числами в двоичной системе, либо «неизвестными».
Вопрос : Могут ли неизвестные записи в M быть заполнены действительными числами, так что M становится матрицей расстояний точек в k- мерном евклидовом пространстве ℝ k ?
Эквивалентно,
Экземпляр : граф G, где каждое ребро имеет положительный целочисленный вес, записанный в двоичном виде.
Вопрос : Могут ли вершины G помещаться в kевклидово пространство ℝ k, так что для каждого ребра G расстояние между двумя конечными точками равно весу ребра?

Более того, Сакс [Sax79] показал (путем более сложного сокращения из 3SAT), что k- мерное евклидово расстояние до матрицы завершения остается NP-трудным даже при ограничении, что все известные записи в M либо 1, либо 2 для каждой положительной целочисленной константы. к . В частности, проблема является NP-полной, даже когда известны записи в M даны в унарном виде. [Sax79] также содержит некоторые результаты твердости о приближенном внедрении.

Между прочим, я не думаю, что это тривиально, что проблема в NP; обратите внимание, что вам нужны иррациональные координаты в некоторых случаях, когда к > 1. Я не знаю, если это известно, чтобы быть в NP.

Ссылки

[Sax79] Джеймс Б. Сакс. Встраиваемость взвешенных графов в k- пространстве сильно NP-трудна. В материалах 17-й конференции Аллертона по коммуникациям, управлению и вычислениям , с. 480–489, 1979. Также у Джеймса Б. Сакса: Две статьи по проблемам вложения графов , факультет компьютерных наук, Университет Карнеги-Меллона, 1980.

[Yem79] Йехиам Йемини. Некоторые теоретические аспекты проблем определения местоположения. В 20-м ежегодном симпозиуме по основам компьютерных наук (FOCS) , с. 1–8, октябрь 1979. DOI: 10.1109 / SFCS.1979.39

Цуёси Ито
источник
1
Благодарю. Конечно, в общем случае это не очевидно в NP, но если вы превратите это в многообещающую проблему, ограничив точки лежащими на решетке, и вместо этого получите квадрат расстояний, а не сами расстояния, тогда все квадратные расстояния являются целыми числами, и поэтому решение может быть проверено точно за полиномиальное время.
Джо Фицсимонс
11

dndN

Суреш Венкат
источник
1
Отлично, это может быть просто указатель мне нужен. Извините, что трачу ваше время, если это несколько тривиальный вопрос.
Джо Фицсимонс
1
Это не тривиально, если вы не копаетесь в геометрии расстояния :)
Суреш Венкат
Я прочитал ваш пост, и он определенно указывает мне верное направление. Однако я не совсем понимаю, как это будет применяться только с частичным набором расстояний. Не могли бы вы просветить меня?
Джо Фицсимонс
Ах, проблема, которую я понимаю, состоит в том, что это не обрабатывает частичный случай. :(
Суреш Венкат
1
@Joe: матрица расстояний удовлетворяет всем неравенствам отрицательного типа тогда и только тогда, когда соответствующая «матрица Грама» является положительной полуопределенной. (Я поместил «матрицу Грама» в страшные кавычки, потому что это не совсем матрица Грама, если расстояние не реализуемо в евклидовом пространстве.) Однако я не знаю, как справиться с ограничением на размерность, используя этот подход.
Цуёси Ито