Помогите с алгоритмом

Я правильно понимаю, что, допустим, если в одномерном пространстве заданы точки A(0), B(1), C(5) и D(6), то результат будет равен:
X = d(A,B) + d(B,A) + d(C,D) + d(D,C) = 1 + 1 + 1 + 1 = 4?

ESS сказав(ла):

Я правильно понимаю, что, допустим, если в одномерном пространстве заданы точки A(0), B(1), C(5) и D(6), то результат будет равен:
X = d(A,B) + d(B,A) + d(C,D) + d(D,C) = 1 + 1 + 1 + 1 = 4?

Натисніть, щоб розгорнути...

Судя из постановки задачи - правильно.

Для первой части легко понятно как считается за n^2, а вот как в принципе посчитать для второй части - непонятно. Понятно что ищем глобальный экстремум функции многих переменных. Точно мы его не найдем...

Размещаем произвольно свободные координаты, делаем метод по-координатного спуска или метод градиентного спуска
но в любом случае никак непонятно, что мы не "упадем" в локальный минимум, вместо глобального

Можно попробовать Нелдера Мида - он имеет хорошую сходимость. Но для большого количества переменных его нужно модифицировать.

Если допустимо не идеальное, но близкое к нему решение - таки да, там методов гуляй-не хочу. Честно говоря, и возиться тогда не хочется.

Гораздо интереснее - найти единственное идеальное решение, да еще и доказать, что таким алгоритмом находится именно оно.

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

И вообще, в моем видении это дискретная задача на самом деле. Неизвестная координата равна одной из известных в этой же размерности. Значит, если есть

1 2 3 9
5 4 ? 8
3 ? 9 1

то вместо вопросиков может быть один из двух вариантов:
1 2 3 9
5 4 {3;9} 8
3 {2;4} 9 1

Тут 4 варианта и все отлично. Но в общем случае сложность такого алгоритма бешеная, если размерность D, количество точек N, в каждом столбце есть n таких вопросиков, то количество вариантов:

( N - n )^(n*D).

Сие безумно много. Надо думать, как сузить эту область.

a). Это не задача коммивояжера
b). Здесь нельзя использовать градиент, он свалится в локальный минимум
c). Можно сделать генетическим алгоритмом, который не будет оптимальным.
ТС - нужно точное решение?

Ferox сказав(ла):

Achenar не обязательно есть хотя бы одна точка со всеми заданными координатами.

Натисніть, щоб розгорнути...

Ойвэй, а шо, перейти к системе координат, где эта точка имеет координаты (0,..., 0) так сложно?

Ну в общем наконец-таки люди начали думать, вместо того чтобы шутить. Есть еще одно пожелание к алгоритму.

Крайне желательно, а может быть даже обязательно, чтобы решение задачи об n+1 точках, сводилось к решению задачи об n точках плюс какие-то дополнительные расчеты. То есть можно считать что решение задачи об n точках (плюс возможно какие-то дополнительные данные накопленные и сохраненные при решении задачи об n точках) уже есть и теперь нужно за оптимальное время решить ту же задачу об n+1 точках.

BiancoNeri сказав(ла):

А по сути - Ferox есть еблан.

Натисніть, щоб розгорнути...

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

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

Хохмы ради сгенерил 100 4D точек, из которых 200 координат принял неизвестными. Получил 10^254 вариантов, что само по себе феерично доставляет. Но можно постепенно сужать это количество, и вполне реально, что время расчета станет разумным.

Дело в том, что не все варианты (пост #25) даже в условиях полной непонятки имеют смысл. Чтобы это определять, нужен алгоритм вычисления минимального и максимального расстояния между двумя точками, у которых координаты могут быть вариантами.

Например, между точками

5 - 4 - {3;9} - 8
3 - {2;4} - 9 - 1

минимальное расстояние (без квадратов) - 2 + 0 + 0 + 7 = 9. Нули - потому что неизвестная координата в предположении, что точки максимально приблизились, выравнивается с известной или просто обе неизвестны, но все равно одинаковы, один фиг там будет ноль.

Максимальное расстояние - 2 + 2 + 6 + 7 = 15, то есть подбираем так, чтобы неизвестные координаты стояли как можно дальше. Если обе неизвестны - максимум второй минус минимум первой vs максимум первой минус минимум второй, кто больше - тот и составляющая расстояния.

Оказалось, что в тестовом сгенеренном случае только 0,01% имеют смысл, потому что минимальное расстояние, скажем, A -> B оказывается БОЛЬШЕ, чем максимальное A -> C. Что означает, что в A уже никогда не будет ничего скопировано из B, и если в B были известные координаты, а на их месте в A стоял неизвестный набор вариантов, то такой вариант исключался.

Проверив 100х99 точек, уменьшил количество вариантов до 10^250. Тоже феерично, но если так за каждый проход уменьшать количество вариантов на 4 порядка, то шансы есть.

Далее делаем "шаг" - берем первую неизвестную и насильно говорим, что она равна конкретному из своих вариантов. Получаем измененный набор точек, который тоже подвергается сужению, второй проход уменьшил количество вариантов еще в 40 раз. Грубо говоря, сужение мы должны проводить перед каждым шагом, иначе алгоритм рискует пережить Вселенную.

Второй шаг - берем следующую неопределенную, заменяем на один из вариантов и т.д., пока не останется неопределенных координат. Это даст ОДНО из решений Отменяем последний ход, берем следующий вариант и т.д., думаю, перебор по дереву не нужно подробно расписывать.

Без реализации и проверки все вышенаписанное - мечты и надежды, но вдруг у людей прострелит мысль.

Achenar сказав(ла):

и я все-таки считаю, что неизвестная координата у идеального решения равна соответствующей координате одной из других точек.

Натисніть, щоб розгорнути...

Это однозначно

Пространство имеет примерно 7-8 измерений, точек десятки-сотни тысяч. Понятно что нужен какой-то нестрогий алгоритм.

Что касается метрики пространства - это действительно сумма модулей разностей координат. Безо всяких квадратов и корней.

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

Чуть переформулирую задачу, чтоб было понятней.
1. Есть набор точек A1...Am в n-мерном пространстве.
2. Есть некоторая функция F(Ai) = min(d(Ai, A1), ..., d(Ai, Am)).
3. Часть точек с "плавающими" координатами.
4. Нужно расставить точки так, чтобы сумма F(A1)+...+F(Am) была минимальна.
Я прав?

Первое что пришло в голову - генетический алгоритм. Второе - симплекс.

Генетический алгоритм достаточно прямолинеен и тяжёл будет, но можно подобрать параметры оптимальные. И можно существенно оптимизировать F(Ai) - разбив пространство деревом, наподобие OcTree для 3D.