2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача оптимизации
Сообщение28.01.2021, 18:46 
Изображение


Имеется N кандидатов. Каждый из них оценивается по параметрам A, B, C и т.д. Параметры A, B, C - это числа от 0 до бесконечности. Необходимо объединить кандидатов в группу, чтобы сумма их параметров была максимально близка к заданной (A=x1, B=x2, C=x3).
Этот класс задач называется задачи оптимизации? Где почитать про алгоритмы решения?

 
 
 
 Re: Задача оптимизации
Сообщение28.01.2021, 18:57 
Аватара пользователя
Если близость определяется суммой квадратов отклонений от эталона, то похоже на "0-1 quadratic knapsack problem". Где прочитать про алгоритмы решения, не знаю.

 
 
 
 Re: Задача оптимизации
Сообщение28.01.2021, 19:05 
Можно ещё посмотреть на subset sum problem в оптимизационной формулировке. Есть приближённые полиномиальные алгоритмы, есть алгоритмы динамического программирования.https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm

 
 
 
 Re: Задача оптимизации
Сообщение07.02.2021, 08:12 
Да, это задача оптимизации, а конкретнее: задача [бинарной] классификации. Применим метод ближайших соседей (NN, kNN) и прочие алгоритмы классификации из машинного обучения вплоть до нейронных сетей.

 
 
 
 Re: Задача оптимизации
Сообщение07.02.2021, 09:52 
Аватара пользователя
randy в сообщении #1503099 писал(а):
Необходимо объединить кандидатов в группу, чтобы сумма их параметров была максимально близка к заданной (A=x1, B=x2, C=x3).

Для оптимизации требуется чтобы параметр оптимизации был один, а у вас их несколько. Поэтому требуется привести несколько параметров к одному. Способ приведения в каждой задаче определяется индивидуально. Это может быть, например, $\sum f(A-X_{1})+f(B-X_{2})+f(C-X_{3})$. Вид функции $f$ выбираете самостоятельно в зависимости от требований к разбросу разностей.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group