C大調如歌的行板
我也來發明山楂車輪

隨筆 - 32 文章 - 94 trackbacks - 0

2013年1月

>

日

一

二

三

四

五

六

30

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

31

1

2

3

4

5

6

7

8

9

常用鏈接

留言簿(8)

隨筆分類

隨筆檔案

好友連接

搜索

閱讀排行榜

評論排行榜

以前寫的一個N連看

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

基本的算法是這樣的：
先寫一個函數f1，判斷點1和點2能否經過某個方向直線到達，方向有上、下、左、右四種

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

我的算法優化方法很簡單，就是在原來基礎上加上一個對應于所有點的數組，用來記錄對應的點在第多少連的情況下仍然沒有找到目標點。例如：假設總共只能n連，當前點已經被記錄到經過x連仍然找不到目標點，這時，如果繼續遞歸到第n-x+1連又來到該點，這時只剩下x-1連可以遞歸，而當前點已經記錄過x連都無法到達，所以接下來的遞歸可以忽略。
這樣，大大減少了無效的計算，原來在第6連最壞情況下算了40多秒得到無解，現在可以在20連最壞情況下計算2秒得到無解。

那個n連看的算法當時用一天寫出來，非常興奮。無奈電腦是內網，要保密，不能把代碼直接傳出來，之前想過有時間要貼出來，一直忘記了?，F在在轉到這個新開的blog。
只貼算法有關部分。用的是python語言：

1

class CY_LianlianKan(

..):
2

def __init__(self):
3

self.m_Array=[] #存儲內容的矩陣
4

self.m_LinkCount=0 #需要連的總數
5

self.m_FirstPosition=-1 #記下連的第一點
6

self.MaxWidth=13 #矩陣寬
7

self.MaxHeight=12 #矩陣高
8

#其它初始化內容
9

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

def IsTargetXYValid(self,X,Y):
11

#目標坐標是否有效,超過矩陣寬高即無效
12

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

def IsTargetXYBlank(self,X,Y):
14

#目標是否空白可以通過
15

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

def GetArrayXY(self,X,Y):
17

#獲取矩陣坐標為XY的內容
18

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

def IsLineable(self,x1,y1,x2,y2,direction):#判斷兩點是否可以通過某方向直線連接
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成功時用于記錄路徑 n當前剩下的連數 LRorUD當前方向是上下還是左右
49

#hasReachPoint 一個矩陣，用于記錄矩陣中各個點目前已經經過多少連了還找不到目標點
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:#到達不了，上下轉彎，遞歸
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:#到達不了，上下轉彎，遞歸
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:#上下移動
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:#到達不了，左右轉彎，遞歸
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:#到達不了，左右轉彎，遞歸
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連看的計算函數
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

當然，現在想到還有可以繼續優化的地方，例如尋路時，從起點和目標點同時出發尋路，而不是只從一個點出發尋路。這樣做或許還可以雙線程優化，不過具體做法就沒有細想了。

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

FeedBack:

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

我最近想寫個立體數獨，不過理論功底不行…… 回復更多評論

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

那還要先證明立體數獨需要用多少個候選數回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: 某人水題一道 shader的小奏鳴曲一個想法，實習n維立方體?。?！（結束）一個想法，實現n維超級立方體！?。〕醪匠晒Γ。。。ǖ诙拢?/a> 一個想法，用程序畫出高維超立方體在三維上的投影?。。。?）以前寫的一個N連看

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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