Как найти сумму N векторов, взятых по одному из N множеств векторов, ближайшую к заданному вектору?
Дано: вектор V и N множеств векторов Wi (размеры множеств - любые, вектора - любые; не обязательно ортогональные; могут повторяться)
Мне надо взять по одному векторов из множеств W так, чтобы их сумма была близка к V.
Сейчас я делаю что-то типа симплекс метода - выбираю стартовые N векторов и попарно их оптимизирую. Но для этого приходится искать минимум среди всех попарных сочетаний Wi (плюс остальные вектора, минус V - ну это понятно).
Вообще - это очень сложная задача. Даже в одномерном случае это получается что-то типа задачи размена монет. И главная проблема, что целевая функция - не линейная. Там или модули или квадраты вылезают в любом случае.
Поэтому симплекc метод тут никак не поможет. Это задача квадратичного программирования, в лучшем случае.
Тут или полный перебор, или какой-нибудь метод отжига придется делать. В одномерном случае при небольших числах можно какое-нибудь динамическое программирование использовать, но это вряд ли ваш случай.
