骑士巡游问题时间复杂度是多少

楼上的程序太麻烦，效率低【骑士游历问题】 设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。输入： m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)输出： 路径数目（若不存在，则输出0）【分析】 本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。（专为楼下设计） 从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。 阶段i：中国象棋马当前的列位置（x1≤i≤x2） 状态j：中国象棋马在i列的行位置（1≤i≤m） 状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目附标程：const maxm=50; maxn=50;var m,n,x1,y1,x2,y2:integer; i,j,k,x,y:integer; map:array[-2..maxm+2,-2..maxn+2] of extended;beginfillchar(map,sizeof(map),0);readln(m,n,x1,y1,x2,y2);map[x1,y1]:=1;for i:=x1+1 to x2 do for j:=1 to m do map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];writeln(map[x2,y2]:0:0);end. 搜索比较慢，有代码如下：program p7_1;const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2); dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);var board:array[-1..7,-1..7] of integer; t,i,j,a,b:integer;procedure search(t,x,y:integer);var p,m,n:integer;begin if t=26 then begin for m:=1 to 5 do begin for n:=1 to 5 do write(board[m,n]:3); writeln; end; t:=-1; halt end; if board[x,y]=0 then begin board[x,y]:=t;inc(t); for p:=1 to 8 do search(t,x+dx[p],y+dy[p]); board[x,y]:=0; end;end;begin t:=1; for i:=-1 to 7 do for j:=-1 to 7 do board[i,j]:=-1; for a:=1 to 5 do for b:=1 to 5 do board[a,b]:=0; search(t,1,1); if t-1 then write('Wrong!');end.

创新互联建站基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽，联通大带宽，移动大带宽，多线BGP大带宽租用,是为众多客户提供专业遂宁托管服务器报价，主机托管价格性价比高，为金融证券行业服务器托管，ai人工智能服务器托管提供bgp线路100M独享，G口带宽及机柜租用的专业成都idc公司。

骑士巡游问题

没做过，看过。“骑士总是移向具有最少出口且没有到达过的方格之一”是说，它可移动的位置有N个，在这N个中，寻找下一次可移动的位置最少的那个，做为骑士要去的点的位置。这是一种贪婪法，有的位置有解但你却求不出来。

骑士巡游问题 pascal 急！！！

楼上的程序太麻烦，效率低

【骑士游历问题】

设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。

输入：

m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)

输出：

路径数目（若不存在，则输出0）

【分析】

本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。（专为楼下设计）

从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。

阶段i：中国象棋马当前的列位置（x1≤i≤x2）

状态j：中国象棋马在i列的行位置（1≤i≤m）

状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目

附标程：

const

maxm=50;

maxn=50;

var

m,n,x1,y1,x2,y2:integer;

i,j,k,x,y:integer;

map:array[-2..maxm+2,-2..maxn+2] of extended;

begin

fillchar(map,sizeof(map),0);

readln(m,n,x1,y1,x2,y2);

map[x1,y1]:=1;

for i:=x1+1 to x2 do

for j:=1 to m do

map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];

writeln(map[x2,y2]:0:0);

end.

搜索比较慢，有代码如下：

program p7_1;

const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2);

dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);

var board:array[-1..7,-1..7] of integer;

t,i,j,a,b:integer;

procedure search(t,x,y:integer);

var p,m,n:integer;

begin

if t=26 then begin

for m:=1 to 5 do begin

for n:=1 to 5 do write(board[m,n]:3);

writeln;

end;

t:=-1;

halt

end;

if board[x,y]=0 then begin

board[x,y]:=t;inc(t);

for p:=1 to 8 do search(t,x+dx[p],y+dy[p]);

board[x,y]:=0;

end;

end;

begin

t:=1;

for i:=-1 to 7 do

for j:=-1 to 7 do board[i,j]:=-1;

for a:=1 to 5 do

for b:=1 to 5 do board[a,b]:=0;

search(t,1,1);

if t-1 then write('Wrong!');

end.

网站栏目：骑士巡游java代码 骑士源码
文章链接：http://myzitong.com/article/dopjjhg.html