Как найти сумму N векторов, взятых по одному из N множеств векторов, ближайшую к заданному вектору?

Question

[ivodopyanov]

Дано: вектор V и N множеств векторов Wi (размеры множеств - любые, вектора - любые; не обязательно ортогональные; могут повторяться)
Мне надо взять по одному векторов из множеств W так, чтобы их сумма была близка к V.

Сейчас я делаю что-то типа симплекс метода - выбираю стартовые N векторов и попарно их оптимизирую. Но для этого приходится искать минимум среди всех попарных сочетаний Wi (плюс остальные вектора, минус V - ну это понятно).

Можно ли это делать лучше?

Answer 1

[Wataru]

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

Поэтому симплекc метод тут никак не поможет. Это задача квадратичного программирования, в лучшем случае.

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