Как я могу эффективно найти подмножество мероприятий, которые остаются в рамках бюджета и максимизируют полезность? - PullRequest
Новая
       56

Как я могу эффективно найти подмножество мероприятий, которые остаются в рамках бюджета и максимизируют полезность?

1 голос
/ 29 июля 2011

Я пытаюсь разработать алгоритм для выбора поднабора действий из большого списка.Если выбрано, каждое действие использует некоторое количество фиксированного ресурса (т.е. сумма по выбранным действиям должна оставаться в общем бюджете).Может быть несколько возможных подмножеств, и способы их выбора будут основаны на расчете альтернативной стоимости невыбранных операций.

РЕДАКТИРОВАТЬ: Существует две причины этогоэто не проблема 0-1 для ранца :

  • Для ранца требуются целочисленные значения весов (т. е. потребляемых ресурсов), тогда как потребление ресурсов (т. е. масса на языке рюкзака)непрерывная переменная.(Очевидно, что можно выбрать некоторый уровень точности и квантовать требуемые ресурсы, но размер моей корзины должен быть очень маленьким, а рюкзак - O(2^n) в Вт.
  • Я не могу рассчитать альтернативную стоимость априори;то есть я не могу оценить пригодность каждого из них независимо, хотя я могу оценить полезность данного набора выбранных действий или предельную полезность от добавления дополнительной задачи в существующий список.

Проведенное мною исследование предлагает наивный подход:

Определение блока питания
Для каждого элемента блока питания рассчитайте его полезность на основе элементовотсутствует в наборе
Выберите элемент с наибольшей полезностью

Однако я знаю, что есть способы ускорить время выполнения и требуемую память. Например:

  • полное перечисление powerset - O(2^n), но мне не нужно полностью перечислять список, потому что, как только я нашел набор задач, который превышает бюджет, я зналБлагодаря тому, что любой набор, который добавляет больше задач, неосуществим и может быть отклонен.То есть, если {1,2,3,4} неосуществимо, то же самое можно сказать и о {1,2,3,4} U {n}, где n - это любая из задач, остающихся в большом списке.
  • Поскольку я просто суммирую, порядок задач не имеет значения(т. е. если возможно {1,2,3}, то {2,1,3}, {3,2,1} и т. д.).
  • Все, что мне нужно в конце концов, - это выбранный набор, поэтому мне, вероятно, нужно только лучшее значение утилиты, найденное на данный момент для целей сравнения.
  • Мне не нужно хранить перечисления списка,пока я могу быть уверен, что я посмотрел на все возможные.(Хотя я думаю, что сохранение суммы долга для ранее вычисленных возможных подмножеств может ускорить выполнение.)

Я убедил себя, что хороший алгоритм рекурсии будет работать, но я не могу понять,как определить его, даже в псевдокоде (что, вероятно, наиболее целесообразно, потому что он будет реализован на нескольких языках - возможно, Matlab для прототипирования, а затем скомпилированный язык позже).

Ответы [ 3 ]

2 голосов
/ 29 июля 2011

Задача о ранце является NP-полной, что означает, что не существует эффективного способа решения проблемы. Однако есть решение с псевдополиномиальным временем, использующее динамическое программирование. См. раздел Википедии для получения более подробной информации.

Однако, если максимальная полезность велика, вам следует придерживаться алгоритма аппроксимации. Одна из таких схем приближения состоит в том, чтобы жадно выбирать предметы, которые имеют наибольшую полезность / стоимость. Если бюджет большой, а стоимость каждого предмета мала, это может сработать очень хорошо.

РЕДАКТИРОВАТЬ: Поскольку вы определяете полезность с точки зрения предметов, не входящих в набор, вы можете просто переопределить ваши расходы. Отрицайте стоимость, а затем сдвиньте все так, чтобы все ваши значения были положительными.

1 голос
/ 29 июля 2011

Как уже упоминали другие, вы пытаетесь решить какую-то проблему с рюкзаком. Хотя теоретически вы обречены, на практике вы можете многое сделать для повышения производительности вашего алгоритма. Вот некоторые (дико различающиеся) идеи:

  • Имейте в виду Откат . Это соответствует вашему наблюдению, что после того, как вы вычеркнули {1, 2, 3, 4} в качестве решения, {1, 2, 3, 4} u {n} не стоит смотреть.
  • Применить Динамическое программирование Методы.
  • Проясните ваши фактические требования :
    • Может быть, вам не нужен набор best ? Будет ли хороший делать? Я не знаю, есть ли алгоритм, который обеспечивает хорошее решение за полиномиальное время, но вполне может быть.
    • Может быть, вам не нужен лучший набор все время ? Используя рандомизированные алгоритмы, вы можете решить некоторые NP -проблемы за полиномиальное время с риском сбоя в 1% (или что вы считаете «достаточно безопасным») всех выполнений.

(Помните: одно дело знать, что проблема остановки не разрешима, а другое - создать программу, которая определяет, будут ли реализации «hello world» работать неопределенно долго.)

0 голосов
/ 09 августа 2011

Я думаю, что следующий итерационный алгоритм будет проходить через весь набор решений и сохранять список задач, общую стоимость их выполнения и альтернативную стоимость невыполненных задач.

Похоже, что он будет выполняться в псевдополиномиальное время: полиномиальное по количеству действий и экспоненциальное по количеству действий, которые могут вписаться в бюджет. 

ixCurrentSolution = 1

initialize empty set solution {
    oc(ixCurrentSolution)        = opportunity cost of doing nothing
    tasklist(ixCurrentSolution)  = empty set
    costTotal(ixCurrentSolution) = 0
    }

for ixTask = 1:cActivities
    for ixSolution = 1:ixCurrentSolution 
        costCurrentSolution = costTotal(ixCurrentSolution) + cost(ixTask)
        if costCurrentSolution < costMax
             ixCurrentSolution++
             costTotal(ixCurrentSolution) = costCurrentSolution 
             tasklist(ixCurrentSolution)  = tasklist(ixSolution) U ixTask 
             oc(ixCurrentSolution)       = OC of tasks not in tasklist(ixCurrentSolution)
        endif
    endfor
endfor
...