时间戳

首页 > 解决方案 > 蛮力算法牛运输的问题

python - 蛮力算法牛运输的问题

问题描述

我正在研究优化问题，但遇到了作业问题。我必须编写一个蛮力算法来最小化飞船旅行的次数。问题是：外星人创造了一种新型的奶牛，现在他们想用最少的旅行次数把它运回来。每次行程的最大值为 10 吨。

这个练习提供了一些东西，比如这个算法来获取一个列表的所有可能的分区： 


# From codereview.stackexchange.com                    
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]

输入是奶牛的字典，例如：cows = {'Jesse': 6,'Maybel': 3, 'Callie': 2, 'Maggie': 5}，键是奶牛的名字和该值是母牛的重量（以吨为单位）。

输出必须是列表列表，其中每个内部列表代表一次旅行，例如：[['Jesse', 'Callie'], ['Maybel', 'Maggie']]

我的问题是：如何使用 get_partitions() 实现这个算法？DFS 是解决这个问题的好方法吗？

我已经尝试了很多方法，但是我在 stackoverflow 找到了其中两种方法，似乎更接近答案：

这是我从正确答案中得到的最接近的结果。首先，我使用 get_partitions 生成所有可能的分区，然后我将分区过滤到一个名为 possible 的列表中，其中仅包含行程，limit <= 10并且行程中包含所有奶牛（排除那些只有一个或两个奶牛名称的分区）。

def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips
        Use the given get_partitions function in ps1_partition.py to help you!
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation

    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)

    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    possible_combinations = []
    for partition in get_partitions(cows.keys()):
        possible_combinations.append(partition)
    possible_combinations.sort(key=len)

    def _is_valid_trip(cows, trip):
        valid = False
        for cow_name in cows:
            if cow_name in trip:
                valid = True
            else:
                valid = False
        return valid

    possibles = []
    for partition in possible_combinations:
        trips = []
        for trip in partition:
            total = sum([cows.get(cow) for cow in trip])
            if total <= limit and _is_valid_trip(cows.keys(), trip):
                trips.append(trip)
            possibles.append(trips)

    all_possibilities = [possibility for possibility in possibles if possibility != []]
    return min(all_possibilities)

我的 TestCase 仍然给出：

AssertionError: Lists differ: [['Callie', 'Maggie']] != [['Jesse', 'Callie'], ['Maybel', 'Maggie']]

First differing element 0:
['Callie', 'Maggie']
['Jesse', 'Callie']


Second list contains 1 additional elements.
First extra element 1:
['Maybel', 'Maggie']

- [['Callie', 'Maggie']]
+ [['Jesse', 'Callie'], ['Maybel', 'Maggie']]

----------------------------------------------------------------------
Ran 5 tests in 0.009s

FAILED (failures=1)

标签： pythonpython-3.x

解决方案

这是我从正确答案中得到的最接近的结果。首先，我使用 get_partitions 生成所有可能的分区，然后我将分区过滤到一个名为 possible 的列表中，其中只有限制 <= 10 的行程，并且行程中包含所有奶牛（排除那些只有一个或两个奶牛名称的分区）。

这是正确的想法，除了最后一条语句，根据定义，集合的分区将只包含集合的所有元素一次。问题是您是从行程而不是分区构建列表，没有必要这样做，因为您已经在 possible_combinations 中生成了完整的分区集，您需要做的就是删除那些包含超过权重的行程的分区限制这会给你留下这样的东西：

def brute_force_cow_transport(cows, limit):
    ## Generate set of partitions
    possible_combinations = []
    for partition in get_partitions(cows.keys()):
        possible_combinations.append(partition)
    possible_combinations.sort(key=len)

    valid_combinations = possible_combinations[:] ## or list.copy() if using python 3.3+

    ## Remove invalid partitions
    for partition in possible_combinations:
        for trip in partition:
            total = sum([cows.get(cow) for cow in trip])
            if total > limit:
                valid_combinations.remove(partition)
                break

    ## Return valid partition of minimum length
    return min(valid_combinations, key=len)

在这里，由于我们正在迭代分区，因此我们首先制作分区列表的副本，以便我们可以删除包含超出限制的行程的分区，然后返回最小长度的列表作为解决方案。有一些简单的方法可以提高它的性能，但它们留给读者作为练习。

推荐阅读