飛天

快乐的生活......

 

马踏棋盘问题

    问题描述:
马的遍历问题。在8×8方格的棋盘上,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
    分析:
       1.可以根据深度优先搜索求解.
  
回朔法

      2.优化之后的算法:
      在每个结点对其子结点进行选取时,优先选择‘出口’最小的进行搜索,‘出口’的意思是在这些子结点中它们的可行子结点的个数,也就是‘孙子’结点越少的越优先跳,为什么要这样选取,这是一种局部调整最优的做法,如果优先选择出口多的子结点,那出口少的子结点就会越来越多,很可能出现‘死’结点(顾名思义就是没有出口又没有跳过的结点),这样对下面的搜索纯粹是徒劳,这样会浪费很多无用的时间,反过来如果每次都优先选择出口少的结点跳,那出口少的结点就会越来越少,这样跳成功的机会就更大一些。这种算法称为为贪心算法,也叫贪婪算法或启发示算法,它对整个求解过程的局部做最优调整,它只适用于求较优解或者部分解,而不能求最优解。这样的调整方法叫贪心策略,至于什么问题需要什么样的贪心策略是不确定的,具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高,如果只要求出一个解甚至不用回溯就可以完成,因为在这个算法提出的时候世界上还没有计算机,这种方法完全可以用手工求出解来,其效率可想而知。

//简单排序
void Horse::sort(Node * node,int len)
{
        
for(int i=0;i<len-1;i++)
          
for(int j=i+1;j<len;j++)
          
{
                
if(node[i].value>node[j].value)
                
{
                        Node temp
=node[i];
                        node[i]
=node[j];
                        node[j]
=temp;
                }

          }

}

//计算节点的出口数(估值)
void Horse::ways_out(Node & node)
{
      
int m,n;

      
for(int i=0;i<8;++i)
      
{
          m
=node.x+nx[i];
          n
=node.y+ny[i];
          
if(m<0||n<0||m>=width||n>=height)
             
continue;
          
if(borad[m][n]==0)
                node.value
++;
      }

}


bool Horse::dfs(
int m,int n,int step)
{
      
if(borad[m][n]!=0return false;
      borad[m][n]
=step;
      
if(step==size)         
         
throw 1;
      
int newx,newy;
      Node node[
8];
      
int len=0;
      
for(int i=0;i<8;++i)
      
{
          newx
=m+nx[i];
          newy
=n+ny[i];
          
if(newx<0||newy<0||newx>=width||newy>=height)
             
continue;

          node[len].x
=newx;
          node[len].y
=newy;
          node[len].value
=0;
          ways_out(node[len]);
          len
++;
          
//dfs(newx,newy,step+1);
      }


      sort(node,len);
      
for(int i=0;i<len;++i)
          dfs(node[i].x,node[i].y,step
+1);

      borad[m][n]
=0;
      backcount
++;//回塑次数 
      return false;

}
    下载
    參考文章:
     http://www.programfan.com/blog/article.asp?id=4148

posted on 2008-01-19 13:12 飛天 阅读(3757) 评论(2)  编辑 收藏 引用 所属分类: 算法描述

评论

# re: 马踏棋盘问题 2009-03-29 18:28 网友

怎么不写析构函数啊?  回复  更多评论   

# re: 马踏棋盘问题[未登录] 2013-06-02 11:34 1

1  回复  更多评论   


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


导航

统计

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

Blogs

搜索

最新评论

阅读排行榜

评论排行榜