Написание более быстрого алгоритма возврата в Python - PullRequest
Новая
       8

Написание более быстрого алгоритма возврата в Python

0 голосов
/ 06 декабря 2018

Я изучаю алгоритмы возврата и написал программу из подмножеств .Вот программа: 

items = range(1, 10)
result = []
def backtracking(array, target, temparray= []):
    if target == 0:
        result.append(temparray)
        return

    for index, item in enumerate(array):
        if item > target:
            return
        temparray.append(item)
        backtracking(array[index+1:], target - item, temparray[:])
        temparray.pop()
    return

backtracking(items, 8)
[print(arr) for arr in result]

То есть, чтобы получить сумму 8 из значений от 1 до 9 (без повторов), мы получим этот вывод: - 

[1, 2, 5]
[1, 3, 4]
[1, 7]
[2, 6]
[3, 5]
[8]

Выходэто хорошо, но когда я делаю то же самое для любого числа выше 50, он продолжает работать как всегда.Я ждал почти час и все еще не мог получить результат, поэтому мне пришлось внезапно завершить программу.То же самое было моим опытом с другими backtracking проблемами, когда значения стремятся приблизиться к 40-50.Похоже, что backtracking по своей сути очень медленный, поскольку включает recursion и много function calls.

Я хочу спросить, есть ли что-нибудь, что могло бы ускорить процесс в целом при реализации backtracking algorithms.Есть ли другие, более эффективные algorithms, которые будут использоваться на его месте?Memoization не работает как список, поскольку аргументы не могут быть хешируемыми.

Я разработал несколько интересных решений для некоторых вопросов Project Euler, но не могу получить ответ для больших значений.Я знаю, что мой алгоритм правильный, но очень медленный.Пожалуйста помоги.

...