Подтвердить что ты не робот

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

Скажем, у вас есть два списка: 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].

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

4b9b3361

ОТВЕТЫ

Ответ 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, используя формулу Ryser, то k-я цифра константы в базе x указывает номер перестановок, для которых точечный продукт точно равен k. Более того, формула Райзера довольно немного быстрее, чем суммирование по всем перестановкам напрямую. (Но он все еще экспоненциальный, поэтому он не противоречит тому факту, что вычисление постоянного - это # ​​P-hard.)

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

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

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

Однако вы также можете прекомпопулировать на другом конце, когда назначено большинство значений list1. В этом случае вы можете составить отсортированный список промежуточных итогов для всех остальных значений. И помните, вы можете использовать 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. Алгоритм Райзера также воняет для этой проблемы без численных совпадений, поэтому для этого типа ввода я вижу только два ускорения: отрыв ветки дерева поиска с использованием теста "все" и "нет" и конечного кеша.

Ответ 2

Вероятно, нет (без упрощения предположения): ваша проблема 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).

Ответ 3

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

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

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

< ℕ n | (х <суб > Iсуб > х <суб > Jсуб > 1) <суб > (I, J ) ∈ A >

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

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

| RP <к югу > псуб > | = | S n | = n!

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

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

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

Ответ 4

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