MIT 6.0002 PS1: Space Cows Transportation

请注意,本文编写于 188 天前,最后修改于 170 天前,其中某些信息可能已经过时。

本文是我对 MIT 6.0002 课程(Introduction to Computational Thinking and Data Science)配套作业 Problem Set 1 的解答。这次作业涉及到了贪心算法和动态规划算法。

问题描述

详细的要求见原题,从 MIT OCW 下载原题:Problem Set 1: Space Cows Transportation (ZIP) (This ZIP file contains: 1 .pdf file, 2 .txt files, and 3 .py files)

Part A: Transporting Cows Across Space

Problem A.1: Loading Cow Data

从文件中读取数据到一个字典中,字典的键是字符串,值是整数(题目要求中说明了奶牛的重量是整数)。

我们使用with打开文件,这样做的好处在本文档末尾的“总结”中说明。打开文件后,循环读取文件中的每一行,以逗号分割成两个元素的列表,这两个元素分别为奶牛的名字和奶牛的重量,将它们作为键值对添加进字典cows_weights中。

注意到for line in file时,line的末尾有一个换行符,我们要用strip()方法丢弃换行符。另外要注意的是,需要把字典的值由字符串转换为整数。

def load_cows(filename):
    cow_weights = {}
    with open(filename) as file:
        for line in file:
            line_list = line.strip().split(',')  # 以逗号分隔
            cow_weights[line_list[0]] = int(line_list[1])  # 字符串:整数键值对
    return cow_weights

下面测试load_cows函数。题目为我们提供了两个数据文件,我们分别测试它们:

if __name__ == '__main__':
    print(load_cows('ps1_cow_data.txt'))
    print(load_cows('ps1_cow_data_2.txt'))

结果符合预期:

{'Maggie': 3, 'Herman': 7, 'Betsy': 9, 'Oreo': 6, 'Moo Moo': 3, 'Milkshake': 2, 'Millie': 5, 'Lola': 2, 'Florence': 2, 'Henrietta': 9}
{'Miss Moo-dy': 3, 'Milkshake': 4, 'Lotus': 10, 'Miss Bella': 2, 'Horns': 9, 'Betsy': 5, 'Rose': 3, 'Dottie': 6}

Problem A.2: Greedy Cow Transport

使用贪心算法,每次选择不超过限制的最重的奶牛加入一次运输,如果没有可以加入的奶牛,开启下一次运输,重复按贪心规则加入奶牛,直到不能再加入任何奶牛。特别注意终止条件应该是不能再加入任何奶牛,而不是加入了所有奶牛!这是因为,如果有重量超过 limit 的奶牛的话,后一种方式会导致死循环——永远不能加入重量超过 limit 的奶牛。虽然题目中假设了所有奶牛的重量不超过 10,但是谁能保证飞船的 limit 一定不小于 10 呢?

首先使用sorted函数按照奶牛的重量从大到小(reverse=True)排序,得到一个列表cows_sorted,这时cows_sorted[0]是重量最大的奶牛,cows_sorted[-1]是重量最小的奶牛。对于每一次运输,都从大到小遍历剩下的奶牛,将重量不超过 limit 的最重的奶牛加入运输。遍历完一遍以后,如果不满足上面的终止条件,则继续进行下一次运输。

由于我们使用sorted函数将cows由字典转换为列表了,因此是不会修改原来的cows参数的。这也符合题目中要求“不能修改字典cows”的要求。

def greedy_cow_transport(cows, limit=10):
    cows_sorted = sorted(cows.items(), key=lambda x:x[1], reverse=True)
    transports = []
    while cows_sorted and cows_sorted[-1][1] < limit:
        current_weight = 0      # 当次运输的重量
        current_transport = []  # 档次运输的奶牛名字
        for cow in cows_sorted.copy():  # 从大到小遍历
            if current_weight + cow[1] <= limit:
                current_transport.append(cow[0])
                current_weight += cow[1]
                cows_sorted.remove(cow)  # 从剩余奶牛列表中移除
        transports.append(current_transport)  # 添加一次运输
    return transports

下面测试greedy_cow_transport函数。在已有的两个数据集之外,我又提供了第三个数据集ps1_cow_data_3.txt,其中包含一只重量为 15 的奶牛(它超过了 limit)。ps1_cow_data_3.txt的内容如下:

Jesse,6
Maybel,3
Trump,15
Callie,2
Maggie,5

测试程序:

if __name__ == '__main__':
    print(greedy_cow_transport(load_cows('ps1_cow_data.txt')))
    print(greedy_cow_transport(load_cows('ps1_cow_data_2.txt')))
    print(greedy_cow_transport(load_cows('ps1_cow_data_3.txt')))

结果符合预期:

