Python巧解动物园搬家问题,如何划分无冲突子集,被惊艳到了(64)

  • Post author:
  • Post category:python


小朋友们好,大朋友们好!

我是猫妹,一名爱上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行:处理了一个元素,更新下当前元素。

怎么样?

好了,我们今天就学到这里吧!

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

我是猫妹,咱们下次见!



版权声明:本文为parasoft原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。