Queue-and-Stack2

2020-09-15

前言

上一篇文章提到了哈佛大学的一个网课，其中有一个关于搜索算法的练习题还是值得我们思考一下的。

Six degrees of separation(六度分离)

这个问题的名字听起来很高端，但其实也不难理解。其中心思想大概就是我们与任何一个陌生人之间所间隔的人不会超过五个。换句话说，我们想认识任何一个人，最多只需要通过五个人的接触。每个人与人之间的联系我们可以假设为一度，这样一来我们可以通过对度的计算来实现搜索的目的。

问题来了？

给出三个.csv文档(movies,people,stars),通过列表之间的相同信息，找出初始明星(source)与目标明星(target)通过参演过的电影的最短关联程度。例如，A与B共同参演过一部电影，其分离度则为1，反之每增加一个中间人，其分离度需增加一度。
csv文件格式如下
movies.csv
| id | title | year |
|:—–|:—–|:—–|
| ** |** | ** |
**people.csv
| id | name | birth |
|:—–|:—–|:—–|
| ** |** | ** |
**stars.csv
| person_id | movie_id|
|:—–|:—–|
| ** |**|

Code

要处理csv数据，肯定需要先处理和加载到程序里，在这个项目中，出题者直接把大部分代码展示了出来，而我们所需要完成的是找出路径或者说是找出度的部分。项目文件链接如下degrees.zip

Data

虽然处理数据的代码已经写好了，但我们还得知道数据在被加载后的数据结构是什么样的？

首先在加载数据之前，程序先定义了三个集(names,people,movies)
数据在经过程序处理后，数据结构如下：

names
{‘kevin bacon’:{‘102’},省略…}
people
{‘102’:{‘name’:’Kevin Bacon’,’birth’:’1958’,’movies’:{‘104257’,’112384’}},省略…}
movies
{‘112384’:{‘title’:’Apollo 13’,’year’:’1995’,’stars’:{‘102’,’158’,’200’,’641’}},省略…}

Stack/Queue

如何构造节点？

class Node():
    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action

我们在搜算算法中所要寻找的目标值是储存在节点上的，但是节点只能储存数据不能搜算。如果我们想要实现搜算，需要引入Frontier去管理节点 Ref

1.从包含初始状态的边界(frontier)开始
2.从一个空的探索集开始
3.重复：
如果边界为空，则无解。
从边界删除节点。
如果节点包含目标状态，请返回解。
将节点添加到探索集中。
拓展节点，如果结果节点不在边界或探索集中，则将它们添加到边界

如何实现栈和队列？

这一部分没什么好说的，主要还是栈和队列的数据结构，上一篇已经提过了

class StackFrontier():
    def __init__(self):
        self.frontier = []

    def add(self, node):
        self.frontier.append(node)

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):
        return len(self.frontier) == 0

    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[-1]
            self.frontier = self.frontier[:-1]
            return node
class QueueFrontier(StackFrontier):
    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[0]
            self.frontier = self.frontier[1:]
            return node

搜算算法实现

我们问题是如何搜索出最短的路径在起始人物和目标人物之间。既然我们的任务是找到最优解法，那么必然是选择BFS

#存储最短路径
res = []
#BFS队列实现
queue=QueueFrontier()
#创建起始节点
start=Node(source, None, None)
#将节点加入队列
queue.add(start)
#创建已探索集
Explored_set=set()

while True:
    #检查是否为空
    if queue.empty():
        return None
    node = queue.remove()
    state = node.state
    print(state)
    Explored_set.add(state)
    #搜算目前节点人物参演过的电影
    for movie in people[state]['movies']:
    #搜索该电影出演的人员
        for person in movies[movie]['stars']:
    #判断人员是否搜索过
            if person not in Explored_set:
    #判断人员是否为目标
                if person == target:
    #成功，储存路径并返回
                    res.append((movie, person))
                    while node.parent is not None:
                        res.append((node.action, node.state))
                        node = node.parent
                    res.reverse()
                    return res
                else:
                    child=Node(person,node,movie)
                    queue.add(child)
raise NotImplementedError

Source code原地址

最后

上面展示的并不是完整的代码，只是把搜算这一部分拿出来总结。因为自己当时看到这个题目的时候不知道从何入手，所以值得把别人写好的代码再反复研究。
Updated on 10/16/2020