['Betsy'], ['Henrietta'], ['Herman', 'Maggie'], ['Oreo', 'Moo Moo'], ['Millie', 'Milkshake', 'Lola'], ['Florence']]
[['Lotus'], ['Horns'], ['Dottie', 'Milkshake'], ['Betsy', 'Miss Moo-dy', 'Miss Bella'], ['Rose']]
[['Jesse', 'Maybel'], ['Maggie', 'Callie']]

特别注意第三个测试,重量超过 limit=10 的 Trump 被丢弃了。

Problem A.3: Brute Force Cow Transport

get_partitions获取奶牛的所有组合,然后检查每个组合的每次运输是否都符合 limit 的限制,然后从那些符合限制的组合中选择一个运输次数最少的。“运输次数最少”的意思就是说内层列表的数量最少。由于逻辑简单,所以直接给出代码:

def brute_force_cow_transport(cows, limit=10):
    # 首先删除那些重量超过限制的奶牛
    cows_filtered = {k:v for k,v in cows.items() if v <= limit}

    transports = []
    for partition in get_partitions(cows_filtered):
        flag = True  # 当前分片是否有效
        for transport in partition:
            if sum(map(cows_filtered.get, transport)) > limit:
                flag = False
                break
        if flag:
            if len(partition) < len(transports) or len(transports) == 0:
                transports = partition
    return transports

以上代码中使用的语法糖是summap配合使用,实现了映射后求和的功能。map(cows_filtered.get, transport)transport中的每个元素调用cows_filtered.get函数,并返回一个迭代器(而不是列表)。然后sum对这个可迭代对象求和。

测试程序:

if __name__ == '__main__':
    print(brute_force_cow_transport(load_cows('ps1_cow_data.txt')))
    print(brute_force_cow_transport(load_cows('ps1_cow_data_2.txt')))
    print(brute_force_cow_transport(load_cows('ps1_cow_data_3.txt')))

结果符合预期:

[['Henrietta'], ['Maggie', 'Herman'], ['Lola', 'Oreo', 'Florence'], ['Betsy'], ['Millie', 'Milkshake', 'Moo Moo']]
[['Rose', 'Dottie'], ['Miss Bella', 'Miss Moo-dy', 'Betsy'], ['Milkshake'], ['Horns'], ['Lotus']]
[['Callie', 'Maybel', 'Maggie'], ['Jesse']]

Problem A.4: Comparing the Cow Transport Algorithms

为了使得能够在多个数据集上进行比较,我修改函数定义。原定义没有参数,我为其添加了一个参数filename,可以改变数据集的文件。

题目中要求使用time.time()进行计时,不过实际情况表明这样计算出来的时间不够精确。作为替代,我改用time.perf_counter(),它可以用来计算精确的处理器时间。在compare_cow_transport_algorithms中,分别为greedy_cow_transportbrute_force_cow_transport计时,然后输出运行的毫秒数,保留四位小数。保留小数用到了格式化字符串,这里不做过多说明。

def compare_cow_transport_algorithms(filename):
    cows = load_cows(filename)

    start = time.perf_counter()  # 开始:处理器时间
    greedy_result = greedy_cow_transport(cows)
    end = time.perf_counter()  # 结束:处理器时间
    print('--- Greedy algorithm ---')
    print('Result:', end=' ')
    print(greedy_result)
    print('Time cost:', end=' ')
    print('{:.4f} ms'.format((end-start)*1000))
    print()

    start = time.perf_counter()  # 开始:处理器时间
    brute_result = brute_force_cow_transport(cows)
    end = time.perf_counter()  # 结束处理器时间
    print('--- Brute force algorithm ---')
    print('Result:', end=' ')
    print(brute_result)
    print('Time cost:', end=' ')
    print('{:.4f} ms'.format((end-start)*1000))

测试程序:

if __name__ == '__main__':
    compare_cow_transport_algorithms('ps1_cow_data.txt')
    print()
    compare_cow_transport_algorithms('ps1_cow_data_2.txt')
    print()
    compare_cow_transport_algorithms('ps1_cow_data_3.txt')

结果:

--- Greedy algorithm ---
Result: [['Betsy'], ['Henrietta'], ['Herman', 'Maggie'], ['Oreo', 'Moo Moo'], ['Millie', 'Milkshake', 'Lola'], ['Florence']]
Time cost: 0.0222 ms
--- Brute force algorithm ---
Result: [['Henrietta'], ['Oreo', 'Florence', 'Lola'], ['Millie', 'Moo Moo', 'Milkshake'], ['Maggie', 'Herman'], ['Betsy']]
Time cost: 902.8110 ms

