时间戳

首页 > 解决方案 > 使用排列优化蛮力

python-3.x - 使用排列优化蛮力

问题描述

解释脚本的作用

我制作了一个 python 脚本，目标是在圆形板上平衡弹珠。大理石 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

标签： python-3.xoptimizationpython-multiprocessingpython-multithreadingbrute-force

解决方案

由于瓶颈是 CPU 使用率，多线程在这里不会有太大帮助，但多处理应该。不是专家，但最近一直在尝试并行性，所以如果我得到任何地方，我会尝试并更新这个答案。（编辑：我已经尝试了多次使用多处理的尝试，但我只成功地增加了运行时间！）

可能是您需要存储所有解决方案，但如果不需要，那么在时间方面的一个小优化，但在内存方面却是巨大的，就是不存储所有可能的结果而只存储最佳结果，所以你不要不必要地创建另一个很长的数组。理想情况下，您可以直接计算解决方案的数量，因为它仅取决于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

推荐阅读