Использование может использовать Branch and Bound.
Вы должны вступить в раздел «для задач i, которые задают, я выбираю?», Выбирая самый большой набор, чтобы в первую очередь вызвать сбои как можно выше в дереве, чтобы сохранить работу. Для первоначального решения вы можете перевернуть это, чтобы быстро найти разумное (но не оптимальное) решение, которое в конечном итоге помогает сохранить работу, сокращая больше в реальном поиске позже.
Вы также можете перейти на s[q,t] из следующей модели, которая ближе всего к 0.5 (в некотором роде, выбор, который является «наименее уверенным»).
Связанное может быть основано на линейной релаксации этой ILP модели:
maximize sum of x[t] over all t
variables:
0 <= x[t] <= 1 ; x[t] decides whether task t is scheduled or not
0 <= r[i,t] <= 1 ; r[i,t] decides whether task t uses resource i
0 <= s[q,t] <= 1 ; s[q,t] decides whether set q of task t is used
constraints:
1. for all tasks t: (sum s[q,t] over all valid q) - x[t] = 0
2. for all sets s[q,t]: (sum r[i,t] over all i in the set) - size_of_set * s[q,t] >= 0
3. for all resources i: sum r[i,t] over all t <= 1
- силы ровно 1 набор ресурсов, которые будут связаны с любой задачей, которая выбрана.
- заставляет ресурсы, используемые путем выбора набора q для задачи t, используемой задачей t (> = 0, потому что наборы могут перекрываться)
- заставляет все ресурсы использоваться не более одного раза.
Возможно, я допустил ошибки в модели, и я не уверен, насколько это хорошо. Во всяком случае, разрешите его с помощью линейного программирования (без сомнения, для него есть библиотека для Python), а затем сделайте несколько сокращений Гомори для хорошей меры (они могут выглядеть страшно, но на самом деле их довольно просто программировать), не слишком много, хотя , пытаясь получить целочисленное решение с разрезами Гомори, часто сходится очень медленно. Выполнение некоторых из них - дешевый способ улучшить решение.
Это даст вам оценку, которая позволит вам обрезать часть пространства поиска. Насколько это на самом деле чернослив зависит от того, насколько близко он доходит до фактического решения. Я предсказываю, что он будет стремиться выбирать несколько наборов, принадлежащих задаче, с некоторым коэффициентом от 0 до 1, потому что выбор набора «только бит» позволяет ему использовать один и тот же ресурс для нескольких задач. Он должен выбрать несколько наборов, потому что он должен использовать в общей сложности 1 набор для каждой задачи, но это также означает, что у него больше выбора ресурса, чтобы он мог это сделать. Линейное программирование настолько скрытно, что всегда пытается дать вам, в некотором смысле, самый неприятный ответ :)
Конечно, в этой модели вы исключили бы любые возможности, которые больше не возможны (выделенные ресурсы и наборы которые содержат их и задачи, которые будут иметь нулевые возможные множества) и пропустить запланированные задачи.
Если это слишком сложно, вы можете рассчитать гораздо более простую связь следующим образом: для всех задач t возьмите размер их самого маленького набора s[t]. Проверьте, сколько вы можете предпринять, пока общий размер не будет больше количества нераспределенных ресурсов (так что сделайте наименьшее, добавьте следующий маленький и т. Д.) Сортируйте их или используйте мини-кучу).
Конечно, если с выделенными ресурсами столько задач теперь без каких-либо возможных наборов, которые в общей сложности (включая те, которые были уже запланированы), вы не можете получить больше, чем лучшее решение до сих пор, вы можете дать вверх по текущей ветви дерева рекурсии.
Для первоначального решения вы можете попробовать использовать жадный алгоритм, который вы описали, но с одним изменением: возьмите самый маленький набор, содержащий только нераспределенные ресурсы. Таким образом, он пытается «уклониться от пути» дальнейших задач, хотя, очевидно, вы можете построить случаи, когда это хуже, чем выбор первого возможного набора.
Редактирование: и, конечно, если в наборе наборов заданий есть набор, являющийся надмножеством другого набора в этой коллекции, просто удалите его. Не может быть лучше использовать это супермножество. Это происходит, чтобы исправить пример, указанный в OP, но обычно это не так.
Большое вам спасибо за ваш исчерпывающий ответ! Это желание приложить все усилия, чтобы помочь незнакомцам с их проблемами программирования, которые делают этот сайт столь же полезным, как и он. – CarlEdman