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


Допустим, у вас есть два списка: 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) <некоторое заданное значение?

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

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


12


источник


Ответы:


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

Существует класс подсчета #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-hard.)

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

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


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

Однако вы также можете прекомпопулировать на другом конце, когда назначены большинство значений списка1. В этом случае вы можете составить отсортированный список промежуточных итогов для всех остальных значений. И помните, вы можете использовать list1 по порядку и делать все перестановки на стороне списка2. Например, предположим, что последние три записи списка 1 [4,5,6], и предположим, что три из значений в списке2 (где-то посередине) являются [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 в любом случае.) В отличие от кеша head, кеш-код может значительно ускорить код, даже если есть нет числовых совпадений среди записей списка1 и list2. Алгоритм Райзера также воняет для этой проблемы без численных совпадений, поэтому для этого типа ввода я вижу только два ускорения: отрыв ветви дерева поиска с использованием теста «все» и «нет» и конечного кеша.


9



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

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).


8



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

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

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

<ℕ N  | ( Икс я Икс J -1 ) (i, j) ∈ A  >

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

Назовите группу отражений «RP N "(это должно иметь другое имя, но память не работает). RP N  изоморфна симметрической группе S N , таким образом

| RP N | = | S N | = n!

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

RP» 4  построено из 4 подпространств, изоморфных ℤ 6 , В общем, RP ' N  построена из n подпространств, изоморфных RP ' н-1 ,

Здесь мои абстрактные мышцы алгебры действительно начинают терпеть неудачу. Я постараюсь продолжать работать над строительством, но ответ Манагу не оставляет большой надежды. Я боюсь, что сокращение RP 3  до ℤ 6  это единственное полезное сокращение, которое мы можем сделать.


2



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


0



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