Это лучший способ решить сумму подмножества?

Я пробовал базовый способ быстрее решить проблему суммы подмножества, и я придумал это

Наивным способом является функция oldSS, которая проверяет все 2^n комбинаций. Но потом я заметил, что перед проверкой каждого случая вычисляю минимальное и максимальное значение, возможное для текущего сценария, и если цель лежит в стороне от этого диапазона, и потенциально там может быть решение, то только тогда выполняйте сценарий. Это функция newSS. Я проверял время, и оно дало мне это

9.91289400371
0.00154754789233

Я мог бы дополнительно улучшить время newSS, кэшируя значения getMinMax в глобальной переменной. Однако для наивного подхода время можно улучшить до 2 ^ (n/2), используя умный хак, который сокращает первоначальный список на 2, а затем выполняет наивный подход для каждого, а затем сравнивает два сгенерированных списка.

Но по сравнению со временем выполнения 2^(n/2), кто-нибудь знает, насколько хорошо работает функция newSS?

Спасибо

import timeit
from random import randint

def oldSS(lst, acc, target):
    if lst:
        return oldSS(lst[1:], acc+lst[0], target) or oldSS(lst[1:], acc, target)
    return acc==target

def randomList():
    l = []
    for i in range(20):
        l.append(randint(0,1000))
    return l
def getMinMax(lst):
    mi = 0
    mx = 0
    for i in lst:
        if i < 0:
            mi += i
        elif i > 0:
            mx += i
    return (mi, mx)
def newSS(lst, acc, target):
    if lst:
        a = False
        b = False
        mimx = getMinMax(lst[1:])

        nmi = acc+lst[0] + mimx[0]
        nmx = acc+lst[0] + mimx[1]
        if target >= nmi and target <= nmx:
            a = newSS(lst[1:], acc+lst[0], target)

        nmi = acc + mimx[0]
        nmx = acc + mimx[1]
        if target >= nmi and target <= nmx:  
            b = newSS(lst[1:], acc, target)
        return a or b
    return acc==target


if __name__ == '__main__':
    print timeit.timeit('oldSS(randomList(), 0, 60)', number=10, setup="from __main__ import oldSS,randomList")
    print timeit.timeit('newSS(randomList(), 0, 60)', number=10, setup="from __main__ import newSS,getMinMax,randomList")

python performance np complexity-theory subset-sum
person omega    schedule 08.05.2016    source источник
comment
Результаты такие же?   -  person Peter Wood    schedule 09.05.2016
comment
Я думаю, они должны быть одинаковыми. Я попробовал это с помощью `r = randomList() print oldSS(r, 0, 60) print newSS(r, 0, 60)` и `r = randomList() print oldSS([1,2,3], 0, 6) напечатайте newSS([1,2,3], 0, 6)` и он дал те же ответы.   -  person omega    schedule 09.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

Известно, что ветвь и граница уменьшают сложность задач в лучшем случае. Однако худший случай никогда не меняется. Подумайте о наборе чисел, в которых нижняя и верхняя границы промежуточных итогов очень близки к целевому значению. В этом случае вы не можете обрезать какую-либо значимую часть пространства поиска. В среднем вы можете значительно улучшить время работы. Вычислить точную среднюю сложность алгоритма ветвей и границ немного сложно, поскольку методы ветвей и границ очень чувствительны к входному распределению. Мое образованное, но немного ржавое предположение заключается в том, что сложность вашего нового алгоритма не будет ниже O (2 ^ n/2).

Если вам нужен научный ответ об асимптотической вычислительной сложности, я бы порекомендовал провести некоторое исследование, или вы можете задать вопрос на бирже стека CS. Если вы просто пытаетесь понять, какой подход работает лучше, вы можете провести эмпирические испытания, чтобы сравнить их. Такое испытание было бы наилучшим практическим подходом.

person infiniteRefactor    schedule 08.05.2016