C大調(diào)如歌的行板
我也來發(fā)明山楂車輪

隨筆 - 32 文章 - 94 trackbacks - 0

2009年6月

>

日

一

二

三

四

五

六

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

常用鏈接

留言簿(8)

隨筆分類

隨筆檔案

好友連接

搜索

閱讀排行榜

評(píng)論排行榜

以前寫的一個(gè)N連看

這一周，我寫好了一個(gè)連連看，在設(shè)計(jì)連連看的算法的過程中，我設(shè)計(jì)了一個(gè)可以控制連數(shù)的連連看算法，并把連連看改成了“n連看”，然后經(jīng)過算法優(yōu)化，使我的連連看算法在20連、無解、矩陣是13*11、最壞情況（一個(gè)周圍空曠，一個(gè)被包圍）下，運(yùn)算速度僅2秒左右。而經(jīng)過優(yōu)化之前，到了6連的最壞情況下就已經(jīng)慢得無法接受了。

基本的算法是這樣的：
先寫一個(gè)函數(shù)f1，判斷點(diǎn)1和點(diǎn)2能否經(jīng)過某個(gè)方向直線到達(dá)，方向有上、下、左、右四種

再寫一個(gè)函數(shù)f2用于循環(huán)遞歸調(diào)用f1，思路是：如果起始點(diǎn)通過直線到達(dá)不了目標(biāo)點(diǎn)，就把起始點(diǎn)可以直線到達(dá)的每個(gè)點(diǎn)當(dāng)成下一次調(diào)用的起始點(diǎn)，直到找到目標(biāo)點(diǎn)就立即返回。f2的參數(shù)包括：
n連：用來控制遞歸深度；
2個(gè)點(diǎn)（起始點(diǎn)和目標(biāo)點(diǎn)），用來判斷能夠經(jīng)過n連連接的2個(gè)點(diǎn)；
判斷當(dāng)前是“上下”或“左右”方向：由于某個(gè)點(diǎn)尋找目標(biāo)點(diǎn)時(shí)，我引進(jìn)了行走方向，這樣可以節(jié)省一半的計(jì)算量。例如：如果當(dāng)前方向是“上下”，直線找不到時(shí)，下一步遞歸對(duì)直線上的每個(gè)點(diǎn)的尋找，就只需要“左右”方向，不需要上下；
路徑記錄的列表。
以上是基本思路。

我的算法優(yōu)化方法很簡(jiǎn)單，就是在原來基礎(chǔ)上加上一個(gè)對(duì)應(yīng)于所有點(diǎn)的數(shù)組，用來記錄對(duì)應(yīng)的點(diǎn)在第多少連的情況下仍然沒有找到目標(biāo)點(diǎn)。例如：假設(shè)總共只能n連，當(dāng)前點(diǎn)已經(jīng)被記錄到經(jīng)過x連仍然找不到目標(biāo)點(diǎn)，這時(shí)，如果繼續(xù)遞歸到第n-x+1連又來到該點(diǎn)，這時(shí)只剩下x-1連可以遞歸，而當(dāng)前點(diǎn)已經(jīng)記錄過x連都無法到達(dá)，所以接下來的遞歸可以忽略。
這樣，大大減少了無效的計(jì)算，原來在第6連最壞情況下算了40多秒得到無解，現(xiàn)在可以在20連最壞情況下計(jì)算2秒得到無解。

那個(gè)n連看的算法當(dāng)時(shí)用一天寫出來，非常興奮。無奈電腦是內(nèi)網(wǎng)，要保密，不能把代碼直接傳出來，之前想過有時(shí)間要貼出來，一直忘記了。現(xiàn)在在轉(zhuǎn)到這個(gè)新開的blog。
只貼算法有關(guān)部分。用的是python語言：

1

class CY_LianlianKan(

..):
2

def __init__(self):
3

self.m_Array=[] #存儲(chǔ)內(nèi)容的矩陣
4

self.m_LinkCount=0 #需要連的總數(shù)
5

self.m_FirstPosition=-1 #記下連的第一點(diǎn)
6

self.MaxWidth=13 #矩陣寬
7

self.MaxHeight=12 #矩陣高
8

#其它初始化內(nèi)容
9

#----------------------------------
10

def IsTargetXYValid(self,X,Y):
11

#目標(biāo)坐標(biāo)是否有效,超過矩陣寬高即無效
12

#----------------------------------
13

def IsTargetXYBlank(self,X,Y):
14

#目標(biāo)是否空白可以通過
15

#----------------------------------
16

def GetArrayXY(self,X,Y):
17

#獲取矩陣坐標(biāo)為XY的內(nèi)容
18

#----------------------------------
19

def IsLineable(self,x1,y1,x2,y2,direction):#判斷兩點(diǎn)是否可以通過某方向直線連接
20

#方向direction：1←2→3↑4↓
21

if direction==1:
22

if y1==y2 and x1>x2:
23

for i in xrange(x2,x1+1):
24

if self.GetArrayXY(i,y1)>0:
25

return False
26

return True
27

elif direction==2:
28

if y1==y2 and x1<x2:
29

for i in xrange(x1,x2+1):
30

if self.GetArrayXY(i,y1)>0:
31

return False
32

return True
33

elif direction==3:
34

if x1==x2 and y1<y2:
35

for i in xrange(y1,y2+1):
36

if self.GetArrayXY(x1,i)>0:
37

return False
38

return True
39

elif direction==4:
40

if x1==x2 and y2<y1:
41

for i in xrange(y2,y1+1):
42

if self.GetArrayXY(x1,i)>0:
43

