問題4 拼塊游戲

問題導(dǎo)入

在平面上矩形框內(nèi)有m x n個小方塊，按照m行n列排放。每個方塊面上被兩條對角線分為4個三角形區(qū)域。每個三角形可以從4中顏色中任選一種著色。如果相鄰方塊鄰接邊兩側(cè)的三角形區(qū)域顏色相同則記1分。給定一種排列，玩家每一步可任選兩個方塊相互交換位置（稱為置換），但不能旋轉(zhuǎn)。玩家需通過置換操作爭取盡可能的高分，置換次數(shù)并無限制。

?

顯然，內(nèi)部邊界線段數(shù)是可能的最高分。

?

因為置換次數(shù)無限制，那么似乎可以用窮舉發(fā)，窮舉m x n個小方塊可能的排列，計算每種排列的分值。但是這個排列數(shù)是(m x n)!。顯然，想用窮舉的方法確認最優(yōu)解（最高分）顯然不容易。

?

人工智能的啟發(fā)式算法在這里派上了用場。

?

“人工智能”“智能”算法，這個名詞聽起來非常高大上。

?

其實在目前計算機領(lǐng)域內(nèi)，應(yīng)用層面上的“智能”背后的算法支撐，簡單說就是“碰運氣”。

?

作者在本章中，針對這個問題，給出了兩個啟發(fā)式算法，一個是基于貪婪思想，追求局部優(yōu)化的方法；另一個是更加“智能”的啟發(fā)式算法—模擬退火算法。（這類受生命現(xiàn)象或物理過程啟發(fā)而設(shè)計的算法，往往不能嚴格證明在允許的輸入條件下算法結(jié)果的正確性，但通過大量實驗，經(jīng)驗數(shù)據(jù)支撐了算法的可用性和有效性。）【通俗說，就是啟發(fā)式算法不能證明算法能得到最優(yōu)解，但是通過實際大量的運行，得到解就是最優(yōu)解或者很接近最優(yōu)解】

?

作者在本章，就拼塊游戲，也給出了兩個算法的運行結(jié)果。想感受，現(xiàn)在計算機領(lǐng)域的“智能”算法在解這個問題時，能做到什么程度?？磿?。

?

【作者感受】

我自己在學(xué)習(xí) 啟發(fā)式算法時，也覺得不可思議（初學(xué)時），也覺得不可理喻（學(xué)了一會后，因為水平不夠）。

后來，自己讀博士時，求解一個問題，需要用到啟發(fā)式算法，實驗室的一些同門求解其他問題時，有時也要用啟發(fā)式算法（模擬退火、遺傳算法。。。），確實能求得一些更好的結(jié)果出來。其實還是不理解，因為研究方向不同，以后對人工智能也沒有什么涉獵了。

“智能”算法“智能”嗎？有興趣的讀者自己去探索和體會吧。