小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

和猫妹学Python，一起趣味学编程。

今日主题

什么是动物园搬家问题？

如何用Python的队列来解决类似问题？

动物园搬家问题

某动物园搬家，要运走N种动物，老虎与狮子放进一个笼子打架，大象与犀牛放一个笼子打架，野猪与猎狗放在一个笼子里打架…

请你设计一个算法，使得装进同一个笼子的动物互相不打架。

A={0,1,2,3,4,5,6,7,8}#代表N种动物的集合，

R={(1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4)}#冲突关系集合

这类问题被称为划分无冲突子集问题。

算法思路

1.把所有动物按次序入队，比如index从小到大。这里用到了队列。

2.创建一个笼子(集合)，出队一个动物，如果和笼子里的动物无冲突则添加到该笼子，有冲突则添加到队列尾部，等待进入新的笼子。

3.由于队列先进先出的特性，如果当前出队动物的index，不大于其前一个出队动物的index，说明当前队列中所有动物已经尝试进入且进入不了当前笼子，也就是说此时需要创建新的笼子(集合)。

Python实现

代码实现（代码见同名公众号，次条推文）：

代码逻辑：

20行：N种动物集合

21行：冲突关系集合

23~26行：将冲突关系集合转换为冲突关系矩阵

3~18行：划分无冲突子集函数，M表示冲突矩阵，N表示动物集合

4行：划分无冲突子集，它是一个列表，表示笼子。列表中的元素也是列表，表示动物。

5行：创建一个队列，有序，比如012345678表示9种动物。

处理时，从队列头取动物索引，取出的动物有两个选择，和当前笼子中动物不冲突则放入笼子，否则放到队列尾部。

一开始，队列是有序的，从小到大。

当上一个元素大于当前元素时，表示当前元素已经从队首放置到队尾，此时需要添加新的笼子。

6行：上一个元素要足够大，表示一开始就要创建新笼子。

7行：只有队列非空，就要继续计算，如何放置剩余动物到笼子。

8行：从队列中弹出一个元素，表示当前元素。

9~10行：如何当前元素比上一个元素还小，表示当前元素之前已经从队首移动到队尾过。此时需要创建新的笼子，在列表中添加一个新的元素，该元素是一个空的列表。

11~16行：判断当前元素和当前笼子中的元素是否有冲突。如果有冲突，将该元素添加到队列尾部。如果没有冲突，将它添加到笼子中，也就是列表中。

17行：处理了一个元素，更新下当前元素。

怎么样？

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！返回搜狐，查看更多

责任编辑：