@ivodopyanov
NLP, python, numpy, tensorflow

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

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

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

Можно ли это делать лучше?
  • Вопрос задан
  • 36 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Вообще - это очень сложная задача. Даже в одномерном случае это получается что-то типа задачи размена монет. И главная проблема, что целевая функция - не линейная. Там или модули или квадраты вылезают в любом случае.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы