Project - Degree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.

    If no possible path, returns None.
    """

    # TODO
    frontier = QueueFrontier()
    frontier.add(Node(state=source,parent=None,action=None))
    explored = set()
    while not frontier.empty():
        node = frontier.remove()
        if node.state == target:
            path = []
            while node.parent is not None:
                path.append((node.action,node.state))
                node = node.parent
            path.reverse()
            return path
        explored.add(node.state)
        for movie,person in neighbors_for_person(node.state):
            if(person not in explored and not frontier.contains_state(person)):
                next = Node(state = person,parent=node,action = movie)
                frontier.add(next)
    return None

这里需要我们完成最短路径这个函数，是要找出从 source 到 target 建立起关系的最短路径

这里是通过出演同一部电影来建立联系

首先，可以调用 utils 里写好的 queuefronti，这里之所以选择 queue，是因为要找最短，所以我们选择 BFS，广度优先

然后，不同于课上的 maze 迷宫问题，我们不用新定义一个 class

这里先是添加初始节点，然后定义 explored，用于标记检测过的 node

然后定义返回条件，判断是否是 target，使用课上的方法回溯，并将 path 翻转（注意 path 中元素的格式）

然后添加遍历的逻辑，借助 neighbors 函数，获取同一电影的其他人，查找是否检测过，如果没有，那就添加到frontier 之中

这里的 frontier 是需要下一步遍历的节点，explored 是遍历过的节点