--- Greedy algorithm ---
Result: [['Lotus'], ['Horns'], ['Dottie', 'Milkshake'], ['Betsy', 'Miss Moo-dy', 'Miss Bella'], ['Rose']]
Time cost: 0.0167 ms
--- Brute force algorithm ---
Result: [['Rose', 'Dottie'], ['Horns'], ['Miss Bella', 'Miss Moo-dy', 'Milkshake'], ['Betsy'], ['Lotus']]
Time cost: 22.8560 ms

--- Greedy algorithm ---
Result: [['Jesse', 'Maybel'], ['Maggie', 'Callie']]
Time cost: 0.0297 ms
--- Brute force algorithm ---
Result: [['Maggie', 'Callie', 'Maybel'], ['Jesse']]
Time cost: 0.0989 ms

Problem A.5: Writeup

1.What were your results from compare_cow_transport_algorithms? Which algorithm runs faster? Why?

运行结果见上方。贪心算法明显比暴力算法快,且数据量越大差距越明显。在贪心算法中,平均情况下每头奶牛会被访问一次,因此平均情况下时间复杂度为$$O(n)$$;而在暴力算法中,get_partitions求得奶牛的所有划分(集合的划分称为“贝尔数(Bell Number)”),然后检查每个划分是否合法,复杂度显然高于线性。

2.Does the greedy algorithm return the optimal solution? Why/why not?

不是,贪心算法给出的不一定是最优解。贪心算法每次选取可用的最大重量,很快地将一次运输尽量填满,然而可能留下空隙,而这些空隙不能填任何一个奶牛,这时必须进行一次新的运输。这种方法可能会忽略某些巧妙的组合,使得每次运输都尽量不会留下空隙,因而可能导致更多的运输次数。比如在上面的ps1_cow_data.txt的测试中,贪心算法给出的结果是 6 次,而暴力算法给出的结果是 5 次。经过观察,发现贪心结果中有一项['Millie', 'Milkshake', 'Lola'],总重量为 5+2+2=9;而暴力结果中有['Oreo', 'Florence', 'Lola'],总重量为 6+2+2=10,完全填满了 limit 而没有留下任何空隙。总体来说,贪心结果留下了过多的空隙,从而导致它得到的不是全局最优解。

3.Does the brute force algorithm return the optimal solution? Why/why not?

是的。由于暴力算法检查了所有(全局)可能的解,并且从中选取了最小的一个,因此它是全局最优的。


Part B: Golden Eggs

Problem B.1: Dynamic Programming: Hatching a Plan

我们使用没有递归的动态规划,所以不需要使用memo参数。

动态规划的目标是找到总和为target_weight的尽可能少的数。初始化一个长为 target_weight+1 的数组(列表)dp,全部填 0。dp[i]的值表示重量为i时需要鸡蛋的最少个数。对于每一个dp[i],它一定是由一个比较小的数字加上一个新数字构成的,可用的数字在元组egg_weights中。递推关系如下:

$$ dp[i] = 1 + min\{dp[i-w]\mid w\in egg\_weights, w\leq i\} $$

Python 中有现成的min函数可供使用,用来表达递推关系非常方便。动态规划最终返回dp[target_weight]就是想要的答案。

注意一些细节问题,egg_weights中的数字必须包含 1,否则可能找不到解。还有,数字必须是由小到大按顺序排列的。使用两个断言来确保参数有效(详见“总结”)。

dp_make_weight的完整代码如下:

def dp_make_weight(egg_weights, target_weight, memo = {}):
    assert 1 in egg_weights
    assert all(x<y for x, y in zip(egg_weights, egg_weights[1:]))

    dp = [0 for i in range(target_weight+1)]
    for i in range(1, target_weight+1):
        dp[i] = 1 + min([dp[i-weight] for weight in egg_weights if weight<=i])
    return dp[target_weight]

进行五个测试,测试代码请直接参见源文件,下面是测试结果:

--- Test 1 ---
Egg weights = (1, 5, 10, 25)
n = 99
Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
Actual output: 9

--- Test 2 ---
Egg weights = (1, 5, 10, 20, 50)
n = 208
Expected ouput: 8 (4 * 50 + 1 * 5 + 3 * 1 = 208)
Actual output: 8

--- Test 3 ---
Egg weights = (1, 9, 90, 91)
n = 99
Expected ouput: 2 (1 * 90 + 1 * 9)
Actual output: 2

--- Test 4 ---
Egg weights = (1,)
n = 13
Expected ouput: 13 (13 * 1 = 13)
Actual output: 13

--- Test 5 ---
Egg weights = (1, 2, 4, 8, 16, 32, 64)
n = 127
Expected ouput: 7 (等比数列求和)
Actual output: 7

Problem B.2: Writeup

1.Explain why it would be difficult to use a brute force algorithm to solve this problem if there were 30 different egg weights. You do not need to implement a brute force algorithm in order to answer this.

