小朋友們好，大朋友們好！

我是貓妹，一名愛上Python編程的小學(xué)生。

和貓妹學(xué)Python，一起趣味學(xué)編程。

今日主題

什么是動物園搬家問題？

如何用Python的隊列來解決類似問題？

動物園搬家問題

某動物園搬家，要運(yùn)走N種動物，老虎與獅子放進(jìn)一個籠子打架，大象與犀牛放一個籠子打架，野豬與獵狗放在一個籠子里打架…

請你設(shè)計一個算法，使得裝進(jì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)}#沖突關(guān)系集合

這類問題被稱為劃分無沖突子集問題。

算法思路

1.把所有動物按次序入隊，比如index從小到大。這里用到了隊列。

2.創(chuàng)建一個籠子(集合)，出隊一個動物，如果和籠子里的動物無沖突則添加到該籠子，有沖突則添加到隊列尾部，等待進(jìn)入新的籠子。

3.由于隊列先進(jìn)先出的特性，如果當(dāng)前出隊動物的index，不大于其前一個出隊動物的index，說明當(dāng)前隊列中所有動物已經(jīng)嘗試進(jìn)入且進(jìn)入不了當(dāng)前籠子，也就是說此時需要創(chuàng)建新的籠子(集合)。

Python實(shí)現(xiàn)

代碼實(shí)現(xiàn)（代碼見同名公眾號，次條推文）：

代碼邏輯：

20行：N種動物集合

21行：沖突關(guān)系集合

23~26行：將沖突關(guān)系集合轉(zhuǎn)換為沖突關(guān)系矩陣

3~18行：劃分無沖突子集函數(shù)，M表示沖突矩陣，N表示動物集合

4行：劃分無沖突子集，它是一個列表，表示籠子。列表中的元素也是列表，表示動物。

5行：創(chuàng)建一個隊列，有序，比如012345678表示9種動物。

處理時，從隊列頭取動物索引，取出的動物有兩個選擇，和當(dāng)前籠子中動物不沖突則放入籠子，否則放到隊列尾部。

一開始，隊列是有序的，從小到大。

當(dāng)上一個元素大于當(dāng)前元素時，表示當(dāng)前元素已經(jīng)從隊首放置到隊尾，此時需要添加新的籠子。

6行：上一個元素要足夠大，表示一開始就要創(chuàng)建新籠子。

7行：只有隊列非空，就要繼續(xù)計算，如何放置剩余動物到籠子。

8行：從隊列中彈出一個元素，表示當(dāng)前元素。

9~10行：如何當(dāng)前元素比上一個元素還小，表示當(dāng)前元素之前已經(jīng)從隊首移動到隊尾過。此時需要創(chuàng)建新的籠子，在列表中添加一個新的元素，該元素是一個空的列表。

11~16行：判斷當(dāng)前元素和當(dāng)前籠子中的元素是否有沖突。如果有沖突，將該元素添加到隊列尾部。如果沒有沖突，將它添加到籠子中，也就是列表中。

17行：處理了一個元素，更新下當(dāng)前元素。

怎么樣？

好了，我們今天就學(xué)到這里吧！

如果遇到什么問題，咱們多多交流，共同解決。

我是貓妹，咱們下次見！