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

[Ferox]

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

Есть точки в n-мерном пространстве. Для каждой точки нужно найти расстояние до ближайшей. Сумма таких минимальных расстояний по всем точкам является ответом. В такой формулировке решение задачи просто и понятно (кому не понятно можно дальше не читать).

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

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

 

[vitos]

Задача коммивояжера чишо?

 

[avbua]

Задача коммивояжера чишо?

ни капельки.

 

[dr_mousefly]

Следует применить градиентные методы нелинейной оптимизации.
В такой формулировке решение задачи просто и понятно (кому не понятно можно дальше не читать).

Лично я не стал читать дальше никнейма ТСЕ.

 

[vitos]

ни капельки.

Не ну как ТС описывает не совсем, но может оказаться шо оно. Вернее сказать наверно - задача агЭнта па абъездке квартир?

 

[Ferox]

Следует применить градиентные методы нелинейной оптимизации.

Где ты тут нелинейность увидел?

 

[dr_mousefly]

Где ты тут нелинейность увидел?

а где ты тут линейность увидел?
теорему Пифагора забыл или тебя раньше из школы выгнали?

 

[Ferox]

Вернее сказать наверно - задача агЭнта па абъездке квартир?

Угу. В n-мерном пространстве. Посвящается Станиславу Лему.

 

[vitos]

Где ты тут нелинейность увидел?

Расстояние меж точками как считается тока так шоп без квадратов и корня?

 

[vitos]

Угу. В n-мерном пространстве. Посвящается Станиславу Лему.

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

 

[Ferox]

Расстояние меж точками как считается тока так шоп без квадратов и корня?

Расстояние между точками может определяться различными метриками, в зависимости от свойства указанного n-мерного пространства. Искомый алгоритм не зависит от метрики. Можешь считать что метрика равна сумме модулей разностей координат по каждому из изменений. Без квадратов и корней.

что есть там еще пространства как бы если ты маршрут на карте прямыми линиями нарисуешь

Какой-то набор слов без смысла. Изъясняйся пожалуйста яснее.

 

[vitos]

линейку бери и айда мерять

А **** та мерить - 40 см и это в неэрегированном состоянии!

Расстояние между точками может определяться различными метриками, в зависимости от свойства указанного n-мерного пространства. Искомый алгоритм не зависит от метрики. Можешь считать что метрика равна сумме модулей разностей координат по каждому из изменений. Без квадратов и корней.

Модуль это уже нелинейная операция. Потому к примеру МНК использует квадраты и там можно получить аналитическое решение.

Какой-то набор слов без смысла. Изъясняйся пожалуйста яснее.

Ну вот ты и покажи как это - яснее.

 

[bizon2006]

Количество точек ограниченно? Расстояние до ближайшей это прямая?

 

[lugal]

Есть точки в n-мерном пространстве. Для каждой точки нужно найти расстояние до ближайшей. Сумма таких минимальных расстояний по всем точкам является ответом. В такой формулировке решение задачи просто и понятно (кому не понятно можно дальше не читать).

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

Требуется придумать оптимальный по быстродействию алгоритм.

Шо студенты не могут решить задачу?
А шо хоть за пространство? Метрическое? Какое именно? Может метрику приведешь?

Количество точек ограниченно? Расстояние до ближайшей это прямая?

Расстояние это метрика. А прямая или нет зависит от пространства.

 

[BigBrother]

Есть точки в n-мерном пространстве. Для каждой точки нужно найти расстояние до ближайшей. Сумма таких минимальных расстояний по всем точкам является ответом. В такой формулировке решение задачи просто и понятно (кому не понятно можно дальше не читать).

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

Требуется придумать оптимальный по быстродействию алгоритм.

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

Расстояние это метрика. А прямая или нет зависит от пространства.

Кривая из линейного в нелинейном таки может быть прямой

 

[Lyalyuk]

Используйте "Жадный" алгоритм

 

[Klez]

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

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

Кстати, по поводу N-мерного пространства, есть ли кривизна этого пространства?

 

[Achenar]

По-моему, это таки задача коммивояжера. Смотрите сами, есть M полностью определенных точек, и N точек, у которых не хватает координат.

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

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

Реализация простая, но сложность - N!.

Тут не столько алгоритм, сколько доказательство, что это коммивояжер, а для него доказано давно, что проще N! не будет.

 

[avbua]

Берем точку из N и приближаем ее к одной из M

Зачем? Тем самым ты отдаляешь эту точку от другой из области N с которой у неё минимальное расстояние, тем самым ухудшая решение.

 

[Ferox]

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