如何从所有蛮力组合中找到最佳解决方案？ [英] How to find best solution from all brute force combinations?

问题描述

我想从字典的所有蛮力组合中找到最佳解决方案。对于问题的背景，我需要找出在给定体重限制的情况下运输所有母牛所需的最少旅行次数。

I want to find the best solution from all brute force combinations of a dictionary. For the context of the problem, I need to find out the minimum number of trips needed to transport all the cows given a weight limit.

组合已经给我了使用辅助功能 get_partitions 。该函数返回一个嵌套列表，每个内部列表代表一个行程和该行程中的母牛的名字。

The combinations are already given to me with the helper functions get_partitions. The function returns a nested list, with each inner list represents a trip and names of cows on that trip.

Helper函数：

def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

def get_partitions(set_):
    for partition in partitions(set_):
        yield [list(elt) for elt in partition]

我想做的是按长度对所有组合进行排序，然后使用嵌套循环对其进行迭代。如果总重量超过限制，那么我会跳出内循环并将下一个子列表附加到另一个列表中。问题在于下一个子列表仍然包含分区中的剩余列表，因为它们的总权重低于限制。

What I tried to do was sorting all combinations by length then iterate over them with a nested loop. If the total weight exceed the limit, then I break out of the inner loop and append the next sublist to another list. The problem is that the next sublist still contain leftover lists from the partition since their total weight is below the limit.

我的代码：

def brute_force_cow_transport(cows, limit):

    # Generate and sort all combinations by length
    partitions = [item for item in get_partitions(cows)]
    partitions.sort(key=len)

    # Iterate over each sublist of combinations
    possibles = []
    for partition in partitions:
        trips = []
        for section in partition:
            total = sum([cows.get(cow) for cow in section])
            if total > limit:
                break
            else:
                # Appending next sublists create duplicates
                trips.append(section)
            possibles.append(trips)

    # Remove duplicates from possible solutions
    best = []
    for item in possibles:
        if item and item not in best:
            best.append(item)
    return min(best)

当我运行函数时，每次都会返回不同的结果。我认为这是因为我追加到结果中的剩余子列表引起了问题，但我不确定：

When I run my function, it keeps returning a different result each time. I think it's because the leftover sublists I appended to the results is causing the problem but I'm not sure:

cows = {'MooMoo': 50, 'Miss Bella': 25, 'Boo': 20, 
        'Milkshake': 40, 'Horns': 25, 'Lotus': 40}

>>> brute_force_cow_transport(cows, limit=100)
[['Boo', 'Miss Bella', 'MooMoo']]

正确的结果：

[['MooMoo', 'Horns', 'Miss Bella'], ['Milkshake', 'Lotus', 'Boo']]

如果有人可以帮助我指出我在哪里出错了，将不胜感激。

If anyone can help me point out where I went wrong, that would be greatly appreciated.

编辑：添加了辅助函数

推荐答案

我们可以将其视为深度优先搜索问题。

We can approach this as a depth-first-search problem.

def getCows(dict, limit):
    best_solution = []
    best_solution_score = 0

    def dfs(current_cows, current_total):
        nonlocal best_solution_score
        nonlocal best_solution
        if current_total > best_solution_score:
            #replace best solution
            best_solution = [tuple(sorted(current_cows))]
            best_solution_score = current_total
        elif current_total == best_solution_score:
            #add to best solution
            best_solution.append(tuple(sorted(current_cows))) 
        for cow, weight in dict.items():
            if cow not in current_cows and current_total + weight <= limit:
                #if adding next cow under limit recurse
                dfs(current_cows + [cow], current_total + weight)

    dfs([], 0)
    return list(set(best_solution)) #remove duplicates

cows = {'MooMoo': 50, 'Miss Bella': 25, 'Boo': 20,
    'Milkshake': 40, 'Horns': 25, 'Lotus': 40}


print(getCows(cows, limit=100))
>>>[('Horns', 'Miss Bella', 'MooMoo'), ('Boo', 'Lotus', 'Milkshake')]

这篇关于如何从所有蛮力组合中找到最佳解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！