Динамическое программирование: сумма продуктов

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

Существует класс подсчета под названием #P, который является очень похоже на класс NP. В качественном отношении это даже сложнее, чем NP. Нет особых причин полагать, что эта задача подсчета лучше, чем # P-hard, хотя это может быть сложно или легко доказать.

Однако многие # P-сложные задачи и NP-сложные задачи сильно различаются по времени, которое требуется для решения на практике, и даже одна конкретная сложная задача может быть сложнее или проще в зависимости от свойств входных данных. NP-hard или # P-hard означают, что существуют сложные случаи. Некоторые задачи с NP-трудностью и # P-сложностью также имеют менее сложные случаи или даже совершенно легкие. (У других очень мало случаев, которые кажутся намного проще, чем самые сложные.)

Таким образом, практический вопрос может во многом зависеть от интересующей информации. Предположим, что порог находится на высоком или низком уровне, или у вас достаточно памяти для приличного количества кешированных результатов. Затем существует полезный рекурсивный алгоритм, который использует две идеи, одна из которых уже упоминалась: (1) После частичного присвоения некоторых значений оставшийся порог для фрагментов списка может исключить все перестановки или разрешить их все. (2) Если позволяет память, вы должны кэшировать промежуточные итоги для некоторого оставшегося порога и некоторых фрагментов списка. Чтобы улучшить кэширование, вы также можете выбрать элементы из одного из списков по порядку.

Вот код Python, который реализует этот алгоритм:

list1 = [1,2,3,4,5,6,7,8,9,10,11]
list2 = [1,2,3,4,5,6,7,8,9,10,11]
size = len(list1)
threshold = 396     # This is smack in the middle, a hard value

cachecutoff = 6     # Cache results when up to this many are assigned

def dotproduct(v,w):
    return sum([a*b for a,b in zip(v,w)])

factorial = [1]
for n in xrange(1,len(list1)+1):
    factorial.append(factorial[-1]*n)

cache = {}

# Assumes two sorted lists of the same length

def countprods(list1,list2,threshold):
    if dotproduct(list1,list2) <= threshold:            # They all work
        return factorial[len(list1)]
    if dotproduct(list1,reversed(list2)) > threshold:   # None work
        return 0
    if (tuple(list2),threshold) in cache:               # Already been here
        return cache[(tuple(list2),threshold)]
    total = 0
    # Match the first element of list1 to each item in list2
    for n in xrange(len(list2)):
        total += countprods(list1[1:],list2[:n] + list2[n+1:],
            threshold-list1[0]*list2[n])
    if len(list1) >= size-cachecutoff:
        cache[(tuple(list2),threshold)] = total
    return total

print 'Total permutations below threshold:',
print countprods(list1,list2,threshold)
print 'Cache size:',len(cache)

Как говорится в строке комментария, я тестировал этот код с жестким значением порога. Это немного быстрее, чем наивный поиск по всем перестановкам.

Есть другой алгоритм, который лучше этого, если выполняются три условия: (1) У вас недостаточно памяти для хорошего кеша, (2 ) записи списка представляют собой небольшие неотрицательные целые числа, и (3) вас интересуют самые жесткие пороги. Вторая ситуация для использования этого второго алгоритма - это если вы хотите, чтобы подсчеты для всех пороговых значений были ровными, независимо от того, выполняются ли другие условия. Чтобы использовать этот алгоритм для двух списков длины n, сначала выберите основание x, которое является степенью 10 или 2, которая больше факториала n. Теперь составьте матрицу

M[i][j] = x**(list1[i]*list2[j])

. Если вы вычислите перманент этой матрицы M, используя формулу Райзера , тогда k-я цифра перманента в базе x сообщает вам количество перестановок, для которых скалярное произведение равно k. Более того, формула Райзера работает немного быстрее, чем суммирование по всем перестановкам напрямую. (Но это все еще экспоненциально, поэтому это не противоречит тому факту, что вычисление перманента является # P-сложным.)

Кроме того, да, верно, что набор перестановок является симметричной группой. Было бы здорово, если бы вы могли каким-то образом использовать теорию групп, чтобы ускорить эту задачу подсчета. Но, насколько мне известно, из этого описания вопроса ничего такого глубокого не вытекает.

Наконец, если вместо точного подсчета количества перестановок ниже порогового значения вы захотите только приблизительно это число , тогда, наверное, игра полностью изменится. (Вы можете аппроксимировать перманент за полиномиальное время, но здесь это не помогает.) Я должен был бы подумать, что делать; в любом случае вопрос не в этом.

Я понял, что есть другой вид кэширования / динамического программирования, который отсутствует в приведенном выше обсуждении и в приведенном выше коде. Кэширование, реализованное в коде, представляет собой кеширование на ранней стадии: если только первые несколько значений list1 назначаются list2, а оставшийся порог встречается более одного раза, то кеш позволяет коду повторно использовать результат. Это отлично работает, если записи list1 и list2 являются целыми числами, которые не слишком велики. Но если записи являются типичными числами с плавающей запятой, это будет неудачный кэш.

Однако вы также можете выполнить предварительное вычисление на другом конце, когда большинство значений list1 было присвоено. В этом случае вы можете составить отсортированный список промежуточных итогов для всех оставшихся значений. И помните, вы можете использовать list1 по порядку и выполнять все перестановки на стороне list2. Например, предположим, что последние три записи list1 равны [4,5,6], и предположим, что три из значений в list2 (где-то посередине) равны [2.1,3.5,3.7]. Затем вы должны кэшировать отсортированный список из шести точечных произведений:

endcache[ [2.1, 3.5, 3.7] ] = [44.9, 45.1, 46.3, 46.7, 47.9, 48.1]

Что это для вас значит? Если вы посмотрите на код, который я опубликовал, функция countprods (list1, list2, threshold) рекурсивно выполняет свою работу с подпороговым значением. Первый аргумент, list1, мог бы быть лучше в качестве глобальной переменной, чем в качестве аргумента. Если list2 достаточно короткий, countprods может выполнять свою работу намного быстрее, выполняя двоичный поиск в endcache списка [list2]. (Я только что узнал из stackoverflow, что это реализовано в модуле bisect в Python, хотя код производительности в любом случае не будет написан на Python. ) В отличие от головного кеша, конечный кеш может значительно ускорить код, даже если нет числовых совпадений между записями list1 и list2. Алгоритм Райзера также плохо справляется с этой проблемой без числовых совпадений, поэтому для этого типа ввода я вижу только два ускорения: отсечение ветви дерева поиска с использованием теста «все» и теста «нет», а также конечный кеш.