Stefan_Lang
Это не вопрос программирования. Речь идет о поиске алгоритма, который дает вам правильный результат. Кроме того, речь может идти о поиске алгоритма, который быстро даст вам результат, но вы этого не сказали. В любом случае, вы можете получить больше ответов, если просто удалите языковые теги.
Хитрость в поиске (и оценке) алгоритмов заключается в том, чтобы найти *некоторый* способ, который работает, а затем проверить, работает ли он в угловых случаях, или если есть что-то, что вы можете сделать, чтобы ускорить его, если он слишком медленный.
Самый простой подход к практически любой проблеме с ограниченным числом потенциальных решений называется "грубой силой". Грубая сила означает, что вы пробуете все возможные комбинации и выясняете, какая из них работает.
В этом случае единственная проблема заключается в том, каковы комбинации, и как я могу убедиться, что я пробую их все? Итак, давайте рассмотрим задачу: у вас есть m рабочих мест и n людей, которые могли бы работать на любом из этих рабочих мест. Это типичная задача планирования. Вы можете выразить эту задачу в виде списка назначений заданий людям, например {задание 1, Лицо 1}, {Задание 2, лицо 3}, задание 3, лицо 1}, {Задание 4, лицо 4}. Поскольку каждая работа указана ровно один раз, и порядок не имеет значения, вы можете перечислить это так же, как список людей вместо этого, где номер работы подразумевается позицией в списке. Для приведенного выше примера это будет { 1, 3, 1, 4 }.
Исходя из этой нотации, если вы хотите выразить все расписания, вам понадобятся списки планирования, подобные этому, со следующими условиями:
1. каждая позиция списка соответствует одному из m заданий, поэтому список содержит m элементов.
2. Каждый из m элементов соответствует номеру одного из n человек, которые будут обрабатывать задание на данной должности, поэтому это может быть любое число от 1 до n
Это означает, что вам нужно настроить контейнер для списков из m чисел, затем сгенерировать все комбинации таких списков, повторяя каждый элемент от 1 до n, и добавить эту комбинацию в ваш контейнер.
Когда у вас есть этот контейнер, вы должны найти лучший, то есть тот, который приводит к наименьшему времени обработки. Для этого вам нужна функция, которая вычисляет время обработки для данного графика. Это не должно быть трудно написать эту функцию.
Для приведенного примера вы получите 5*5*5*5=625 графиков. В более крупных примерах общее число расписаний может быть слишком большим для хранения, поэтому вместо того, чтобы хранить их в контейнере, вы должны просто генерировать по одному расписанию за раз, оценивать время обработки и хранить это расписание только в том случае, если оно является одним из лучших.
Кроме того, для более крупных примеров оценка каждого расписания будет слишком трудоемкой: вы должны подумать о способах сокращения числа расписаний для тестирования. Но я не буду углубляться в это здесь - сейчас для вас важно только понять, как найти "решение", даже если оно не самое лучшее.
Rick York
По сути, именно так работает программа, над которой я работаю. Проблема не имеет только одного правильного ответа, поэтому я должен попробовать все возможности, а затем определить, какая из них была лучшей. Сейчас я использую графический процессор для этого.