随笔 - 32  文章 - 94  trackbacks - 0
<2011年3月>
日一二三四五六
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(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连看的算法当时用一天写出来，非常兴奋。无奈电脑是内网，要保密，不能把代码直接传出来，之前想过有时间要贴出来，一直忘记了。现在在转到这个新开的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) 阅读(1590) 评论(2)  编辑 收藏 引用 所属分类: 算法

FeedBack:
# re: 以前写的一个N连看 2009-06-29 23:15 小卒
我最近想写个立体数独，不过理论功底不行……  回复  更多评论
  
# re: 以前写的一个N连看 2009-06-30 09:34 CY
那还要先证明立体数独需要用多少个候选数  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Copyright ©2024 陈昱(CY) Powered by: 博客园 模板提供：沪江博客