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

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

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

Это теперь такие на экзамене в 1С дают? :))

(0) что за олимпиадные задачки?!

(1)Нет. Так для себя. Балуюсь.
(2)Надо оптимальный по быстродействию алгоритм.

А алгоритм который неоптимален по быстродействию, но всегда выдает лучший результат (в вещественных координатах) уже есть?

Угу. Для первой части.

(0) а реальное применение у этого есть?!

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

Теория оптимизации систем? )

(7) еще и функция кусочно-дифференцируемая

Было такое, там составляются эти самые уравнения, потом куча матриц считается ...
Когда-то деньги на этом зарабатывал)))

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

(10) Куча матриц - это симлекс метод, для случаев линейного программирования. Тут - нелинейный.

(11) Абсолютно понятно что методами первого порядка (Да и прямыми) упадем в локальный экстремум.

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

можно в матлабе поискать чтото...

(15) http://reactivmen.narod.ru/gl01/index121.htm

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

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

(17) А эта ссылка на что?!

(18) Дело в том, что например для задачи (0) - не понимая сути применяемых методов - ты не найдешь глобальный экстремум. Потому что например градиентные методы и методы второго порядка дадут только локальных экстремум.

(19) там нет индексации типа: нахождение оптимального пути - метод1,метод2, метод3. я написал письмецо автору сайта, посмотрим что ответит. но сайт все равно классный.

(14)Хм. Это мысль. Пойду попробую применить. Спасибо.

(22) может спрашивал, у тебя какое образование?

Техническое, высшее.

(24) сорри за переход на личную биография, но как ты успел оказаться в морпехах и в институте? или он (институт) был потом? и "Техническое, высшее." факультет и специальность назвать можешь? (спрашиваю из естественного любопытства)

(25) биография=биографию

А вот училище и специальность это уже секретная информация.

(27) чуйствовал такой ответ после "Техническое, высшее." )

А что у Вас не сочетается служба в морской пехоте и высшее техническое образование?

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

(30)Но вместе никак, я так понимаю. Ну что за вульгарные штампы.

(0) ты, случаем, не транспортную задачу решаешь?

(32) он просто вспоминает дифференцирование =)

(32)Не. Карту рисую.

(34) что за карта?

(35) карта Острова Сокровищ :)