IQCar的實(shí)現(xiàn)II——解題思路

2019-11-17 03:54:25

字體：大中小

供稿：網(wǎng)友

上文簡(jiǎn)單介紹了IQCar游戲。接下來(lái)將描述用計(jì)算機(jī)如何求出它的解法。

　　學(xué)過數(shù)據(jù)結(jié)構(gòu)的，第一感覺就是用“深度優(yōu)先搜索”或者是“廣度優(yōu)先算法”。就是不停的嘗試每一種可能，直到到達(dá)解。然后將嘗試的過程輸出即可。

　　仔細(xì)觀察上文的圖片，發(fā)現(xiàn)，每一輛車的可能性位置可能性非常少（由于車子只能前后移動(dòng)，故長(zhǎng)度為3的車子只有4種可能，長(zhǎng)度為2的車子有五種可能）。那么，則這些車子排列的可能性就不會(huì)多（原因是，如果車子多，則彼此之間的限制會(huì)很多，因?yàn)閮奢v車不能擠在一個(gè)格子里，如果車子少，雖然限制少但是車子少，必然總數(shù)少）。這樣，一般的題目，把所有的車子排列構(gòu)成一個(gè)集合的話，這個(gè)集合中的元素不會(huì)很多（實(shí)際情況是，一般的題目，這個(gè)集合的元素在1200左右）。

　　想到這，我想到用圖論的方法求解。

　　所有的車子的一個(gè)位置排列，成為圖中的一個(gè)點(diǎn)，兩點(diǎn)之間的連線表示能從一個(gè)排列移動(dòng)一個(gè)位置到另一個(gè)排列。題目中的初始狀態(tài)為圖中的一個(gè)點(diǎn)，達(dá)到解題條件的為另一個(gè)點(diǎn)（這樣的點(diǎn)可能不止一個(gè)），問題就轉(zhuǎn)化為在圖中從一個(gè)點(diǎn)找到到另一個(gè)點(diǎn)的通路。

　　這個(gè)求通路的有一個(gè)非常有名的算法，Dijkstra算法（最短路徑算法）。

　　那么本問題就轉(zhuǎn)化為兩個(gè)步驟

　　1、根據(jù)輸入的初始狀態(tài)，生成一個(gè)集合，所有車子的一個(gè)位置排列為集合中的一個(gè)元素。并且為每一個(gè)元素建立他們之間的關(guān)系（有連線則表示能從一個(gè)排列移動(dòng)一個(gè)位置到另一個(gè)排列，反之則無(wú)連線）。

　　2、用Dijkstra算法求出一條通路，這條通路也是最短通路，也就是最優(yōu)解

　　注：寫完程序后，細(xì)細(xì)想來(lái)，在本題中，由于各連線的長(zhǎng)默認(rèn)都是1，Dijkstra算法其實(shí)就是廣度優(yōu)先算法。

　　后文將具體的描述各個(gè)模塊的實(shí)現(xiàn)。

上一篇：原來(lái)高煥堂也誤用職責(zé)鏈模式

下一篇：為CKEditor開發(fā)插入代碼的插件