• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        




            
	
		


            隨筆 - 32 
文章 - 94 
trackbacks - 0


             
	

            

            
	
		
            
			
            
	
            
		
            <2009年6月>
            
	
            日一二三四五六
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011
            

            

            
			
			

            常用鏈接
            


            留言簿(8)
            




		
            隨筆分類
            
		
				
			
	
		
            隨筆檔案
            
		
				
			
	
		
            好友連接
            
		
				
			
	




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


            		
	

            

            
	
					


            
	
	這一周，我寫好了一個連連看，在設計連連看的算法的過程中，我設計了一個可以控制連數的連連看算法，并把連連看改成了“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連看的算法當時用一天寫出來，非常興奮。無奈電腦是內網，要保密，不能把代碼直接傳出來，之前想過有時間要貼出來，一直忘記了。現在在轉到這個新開的blog。
            只貼算法有關部分。用的是python語言：
            

              1class 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) 閱讀(1605) 評論(2)  編輯 收藏 引用  所屬分類: 算法 
            

            







            
	    
    


            
FeedBack:

            
	

		
            
			
            
			
            # re: 以前寫的一個N連看 2009-06-29 23:15 小卒
            
				
            我最近想寫個立體數獨，不過理論功底不行……  回復  更多評論
              
			
            
		
            
	
		
            
			
            
			
            # re: 以前寫的一個N連看 2009-06-30 09:34 CY
            
				
            那還要先證明立體數獨需要用多少個候選數  回復  更多評論
              
			
            
		
            
	




            






            

				
	



            


    
    







	   
	



亚洲国产视频久久|
久久国产V一级毛多内射|
色悠久久久久久久综合网|
久久精品亚洲男人的天堂|
久久人妻少妇嫩草AV无码蜜桃|
久久精品aⅴ无码中文字字幕不卡|
91秦先生久久久久久久|
久久久久久噜噜精品免费直播|
国产一区二区三区久久精品|
国产成人久久精品区一区二区|
久久久久18|
日韩精品无码久久久久久|
色综合久久中文色婷婷|
日产精品久久久久久久|
久久成人国产精品二三区|
亚洲国产精品综合久久网络|
99久久99久久精品免费看蜜桃|
国产精品一区二区久久精品|
四虎国产精品成人免费久久|
国产精品免费福利久久|
久久人人爽人人爽人人片AV麻烦|
久久无码av三级|
精品熟女少妇AV免费久久|
久久综合九色综合精品|
久久久久久人妻无码|
少妇熟女久久综合网色欲|
欧美日韩精品久久久免费观看|
97久久精品人人澡人人爽|
少妇内射兰兰久久|
久久国产色av免费看|
亚洲Av无码国产情品久久|
精品国产乱码久久久久久浪潮|
精品久久久久久国产|
欧美熟妇另类久久久久久不卡|
色偷偷88欧美精品久久久|
国产免费久久久久久无码|
国产V综合V亚洲欧美久久|
久久精品视频网|
91精品无码久久久久久五月天|
久久99国产精品久久|
国产美女亚洲精品久久久综合|