建模！用python玩轉積木安放問題

最新 08-14

上了佩恩教授的AI人工智慧課，小八對生活中一些看似神奇莫測的技術有了新的認識，比如人臉識別，它就是利用了OpenCV庫的神經網路（NN）來訓練電腦學習人臉模型。但電腦如何學習呢？在NN中，我們可以在神經元中給電腦一些輸入，然後將每個神經元依次匯攏到感測器中。大家有認識演算法的，一定想起了圖與樹。沒錯！在每個神經元到感測器的路徑中，都有一定的權值，叫『Weight』（這可不是體重！）。將每個輸入依次乘以每個權值並求和，存入到感測器中，再由顯示器輸出。

那麼問題來了，小八還是沒有解釋清楚電腦的學習原理。其實很簡單，在你給了輸入之後，讓電腦產生隨機的權值並得到輸出，你再給電腦糾正，告訴他正確答案，電腦就會調整權值。如果你的例子多了，電腦的處理精度就會越高。比如，你輸入一個數，想要讓電腦返回那個數的平方，你就得教他：

輸入1，得到1；

輸入2，得到4；

輸入3，得到9……

慢慢地，電腦的NN就會發現你在讓他求一個數的平方（這不是簡單地使用平方根！）

是不是被嚇到了！那麼還有更恐怖的，小八使用NN讓電腦學會了求階乘，

做找規律的題不在話下。。。

給大家介紹完NN的工作機制，小八開始進入正題（其實剛介紹的知識和後面要講的沒什麼太大關係）。不知大家有沒有玩過「智慧金字塔」，就是在一個有限的棋盤內，放置多種形狀的積木（當然，每一種積木只有一個），使其平鋪在棋盤上，不重疊也不出界。小八已經體會過了題目的燒腦和可怕，所以便靈感乍現地想請python來幫忙。規則簡潔明了，但想要轉化為python能夠理解的思維方式就不容易了。計算機的世界裡，只有一堆比特，在這兒可沒有什麼積木的存在。因此，在邏輯運算之前，如何構建表達方式是一個不可避免的難題。希望大家先思考思考~~~

時間到！小八可以先劇透一下——這個難題已經被我攻克了，而最初的思想就是：建模！

那什麼是建模呢？擴充開來就是『構建模型』，這有點類似軟體架構師所做的事情。實際上，它就是一個思維線圖和基礎，把大量現實中紛繁複雜的數據轉化或移入一個預先設計好的模型框架，並為後來的邏輯在模型中運轉提供了可能。上一課，我們剛學了列表，它可以儲存一系列的值，包括它本身。那麼，我們可不可以將堆砌積木的現實問題，變成列表運算的編程問題呢？

這其實是完全可能的，想像一下：棋盤中所有空著的地方標註為0，不同種類積木的實體部分分別標註為1、2、3……等等，這已經是一個好的開端！

小八廢話少說，先上程序諜照：

（註：由於時間緊迫，小八隻添加了兩種積木和一個較小的棋盤，但要擴展種類，用現有的函數是完全可以做到的）

（請自行忽略最上方的一長段注釋）

接下來的內容就簡單介紹，不再詳細講解了。我們在開頭定義了一個new_board()，它的用處和名字一樣，就是設定一個新的棋盤，簡單來說，就是一旦發生積木安放失敗或錯誤，它會在第一時間清除棋盤推倒重來。

spin()這個函數非常巧妙，它很聰明的模擬了積木方向的改變——比如原來的積木是[[1,2,3],

[4,5,6]] （注意只有兩層）

通過spin之後變為：

[[3,6],

[2,5],

[1,4]]

這似乎是把原來的積木逆時針旋轉了一下！我們運用spin，已經可以創建積木的4種不同方向。

下面是一段冗長的、繁瑣的函數lay_block()，你能猜出它的用處嗎？哈哈，恰如其名，這正是用於模擬安放積木的代碼。為了遍歷積木列表組的每一項，我們使用了兩個for in循環，i是行數，j是列數。為了算出積木在棋盤中的具體位置，我們需要將積木塊里的i，j兩個index分別加上棋盤中的格點位置來得到。

（比如積木的某一格點的位置為（1,0）也就是在第二行的第一個，注意，python調用索引值總是現實的個數減一的，而你想以積木的左上角為頂點，在（0,0）處畫，所以這個格點的真實位置是（1+0，0+0）=（1,0），沒錯，這是對的！）關於棋盤位置的具體數據，小八在開頭已經用sites包括了。

為了判斷積木是否出界，只要調用try except引誘出IndexError就行了，但要判斷是否重合，就不太方便了，簡要概括就是如果積木頂點和棋盤頂點都不為0（也就是你試圖把積木實體部分放在棋盤上已經放有積木的地方），就將skip設為True。

接下來在函數run()主體部分，也就是寫了一連串的循環，來得到兩種積木各自的10個位置、4個方向……對了，積木是可以翻轉的，我們將用reverse()把積木列表組倒序。如果python一旦檢測到skip為True，也就是安放積木出現了問題，就將此方案continue掉，換句話說，就是跳入下一個循環，放棄掉老的進度。不過在這兒有一個巧妙的地方，即如果第一個積木就安放錯誤，那第二個積木根本就不用考慮直接跳過了。

只有當兩個積木都安放成功，skip仍為False時，這才是一個可行的方案，小八用print()將答案列印在idle上。

在程序的最後，感謝__name__ == "__main__"使得只有當程序是非導入的情況下在執行run()。

[4]

[4, 4]

[4, 2, 2]

[4, 2, 2, 2]

[2]

[2, 2]

[2, 2, 4]

[4, 4, 4, 4]

電腦算對了！這的確是只有兩種方案，而電腦都考慮到了！

而且，以這樣模塊化的編程習慣，今後要擴充棋盤或積木或更多功能，將會變得非常方便。