fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача оптимизации
Сообщение28.01.2021, 18:46 


23/10/12
713
Изображение


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

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение28.01.2021, 18:57 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
Если близость определяется суммой квадратов отклонений от эталона, то похоже на "0-1 quadratic knapsack problem". Где прочитать про алгоритмы решения, не знаю.

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение28.01.2021, 19:05 


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

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение07.02.2021, 08:12 


12/07/15
3361
г. Чехов
Да, это задача оптимизации, а конкретнее: задача [бинарной] классификации. Применим метод ближайших соседей (NN, kNN) и прочие алгоритмы классификации из машинного обучения вплоть до нейронных сетей.

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение07.02.2021, 09:52 
Аватара пользователя


07/03/16

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group