Оптимизация грубой силы с помощью перестановок - PullRequest
Новая
       41

Оптимизация грубой силы с помощью перестановок

0 голосов
/ 25 октября 2018

ОБЪЯСНЕНИЕ, ЧТО ДЕЛАЕТ СЦЕНАРИЙ

Я написал скрипт на питоне, цель которого - сбалансировать шарики на круглой доске.Мрамор 1 весит 1 единицу, 2 весит 2 единицы и так далее.Цель состоит в том, чтобы найти лучший порядок, чтобы он был максимально сбалансированным.

ПРОБЛЕМА

Я также создал метод, который пробует все возможности с перестановками.Я получаю ошибку памяти, если я пытаюсь использовать более 10 шариков (3628800 возможных).

Есть ли способ оптимизировать код с помощью многопоточности / многопроцессорности, может быть, лучше, чем перестановки?

CODE # balance_game.py # Программа, используемая для умения балансировать шарики на доске 

from itertools import permutations
from math import cos, radians, pow, sin, sqrt
from time import time


# Checks if marbles will balance on a circular board
# Marble 1 weighs 1 unit, 2 weighs 2 units, and so on
def test_your_might(NUMBER_OF_MARBLES, marbles):
    angle = 360 / NUMBER_OF_MARBLES
    angles = [angle * n for n in range(1, NUMBER_OF_MARBLES + 1)]

    X = []
    Y = []
    Fx = []
    Fy = []

    i = 0
    for n in range(0, NUMBER_OF_MARBLES):
        angle = radians(angles[i])
        X.append(cos(angle))
        Y.append(sin(angle))
        i += 1

    for n in range(0, NUMBER_OF_MARBLES):
        Fx.append(X[n] * marbles[n])

    for n in range(0, NUMBER_OF_MARBLES):
        Fy.append(Y[n] * marbles[n])

    return sqrt(pow(sum(Fx), 2) + pow(sum(Fy), 2))


def brute_force_solution(NUMBER_OF_MARBLES):
    possibilities = permutations([x for x in range(1, NUMBER_OF_MARBLES + 1)])
    solutions = {}
    for possibility in possibilities:
        possibility = list(possibility)
        solution = test_your_might(NUMBER_OF_MARBLES, possibility)
        solutions[str(possibility)] = solution
    return solutions


# print(test_your_might(5, [5, 1, 4, 3, 2]))
t0 = time()
solutions = brute_force_solution(10)
t1 = time()

best_order = min(solutions, key=solutions.get)
lowest_score = solutions[best_order]

print(f"Lowest score: {lowest_score}\nOrder: {best_order}")
print(f"It took {t1-t0} seconds to find the best possibility")
print(f"There were {len(solutions)} possibilities")

К вашему сведению, метод brute_force_solution

1 Ответ

0 голосов
/ 25 октября 2018

Поскольку узким местом является использование ЦП, многопоточность здесь мало чем поможет, но многопроцессорность должна.Не эксперт, но недавно экспериментировал с параллелизмом, поэтому попробую поиграть и обновлю этот ответ, если я доберусь куда-нибудь.(РЕДАКТИРОВАТЬ: я попытался несколько попыток использовать многопроцессорность, но мне удалось только увеличить время выполнения!)

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

def brute_force_solution(NUMBER_OF_MARBLES):
    possibilities = permutations([x for x in range(1, NUMBER_OF_MARBLES + 1)])
    # count the number of solutions
    number_of_solutions = 0
    best_solution_so_far = None

    for possibility in possibilities:
        number_of_solutions += 1
        possibility = list(possibility)
        solution = test_your_might(NUMBER_OF_MARBLES, possibility)
        # If this solution is the best so far, record the score and configuration of marbles.
        if (best_solution_so_far is None) or (solution < best_solution_so_far[1]):
            best_solution_so_far = (str(possibility), solution)

    # Return the best solution and total number of solutions tested.
    return (best_solution_so_far, number_of_solutions)


t0 = time()
one_solution = brute_force_solution(11)
t1 = time()

best_order = one_solution[0][0]
best_score = one_solution[0][1]
number_of_solutions = one_solution[1]

Потребовалось некоторое время, но оно работало с 11 шариками: 

>>>Lowest score: 0.00021084993450850984
>>>Order: [10, 7, 3, 4, 11, 1, 8, 9, 5, 2, 6]
>>>It took 445.57227993011475 seconds to find the best possibility
>>>There were 39916800 possibilities

и был незначительно быстрее при запуске на 10 (и учтите, что вы не учитываете сортировку результатов в своем времени, что не нужно с этим новым методом, и добавляет еще одну секунду к вашему времени, чтобы получитьлучшее решение):

Старый 

Lowest score: 1.608181078507726e-17
Order: [1, 7, 3, 10, 4, 6, 2, 8, 5, 9]
It took 43.81806421279907 seconds to find the best possibility
There were 3628800 possibilities

Новый 

Lowest score: 1.608181078507726e-17
Order: [1, 7, 3, 10, 4, 6, 2, 8, 5, 9]
It took 37.06034016609192 seconds to find the best possibility
There were 3628800 possibilities
...