MIT 6.0002 PS2: Fastest Way to Get Around MIT

本文是我对 MIT 6.0002 课程（Introduction to Computational Thinking and Data Science）配套作业 Problem Set 2 的解答。这次作业实现了一些和有向图相关的数据结构，并编写了使用 DFS 的最短路径递归算法。

问题描述

详细的要求见原题，从 MIT OCW 下载原题：Problem Set 2: Fastest Way to Get Around MIT (ZIP) (This ZIP file contains: 1 .pdf file, 1 .txt file, and 2 .py files)

Problem 1: Creating the Data Structure Representation

WeightedEdge 类

在充分理解Node类和Edge类后，首先编写WeightedEdge类，它是Edge的子类，在其基础上增加了边的权重信息total_distance和outdoor_distance。该类在父类的基础上另新定义了两个 getter 成员函数，此外它重写了父类的__str__成员函数，用于输出包含权重的字符串信息。虽然题目没有直接说明权重的类型是否为整数，但是由于题目本身以及提供的数据都为整数，我默认total_distance和outdoor_distance都是 int 类型。

在__str__的实现中使用了父类Edge的同名方法，输出起点和终点的名称；此外，还要多输出边的权重信息。以上这些都通过格式化字符串来实现，即'{} ({}, {})'.format(Edge.__str__(self), self.get_total_distance(), self.get_outdoor_distance()。

class WeightedEdge(Edge):
    def __init__(self, src, dest, total_distance, outdoor_distance):
        Edge.__init__(self, src, dest)
        self.total_distance = total_distance
        self.outdoor_distance = outdoor_distance

    def get_total_distance(self):
        return self.total_distance

    def get_outdoor_distance(self):
        return self.outdoor_distance

    def __str__(self):
        return '{} ({}, {})'.format(Edge.__str__(self), self.get_total_distance(), self.get_outdoor_distance())

Digraph 类

然后看Digraph类。add_node方法向有向图中加入一个新的节点，如果节点已存在，则抛出 ValueError。其中，判断节点是否已经存在可以用has_node方法。特别注意Digraph储存节点的方式——self.nodes是一个集合（set），向集合中添加元素的方法是add。另外，添加节点后还要初始化self.edges字典中该节点的列表为空列表，这样做是为了方便add_edge向图中添加边。

def add_node(self, node):
    if self.has_node(node):
        raise ValueError('The node is already in the graph')
    else:
        self.nodes.add(node)
        self.edges[node] = []  # 为新节点创建边的空列表

添加边add_edge，该方法要求参数edge的起点和终点都是已经在图中的，否则抛出 ValueError；在我的实现中，缺少源点和缺少终点将抛出不同的异常。特别注意Digraph储存边的方式——self.edges是一个字典，键为节点 Node，值为该节点对应的边的列表。因此，添加边时要先用edge的起点找到字典中对应的边的列表，然后将这条新边插入列表。

def add_edge(self, edge):
    if not self.has_node(edge.get_source()):
        raise ValueError('Source node is not int the graph')
    elif not self.has_node(edge.get_destination()):
        raise ValueError('Destination node is not in tht graph')
    else:
        self.edges[edge.get_source()].append(edge)

单元测试

运行graph.py，单元测试通过：

......
----------------------------------------------------------------------
Ran 6 tests in 0.001s

OK

Problem 2: Building up the Campus Map

Problem 2a: Designing your graph

①What do the graph's nodes represent in this problem? ②What do the graph's edges represent? ③Where are the distances represented?

①图中的节点表示学校里面的各个地点（楼房，building），用编号或名称表示。②节点之间的边代表从起点到终点的有向路径。③每条路径有两个属性，分别是总距离和室外距离。所有节点和有向边的集合构成一张有向图。

Problem 2b: Implementing load_map

打开文件的最好方法是使用with，然后使用 for 循环按行读取文件。对于每一行，首先使用split()方法将其拆分为四个元素。注意，使用split()时可以不提供任何参数，这时默认的分隔符为所有空白字符，包括空格和换行符，因此，使用不带参数的split()，不但可以以空格分割字符串，还可以自动去掉末尾的换行符。得到元素后，检查起点和终点是否在图中，如果不在则加入节点，最后，把这条边加入到有向图中。

def load_map(map_filename):
    print("Loading map from file...")
    graph = Digraph()  # 创建空图
    with open(map_filename) as file:
        for line in file:
            elements = line.split()  # 按空格分割成list
            src = Node(elements[0])
            dest = Node(elements[1])
            total_distance = int(elements[2])    # 数字类型
            outdoor_distance = int(elements[3])  # 数字类型

            if not graph.has_node(src):
                graph.add_node(src)
            if not graph.has_node(dest):
                graph.add_node(dest)
            graph.add_edge(WeightedEdge(src, dest, total_distance, outdoor_distance))

    return graph

写这个函数时需要格外注意各个参数的类型，重点需要区分节点是 Node 类型的还是字符串类型的，还要区分边的total_distance和outdoor_distance是字符串类型的还是整数类型的，等等。

Problem 2c: Testing load_map

test_load_map.txt的文件内容：

a b 10 9
a c 12 2
b c 1 1

在测试load_map函数时，可以先把__main__注释掉，暂时不进行单元测试，避免产生大量输出干扰我们。

print('*** Problem 2c BEGIN ***')
test_graph = load_map('test_load_map.txt')
print(test_graph)
print('*** Problem 2c END ***')

根据官方文档，print函数会自动将其参数转换为字符串类型，也就是自动调用参数的__str__方法，无需我们显式地写成print(str(test_graph))。

测试结果如下，和题目中的样例输出相同：

*** Problem 2c BEGIN ***
Loading map from file...
a->b (10, 9)
a->c (12, 2)
b->c (1, 1)
*** Problem 2c END ***

测试完毕后，将以上代码注释掉，然后恢复__main__，为后面进行单元测试做好准备。

Problem 3a: Objective function

What is the objective function for this problem? What are the constraints?

目标函数：要找到从起点到终点的最短路径（total_distance之和最小）；

约束条件：室外路径总长度不超过给定限制（outdoor_distance之和不超过限制）。

Problem 3b: Implement get_best_path

题目中的get_best_path函数的参数和内部变量有许多和 path 有关的数据类型，比较混乱且不够规范，为了遵循题目的要求，需要在编写代码之前特别理清这些数据之间的关系。再者，该函数中关于节点的表示，有时是字符串，有时是 Node 类对象，这也是需要特别小心的。该函数用到递归，其共有 7 个参数，其中digraph、end、max_dist_outdoors在递归过程中时不会改变的，start、path、best_dist和best_path是会变的。

方便起见，我用start和end表示字符串形式的节点（这也是该函数 doc string 中的要求），用start_node和end_node表示 Node 类型的节点，在函数起始处就完成这样的转换，然后检查转换后的 Node 对象是否在图中，如果不在，立即抛出异常。

start_node = Node(start)  # 转换为Node对象
end_node = Node(end)      # 转换为Node对象
if not digraph.has_node(start_node) or not digraph.has_node(end_node):
    raise ValueError('Node not exist')

如果在递归时发现start == end，这说明递归结束了，也就是当前路径的访问已到达终点，直接返回元组即可。

elif start == end:        # 递归到end时，直接返回当前路径及其总长度
    return path[0], path[1]

上面两种情况分别是错误情况、递归停止条件。下面讨论递归的一般步骤。

path中保存着当前正在访问的路径以及这条路径的总长度和室外长度，起初，path中只有起点，且长度为 0，每次递归可能会向其中加入一个新的节点，同时更新长度。每次递归的过程实际上是尝试将当前起点的所有邻接点分别加入路径，从而产生一条新路径，然后检查这个新路径是否满足长度限制，如果满足长度限制，并且新路径的总长度比当前的best_dist还小，那么继续进行递归；否则，没有必要继续递归（一是因为不符合限制的路径是无效的，继续递归也不可能得出正确结果；二是因为如果长度不小于当前的best_dist，那么即使继续递归也不可能比这个最短距离更短），这就是“剪枝”。这里由于变量命名复杂且函数名较长，我为了代码可读性而牺牲了一些简洁性，从而创建了许多变量。

else:
    for edge in digraph.edges[start_node]:
        # 加入下一个节点（当前起点的邻接点），构造出一个新路径，作为path参数进行递归
        next_node = edge.get_destination().get_name()
        next_path_nodes = path[0] + [next_node]    # 新路径经过的节点列表
        next_path_total_dist = path[1] + edge.get_total_distance()         # 新路径的总长度
        next_path_outdoor_dist = path[2] + edge.get_outdoor_distance()     # 新路径的室外长度
        next_path = [next_path_nodes, next_path_total_dist, next_path_outdoor_dist]  # 新的path参数

下面重点考虑满足限制且总长度更小的情况。这时就可以利用刚刚构造出的那条新路径递归地调用get_best_path，递归时应从下一节点（也就是上面说的“当前起点的所有邻接点”之一）开始，所以next_node变量作为新的start参数，next_path作为新的path参数，其余参数不变。通过递归，我们获得了一条新的最短new_best_path，下面我们要看看这条新的最短路径是不是比当前的best_dist更短，如果是，则更新。

if (next_node not in path[0]) and (next_path[2] <= max_dist_outdoors) and (next_path[1] < best_dist):
    # 递归
    new_best_path = get_best_path(digraph, next_node, end, next_path, max_dist_outdoors, best_dist, best_path)
    # 更新
    if new_best_path is not None and new_best_path[1] < best_dist:
        best_dist = new_best_path[1]  # 新的最短路径的长度
        best_path = new_best_path[0]  # 新的最短路径的节点列表

对于起点的每个邻接点，都要经过上面的递归。在检查完所有的邻接点后，根据情况返回不同的值。具体要求见此函数的 doc string。

if best_path: # 列表非空，返回元组
    return best_path, best_dist
else:         # 列表为空，返回None
    return None

注意，以上文档难以看出代码之间的缩进关系，请参照ps2.py源文件。

Problem 3c: Implement directed_dfs

前面的get_best_path负责递归，这里的directed_dfs则是get_best_path的主调函数。值得注意的是，该函数仅返回路径本身，即由路径上的节点（以字符串表示）构成的列表。

用提供的参数去调用get_best_path函数，将返回值存放在result临时变量中。如果满足限制条件的路径不存在，那么get_best_path将返回 None，这时我们需要抛出一个异常；如果返回值不是 None，但是返回的best_dist大于max_total_dist，这表示路径不满足限制条件，同样应该舍弃，抛出异常；其余情况为正确路径，只需返回get_best_path返回的元组的第二项，也就是best_path。

def directed_dfs(digraph, start, end, max_total_dist, max_dist_outdoors):
    result = get_best_path(digraph, start, end, [[start], 0, 0], max_dist_outdoors, float('inf'), [])
    if result is None:
        raise ValueError('get_best_path returned None')
    best_path, best_dist = result
    if best_dist > max_total_dist:
        raise ValueError('No path can satisfies the constraints')
    else:
        return best_path

测试

Ps2Test的结果如下：

Loading map from file...
------------------------
Shortest path from Building 8 to 50 without walking more than 0m outdoors
.Loading map from file...
------------------------
Shortest path from Building 10 to 32 without walking more than 100m total
.Loading map from file...
.Loading map from file...
------------------------
Shortest path from Building 2 to 9
Expected:  ['2', '3', '7', '9']
DFS:  ['2', '3', '7', '9']
.Loading map from file...
------------------------
Shortest path from Building 1 to 32
Expected:  ['1', '4', '12', '32']
DFS:  ['1', '4', '12', '32']
.Loading map from file...
------------------------
Shortest path from Building 2 to 9 without walking more than 0m outdoors
Expected:  ['2', '4', '10', '13', '9']
DFS:  ['2', '4', '10', '13', '9']
.Loading map from file...
------------------------
Shortest path from Building 1 to 32 without walking more than 0m outdoors
Expected:  ['1', '3', '10', '4', '12', '24', '34', '36', '32']
DFS:  ['1', '3', '10', '4', '12', '24', '34', '36', '32']
.Loading map from file...
------------------------
Shortest path from Building 32 to 56 without walking more than 0m outdoors
Expected:  ['32', '36', '26', '16', '56']
DFS:  ['32', '36', '26', '16', '56']
.Loading map from file...
------------------------
Shortest path from Building 32 to 56
Expected:  ['32', '56']
DFS:  ['32', '56']
.
----------------------------------------------------------------------
Ran 9 tests in 0.052s

OK

总结

  • 用集合储存图的节点。在Digraph类中储存节点的数据类型是集合（set），这样做是基于集合的特点——没有重复的元素，显然一个图中是不存在两个相同的节点的。向集合中添加元素的方法是add而不是append。
  • print函数会将其参数自动转换为字符串。以下内容截自官方文档：All non-keyword arguments are converted to strings like str() does and written to the stream, separated by sep and followed by end. 也就是print会在传入的非关键字参数上自动调用str()方法。再来看官方文档中的这一段，这里说str(object) returns object.__str__()。所以，如果我们打印一个对象，实际上是打印出了该对象的__str__()方法返回的字符串。
  • 用with进行文件读取。官方文档对with的解释是“with语句用于包装带有使用上下文管理器定义的方法的代码块的执行。 这允许对普通的 try...except...finally 使用模式进行封装以方便地重用。”大致意思就是使用with封装了常用操作，是我们的代码更便捷。在读取文件这个操作上，使用with打开文件，一不需要显式地处理打开失败的异常，二不需要显式地关闭文件，使用更加方便。
  • 使用pysnooper来跟踪代码。PySnooper是一个开源的调试工具，使用它可以轻松地跟踪代码的执行过程。使用它时，只需要在要跟踪的函数前面加上装饰器@pysnooper.snoop()即可。该工具比较轻量，无需使用 IDE 即可实现与 IDE 相似的功能（我的环境是 Anaconda + VS Code）。本题中我使用这个工具来跟踪get_best_path函数。
  • Python 动态类型和返回元组的特性。在编写get_best_path函数的过程中，我体会到了 Python 和 C/C++ 的不同之处。Python 动态类型决定了我们不需要为一个变量确定类型，也不需要确定函数返回值的类型。比如get_best_path有时返回元组，有时返回 None。Python 函数可以返回多个值，实际上是返回一个元组，不过在return后不需要加括号。在调用这样的函数时，可以直接将返回多个值的函数赋值给多个值，一定程度上提高了可读性，使编程更加简单。不过，对于熟悉 C/C++ 等语言的开发者来说，在编写 Python 函数时不能一贯沿用 C/C++ 的函数编写思想。否则，仅仅用 Python 语法实现 C/C++ 同样的逻辑是没有什么意义的。
  • None。判断一个对象是否为 None 可以用is。按照 Google 代码风格，应使用obj is not None而不是not obj is None。显然前者可读性更好。
  • 本题的重点是get_best_path函数的实现，这个函数中有path、best_path、next_path等和路径有关的变量，它们的数据类型各不相同，要格外注意。该算法采用深度优先搜索，其中按条件判断使用剪枝以减小搜索树的规模。

完整代码

本地下载：mit_6.0002_ps2.zip


Comments

添加新评论

已有 1 条评论

szzhiyang szzhiyang

代码、分析和总结都很清晰和详细，支持！????

回复