注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

马塔棋盘---数据结构---优化版--剪枝  

2014-12-01 22:03:39|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
马踏棋盘是经典的程序设计问题之一,主要的解决方案有两种:一种是基于深度优先搜索的方法,另一种是基于贪婪算法的方法。第一种基于深度优先搜索的方法是比较常用的算法,深度优先搜索算法也是数据结构中的经典算法之一,主要是采用递归的思想,一级一级的寻找,最后找到合适的解。而基于贪婪的算法则是依据贪婪算法的思想设置一种标准,然后依据标准进行选择,从而得到解,但是他不一定能够得到最优解。
 
关于马踏棋盘的基本过程:国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中,按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次,最终使得"马"走遍棋盘的64个方格。
 
深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. (来自百度)

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。(来自百度)

其中基于深度优先搜索的算法就是依据当前点找到下一个可能的点,然后对这个点进行深度优先搜索,然后依次递归,当出现条件不满足时,退回来,

马塔棋盘--实现

1.基本的定义,以及一些细节的东西

#include "stdafx.h"
#include<vector>
#include<stack>
#include<iostream>
#include <algorithm>
#include<time.h>
using namespace std;

struct Point
{
int x,y;
int direction;
};
bool cmp(const Point x,const Point y)
{
return x.direction>y.direction;
}
const int Rows=8;
const int Clowns=8;
class MaTa
{
public:
MaTa()
{
for(int i=0;i<Rows;i++)
{
for(int j=0;j<Clowns;j++)
{
Chess[i][j]=0;
}
}
}
bool Valid(Point x);
void Sort(Point X_Next);
void exitMata(Point start);
void Print();
int Chess[Rows][Clowns];
stack<Point> mata;

};

2.函数体的实现

1.有效性

bool MaTa::Valid(Point x)
{
int row=x.x;
int clown=x.y;
if(row>=0 && row<Rows && clown>=0 && clown<Clowns && Chess[row][clown]==0)
{
return true;
}
return false;

}

2.sort 可走路径的多少

目前这个点可走的路径的下一个点可走路径的多少排序,我们从,下一个点可走的最少,开始走,这样才能达到剪枝的作用!

void MaTa::Sort(Point X)
{
static const int x_move[] ={-2,-1,1,2,2,1,-1,-2};
static const int y_move[] ={1,2,2,1,-1,-2,-2,-1};
Point X_Next[8],X_Next_Next;
for(int i=0;i<Clowns;i++)
{
X_Next[i].x=X.x+x_move[i];
X_Next[i].y=X.y+y_move[i];
if(!MaTa::Valid(X_Next[i]))
{
X_Next[i].direction=-1;
continue;
}
X_Next[i].direction=0;
for(int j=0;j<Clowns;j++)
{
X_Next_Next.x= X_Next[i].x+x_move[j];
X_Next_Next.y= X_Next[i].y+y_move[j];
if(MaTa::Valid(X_Next_Next))
{
X_Next[i].direction++;
}
}

}
/*for(int i=0;i<8;i++)
{
for(int j=i;j<8;j++)
{
if(X_Next[i].direction<X_Next[j].direction)
{
X_Next_Next=X_Next[i];
X_Next[i]=X_Next[j];
X_Next[j]=X_Next_Next;
}
}
}*/
sort(X_Next,X_Next+Clowns,cmp);//从大到小排列
for(int i=0;i<Clowns;i++)//剪枝从最小的开始走;
{
mata.push(X_Next[i]);
}

}

3,实现我们开始走啦!

void MaTa::exitMata(Point start)
{
int steps=1;
Chess[start.x][start.y]=steps;
Point StackTop;
MaTa::Sort(start);
while(!mata.empty())
{
StackTop=mata.top();
//cout<<"("<<StackTop.x<<","<<StackTop.y<<")"<<endl;
if(StackTop.direction<0)
{
mata.pop();
}
else if(Chess[StackTop.x][StackTop.y]>0)
{
Chess[StackTop.x][StackTop.y]=0;
mata.pop();
--steps;
}
else
{
Chess[StackTop.x][StackTop.y]=++steps;
MaTa::Sort(StackTop);
}
if(Chess[StackTop.x][StackTop.y]==Clowns*Rows)
{
MaTa::Print();
break;
}
}
if(mata.empty())
{
cout<<"can‘t run all of chess ";
}

}

打印出来

void MaTa::Print()
{
cout << "恭喜!成功穿过马踏棋盘" << endl;
for (int i = 0; i < Rows; ++i )
{
for (int j = 0; j < Clowns; ++j)
cout << " "<<Chess[i][j];
cout << endl<<endl;
}
}

mian 函数的实现

int _tmain(int argc, _TCHAR* argv[])
{
clock_t start, finish;
start = clock();
MaTa a;
Point point;
cout<<"Please input the first start position"<<endl;
cout<<"such as x y "<<endl;
cin>>point.x>>point.y;

a.exitMata(point);
finish = clock();
printf("本次计算一共耗时 %f 秒\n\n",(double)(finish-start)/CLOCKS_PER_SEC);
return 0;
}



  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017