return False
44

return True
45

return False
46

#---------------------------------------
47

def IsNTurnReachable(self,x1,y1,x2,y2,path,n,LRorUD,hasReachPoint):
48

#path成功時(shí)用于記錄路徑 n當(dāng)前剩下的連數(shù) LRorUD當(dāng)前方向是上下還是左右
49

#hasReachPoint 一個(gè)矩陣，用于記錄矩陣中各個(gè)點(diǎn)目前已經(jīng)經(jīng)過多少連了還找不到目標(biāo)點(diǎn)
50

if n<=0:
51

return False
52

if LRorUD: #左右方向
53

for x in xrange(x1-1,-1,-1):#向左
54

if self.GetArrayXY(x,y1)==0 and hasReachPoint[y1*self.MaxWidth+x]<n:
55

if self.IsLineable(x,y1,x2,y2,3) or self.IsLinable(x,y1,x2,y2,4):
56

path+=[x,y1,x2,y2]
57

return path
58

else:#到達(dá)不了，上下轉(zhuǎn)彎，遞歸
59

hasReachPoint[y1*self.MaxWidth+x]+=1
60

p=self.IsNTurnReachable(x,y1,x2,y2,path+[x,y1],n-1,False,hasReachPoint)
61

if p!=False:
62

return p
63

else:
64

break
65

for x in xrange(x1+1,self.MaxWidth):#向右
66

if self.GetArrayXY(x,y1)==0 and hasReachPoint[y1*self.MaxWidth+x]<n:
67

if self.IsLineable(x,y1,x2,y2,3) or self.IsLineable(x,y1,x2,y2,4):
68

path+=[x,y1,x2,y2]
69

return path
70

else:#到達(dá)不了，上下轉(zhuǎn)彎，遞歸
71

hasReachPoint[y1*self.MaxWidth+x]+=1
72

p=self.IsNTurnReachable(x,y1,x2,y2,path+[x,y1],n-1,False,hasReachPoint)
73

if p!=False:
74

return p
75

else:
76

break
77

else:#上下移動(dòng)
78

for y in xrange(y1-1,-1,-1):#向上
79

if self.GetArrayXY(x1,y)==0 and hasReachPoint[y*self.MaxWidth+x1]<n:
80

if self.IsLineable(x1,y,x2,y2,1) or self.IsLineable(x1,y,x2,y2,2):
81

path+=[x1,y,x2,y2]
82

return path
83

else:#到達(dá)不了，左右轉(zhuǎn)彎，遞歸
84

hasReachPoint[y*self.MaxWidth+x1]+=1
85

p=self.IsNTurnReachable(x1,y,x2,y2,path+[x1,y],n-1,True,hasReachPoint)
86

if p!=False:
87

return p
88

else:
89

break
90

for y in xrange(y1+1,self.MaxHeight):#向下
91

if self.GetArrayXY(x1,y)==0 and hasReachPoint[y*self.MaxWidth+x1]<n:
92

if self.IsLineable(x1,y,x2,y2,1) or self.IsLineable(x1,y,x2,y2,2):
93

path+=[x1,y,x2,y2]
94

return path
95

else:#到達(dá)不了，左右轉(zhuǎn)彎，遞歸
96

hasReachPoint[y*self.MaxWidth+x1]+=1
97

p=self.IsNTurnReachable(x1,y,x2,y2,path+[x1,y],n-1,True,hasReachPoint)
98

if p!=False:
99

return p
100

else:
101

break
102

return False
103

#--------------------------------------------------------
104

def IsLinkAble(self,x1,y1,x2,y2,n):#n連看的計(jì)算函數(shù)
105

if n<=0:
106

return False
107

hasReachPoint=[0]*(self.MaxWidth*self.MaxHeight)
108

for i in [0,1,2,3]:
109

if self.isLineable(x1,y1,x2,y2,i):
110

path=[x1,y1,x2,y2]
111

return path
112

path=[x1,y1]
113

p=self.IsNTurnReachalbe(x1,y1,x2,y2,path,n-1,False,hasReachPoint)
114

if p:
115

return p
116

p=self.IsNTurnReachalbe(x1,y1,x2,y2,path,n-1,True,hasReachPoint)
117

if p:
118

return p
119

return False

當(dāng)然，現(xiàn)在想到還有可以繼續(xù)優(yōu)化的地方，例如尋路時(shí)，從起點(diǎn)和目標(biāo)點(diǎn)同時(shí)出發(fā)尋路，而不是只從一個(gè)點(diǎn)出發(fā)尋路。這樣做或許還可以雙線程優(yōu)化，不過具體做法就沒有細(xì)想了。

posted on 2009-06-28 19:50 陳昱(CY) 閱讀(1622) 評(píng)論(2) 編輯收藏引用所屬分類: 算法

FeedBack:

# re: 以前寫的一個(gè)N連看 2009-06-29 23:15 小卒

我最近想寫個(gè)立體數(shù)獨(dú)，不過理論功底不行…… 回復(fù) 更多評(píng)論

# re: 以前寫的一個(gè)N連看 2009-06-30 09:34 CY

那還要先證明立體數(shù)獨(dú)需要用多少個(gè)候選數(shù) 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 某人水題一道 shader的小奏鳴曲一個(gè)想法，實(shí)習(xí)n維立方體！！！（結(jié)束）一個(gè)想法，實(shí)現(xiàn)n維超級(jí)立方體！！！初步成功！！！（第二章）一個(gè)想法，用程序畫出高維超立方體在三維上的投影！！！（1）以前寫的一個(gè)N連看

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品