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

Question

Допустим, у вас есть два списка, L1 и L2, одинаковой длины, N. Мы определяем prodSum как:

def prodSum(L1, L2) :
    ans = 0
    for elem1, elem2 in zip(L1, L2) :
        ans += elem1 * elem2

    return ans

Существует ли эффективный алгоритм для определения, при условии, что L1 отсортирован, числа перестановок L2, такого, что prodSum (L1, L2) <какое-то предварительно заданное значение? </p>

Если это упростит проблему, вы можете предположить, что L1 и L2 оба являются списками целых чисел из [1, 2, ..., N].

Редактировать: ответ Манагу убедил меня, что это невозможно без предположения, что L1 и L2 являются списками целых чисел из [1, 2, ..., N]. Я все еще был бы заинтересован в решениях, которые предполагают это ограничение.

Answer 1

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

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

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

Таким образом, практический вопрос может сильно зависеть от интереса. Предположим, что порог находится на верхней стороне или на нижней стороне, или у вас достаточно памяти для приличного числа кэшированных результатов. Затем есть полезный рекурсивный алгоритм, который использует две идеи, одна из которых уже упоминалась: (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-сложным.)

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

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

---

Я понял, что есть другой вид кэширования / динамического программирования, который отсутствует в приведенном выше обсуждении и в приведенном выше коде. Кэширование, реализованное в коде, является кешированием на ранней стадии: если для list2 назначены только первые несколько значений list1, и если оставшийся порог встречается более одного раза, то кэш позволяет коду повторно использовать результат. Это прекрасно работает, если записи в 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. Алгоритм Райзера также воняет для этой задачи без числовых совпадений, поэтому для этого типа ввода я вижу только два ускорения: срезание ветви дерева поиска с использованием теста «all» и теста «none» и конечного кэша.

Answer 2

Вероятно, нет (без упрощающего предположения): ваша проблема - NP-Hard. Вот тривиальное сокращение до SUBSET-SUM . Пусть count_perms(L1, L2, x) представляет функцию «подсчитать количество перестановок L2 так, чтобы prodSum (L1, L2)

SUBSET_SUM(L2,n): # (determine if any subset of L2 adds up to n)
    For i in [1,...,len(L2)]
        Set L1=[0]*(len(L2)-i)+[1]*i
        calculate count_perms(L1,L2,n+1)-count_perms(L1,L2,n)
        if result positive, return true
    Return false

Таким образом, если бы был способ эффективно вычислить вашу функцию count_perms(L1, L2, x), то у нас был бы эффективный алгоритм для вычисления SUBSET_SUM (L2, n).

Answer 3

Это также оказывается проблемой абстрактной алгебры. Это было некоторое время для меня, но вот несколько вещей, чтобы начать. В этом нет ничего страшного (все это очень просто; это расширение того факта, что каждая группа изоморфна группе перестановок), но это дает другой взгляд на проблему.

Я попытаюсь придерживаться довольно стандартного обозначения: " x " - это вектор, а " x _i " - это i ^th компонент x . Если «L» является списком, L является эквивалентным вектором. « 1 ⁿ » - вектор со всеми компонентами = 1. Множество натуральных чисел taken считается положительными целыми числами. «[a, b]» - множество целых чисел от a до b включительно. «θ ( x , y )» - это угол, образованный x и y

Примечание prodSum является точечным произведением. Этот вопрос эквивалентен нахождению всех векторов L , сгенерированных операцией (перестановка элементов) в L2, так что θ ( L1 , L ) меньше заданного угла α. Операция эквивалентна отражению точки в 10 ⁿ через подпространство с представлением:

<ℕ <sup>n | ( x _i x _j ^-1 ) _{(i, j) ∈ A} >

, где i и j находятся в [1, n], A имеет хотя бы один элемент, а no (i, i) не находится в A (т. Е. A является нерефлексивным подмножеством [1, n] ² , где | A |> 0). Проще говоря (и более двусмысленно), подпространства - это точки, в которых один или несколько компонентов равны одному или нескольким другим компонентам. Отражения соответствуют матрицам, столбцами которых являются все стандартные базисные векторы.

Давайте назовем группу отражений "RP _n " (у нее должно быть другое имя, но память не работает). RP _n изоморфна симметрической группе S _n . Таким образом

| RP _п | = | S _n | = n!

В 3-х измерениях это дает группу порядка 6. Группой отражения является D ₃ , группа симметрии треугольника, как подгруппа группы симметрии куба. Оказывается, вы также можете генерировать точки, вращая L2 с шагом π / 3 вокруг линии вдоль 1 ⁿ . Это модульная группа 10 ₆ , и это указывает на возможное решение: найти группу порядка n! с минимальным числом генераторов и используйте его для генерации перестановок L2 в виде последовательностей с увеличением, а затем уменьшением угла с L2 . Оттуда мы можем попытаться сгенерировать элементы L с θ ( L1 , L ) <α (например, мы можем выполнить поиск в 1-й половине каждая последовательность для нахождения точки перехода, при этом мы можем указать остальную часть последовательности, которая удовлетворяет условию, и посчитать ее за время O (1). Давайте назовем эту группу RP '<sub> n .

RP ' ₄ состоит из 4 подпространств, изоморфных 110 ₆ . В более общем смысле, RP ' _n состоит из n подпространств, изоморфных RP' _n-1 .

Именно здесь мои абстрактные алгебраические мышцы действительно начинают выходить из строя. Я постараюсь продолжить работу над строительством, но ответ Манагу не оставляет большой надежды. Боюсь, что снижение RP ₃ до ℤ ₆ - единственное полезное снижение, которое мы можем сделать.

Answer 4

Похоже, что если l1 и l2 оба упорядочены по максимуму> минимуму (или минимуму> максимуму, независимо от того, имеют ли они одинаковый порядок), результат максимизируется, а если они упорядочены противоположно, результат минимизируется. и другие изменения порядка, кажется, следуют некоторым правилам; замена двух чисел в непрерывном списке целых чисел всегда уменьшает сумму на фиксированную величину, которая, по-видимому, связана с их расстоянием друг от друга (т.е. обмен 1 и 3 или 2 и 4 имеет одинаковый эффект). Это было просто из-за небольшого возни, но идея в том, что существует максимум, минимум, и если между ними есть какое-то предварительно заданное значение, есть способы подсчета перестановок, которые делают это возможным (хотя; если список не распределен равномерно, то нет. Ну, я не знаю, если l2 (1 2 4 5) поменять местами 1 2 и 2 4, это будет иметь разные последствия)