У меня есть коллекция $ C $ уникальных двоичных 1-мерных векторов длины $ n $, поэтому в этой коллекции есть $ 2 ^ {n-1} $ элементов, исключая один со всеми $ 0 $. Это не совсем powerset, потому что все элементы имеют одинаковую длину, но я использовал powerset для его создания и добавил $ 0 $ соответствующим образом. Например, когда $ n = 3 $,
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Каждый элемент имеет связанную функцию вознаграждения $ R $, где $ R (v) \ ge 0 $ для $ v \ in C $. Также возможно $ R (v) \ ge n $.
Это мои текущие наблюдения по $ R $ (проценты не точные, но репрезентативные):
- $ R (v) = 0 $ как $ 80 $% времени
- $ R (v) = 10 $ как $ 19 $% времени
- $ R (v)> 10 $ как $ 1 % времени
Короче говоря, большинство предметов в этой коллекции не принесут полезной награды. Награды не случайны, но я не знаю, как узнать, за каким распределением они следуют. Каков наилучший способ получить максимальное вознаграждение без необходимости go через все 2 ^ n-1 элемента?
Позвольте мне перефразировать вопрос с примером.
Я думаю о $ C $ как набор конфигураций переключателей вкл / выкл, и каждая конфигурация включает несколько лампочек (например, одна лампочка! = одна лампочка, 0010 может включать 0 лампочек, а 0110 может включать 5 лампочек). Какой самый быстрый способ найти максимальное количество включенных лампочек, если
- вряд ли любая из этих конфигураций включит лампочку,
- очень мало лампочек включат больше чем 10 лампочек, но есть несколько конфигураций, которые могут включать 100 лампочек.
Я пытался использовать вариант Витерби (используя совокупную сумму вознаграждений вместо вероятностей), в которой я Следите за тем, как изменение одного элемента даст максимальный результат, но я думаю, что реализация Branch and Bound или дерева решений будет лучше в этом случае. Алгоритм Geneti c не будет работать, потому что распределение вознаграждений слишком смещено к 0 и 10. И подход с использованием грубой силы для одного за один раз будет длиться вечно, если $ n $ велико.
Какие-либо предложения? Мне придется написать это, но я хочу почувствовать решение.