这个问题的暴力算法叙述如下:首先确定鸡蛋数量的上界——如果全部选择重量为 1 的鸡蛋,那么target_weight的值就是最多需要的鸡蛋数量。从egg_weights中找出所有总个数小于等于这个上界的鸡蛋的所有组合,然后判断每一个组合是否符合总重量等于target_weight的要求。举例说明,倘若有 30 种不同重量的鸡蛋,那么最多需要 30 个重量为 1 的鸡蛋。然后尝试 29 个鸡蛋的所有组合可不可以构成总重量等于 30;然后尝试 28 个鸡蛋的所有组合可不可以构成总重量等于 30;然后尝试 27 个鸡蛋的所有组合可不可以构成总重量等于 30……最后尝试只有 1 个鸡蛋的可不可以构成总重量等于 30,我们要从以上遍历中找出鸡蛋数量最少的。对于组合问题来说,时间复杂度是很高的,因此不可取。

2.If you were to implement a greedy algorithm for finding the minimum number of eggs needed, what would the objective function be? What would the constraints be? What strategy would your greedy algorithm follow to pick which coins to take? You do not need to implement a greedy algorithm in order to answer this.

若使用贪心算法,目标函数是鸡蛋的数量,我们要最小化鸡蛋的数量。约束是所有选取的鸡蛋重量之和等于target_weight鸡蛋的重量只能从egg_weights中选取。使用贪心算法的策略是,首先尽可能多选取比target_weight小的最大重量的鸡蛋,直到如果再多添加一个就会超过,然后尽可能多选取比剩余重量小的最大重量的鸡蛋,如此进行下去。因为一定有重量为 1 的鸡蛋,因此这个过程一定可以结束,也就是说这个问题一定有解。

3.Will a greedy algorithm always return the optimal solution to this problem? Explain why it is optimal or give an example of when it will not return the optimal solution. Again, you do not need to implement a greedy algorithm in order to answer this.

不是,贪心算法不一定给出最优解。下面是一个反例:egg_weights = (1,9,90,91)target_weight = 99,在这个例子中,采用贪心算法的过程是——首先选取 91,剩余 99-91=8,然后只能选取 8 次 1,总数量为 1+8=9。然而,最优解是选取一个 90 和一个 9,总数量为 2。这个反例可以说明贪心算法给出的不是最优解。

总结

  • with进行文件读取官方文档with的解释是“with语句用于包装带有使用上下文管理器定义的方法的代码块的执行。 这允许对普通的 try...except...finally 使用模式进行封装以方便地重用。”大致意思就是使用with封装了常用操作,是我们的代码更便捷。在读取文件这个操作上,使用with打开文件,一不需要显式地处理打开失败的异常,二不需要显式地关闭文件,使用更加方便。
  • allall()函数用于判断给定的可迭代参数中的所有元素是否都为 TRUE,如果是返回 True,否则返回 False。其中元素除了是 0、空、None、False 外都算作 True。在 Problem B 中,有一处要判断列表是否是升序排列的,要检查每个元素是否符合要求——只有每个元素全部都符合要求才行,这正是all()的思想,因此:

    assert all(x<y for x, y in zip(egg_weights, egg_weights[1:]))
  • 只有一个元素的元组。创建单元素元组时,必须在元素后跟一个逗号,否则不会构成元组,而是变成一个普通的值。而对于列表,无论加不加逗号都是一个列表,具体演示如下:

    >>> type(  (123)  )
    <class 'int'>
    >>> type(  (123,)  )
    <class 'tuple'>
    >>> type(  [123]  )
    <class 'list'>
    >>> type(  [123,]  )
    <class 'list'>
  • 使用断言。使用断言,在发现参数不合法的时候及时终止程序,避免造成意外的结果。断言的语法非常简单:

    assert expression

    等价于:

    if not expression:
        raise AssertionError

在 Problem B 的dp_make_weight函数中,我使用了两个断言,确保 1 在egg_weights中、确保egg_weights是升序排列的。

  • 贪心算法不一定给出最优解。贪心法因为只是每一步取区部最优,得到的不一定是全局最优解。但是,贪心算法往往易于设计,因此通常情况下人们还是很喜欢使用贪心算法的。
  • Python 中的计时函数。首先说明,Python 3.3 起,time.clock()函数被废弃了,取而代之的是time.perf_counter(性能计数器)和time.process_time(进程时间)。我使用的是time.perf_counter,它包括在睡眠期间和系统范围内流逝的时间,且具有最高可用分辨率,适合对那些很快的过程计时。

完整代码

本地下载:mit_6.0002_ps1.zip


Comments

添加新评论

已有 1 条评论

这个dp的方法很好,学到了