#algorithm
#алгоритм
Вопрос:
Мне нужна помощь, чтобы найти наилучший алгоритм / модель принятия решений (извините, я не знаю, как это точно назвать) для решения следующей проблемы. У меня есть ученики, живущие в городе, несколько школ в городе, и мне нужно назначить каждого ученика в школу, чтобы мы достигли «наилучшего сочетания критериев». Критериями являются, например:
- разнообразие (мальчики / девочки), близкое к разнообразию группы (т. Е. Не Все мальчики вместе)
- расстояние до школы
- возраст учащегося
- и в будущем может быть больше критериев
Мне нужно не решение, поэтому, например, точный список критериев пока не имеет значения. Мне нужен больше совет о возможных способах решения этой проблемы. «Единственный» способ, который я могу придумать на данный момент, — это написать алгоритм, чтобы попробовать все возможные комбинации учащихся и школ и каким-то образом вычислить оценку каждой комбинации (каждый критерий будет иметь «вес»), а затем выбрать решения с лучшими результатами. Но при таком подходе количество комбинаций может быть довольно большим, если мы возьмем, например, 1000 учащихся и 5 школ. Так что, возможно, есть другие способы сделать это. Язык программирования на данный момент не важен.
Заранее спасибо за любую помощь, которую вы можете предоставить 🙂
Комментарии:
1. Моя первая интуиция в этом заключается в том, что вам может понадобиться 2 набора критериев. 1. с точки зрения учащегося (расстояние до школы, …) и 2. с точки зрения школы (возраст, разнообразие, …). Я чувствую, что есть хороший шанс, что наличие этих 2 точек зрения может помочь упростить вычисления. Для 1. вы могли бы составить рейтинг любимых школ для каждого учащегося, для 2. затем вы могли бы впоследствии выбирать и выбирать учащихся с учетом рейтинга (учащиеся A и B одинаково привлекательны для школы, но A предпочитает школу …)
2. «вычислите оценку […], а затем выберите решения с лучшими результатами» — это в значительной степени определение генетического алгоритма . Единственное отличие заключается в том, что вы не пробуете все возможные комбинации. Вместо этого вы создаете небольшой пул комбинаций, а затем улучшаете эти решения, пока не получите приемлемый результат.
3. В более общем плане, начинать со случайного решения, а затем улучшать его, называется восхождением на холм . Вы могли бы, например, распределить учащихся по школам случайным образом. Затем найдите самого несчастного ученика в одной школе и поменяйте этого ученика на самого несчастного ученика в другой школе. Каждый обмен улучшит общее качество решения. Продолжайте менять местами, пока не достигнете приемлемого решения.
4. Если вы поищете область науки, которая занимается такими проблемами, вы найдете ее на стыке экономики и информатики под названием «Исследование операций». Я думаю, что ваша проблема подпадает под тему проблемы назначения в терминах OR.
5. Спасибо обоим, я думаю, теперь я понимаю, каким должен быть этот подход 🙂 Действительно, проверка всех возможных комбинаций невозможна
Ответ №1:
Это задача линейной оптимизации, обычно решаемая с помощью симплексного алгоритма: https://en.wikipedia.org/wiki/Simplex_algorithm