【题目1】N皇后问题(八皇后问题的扩展)
【题目2】排球队员站位问题
【题目3】把自然数Ｎ分解为若干个自然数之和。
【题目4】把自然数Ｎ分解为若干个自然数之积。
【题目5】马的遍历问题。
【题目6】加法分式分解
【题目7】地图着色问题
【题目8】在n*n的正方形中放置长为2,宽为1的长条块,
【题目9】找迷宫的最短路径。（广度优先搜索算法）
【题目10】火车调度问题
【题目11】农夫过河
【题目12】七段数码管问题。
【题目13】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.
【题目14】在4×4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.
【题目15】迷宫问题.求迷宫的路径.(深度优先搜索法)
【题目16】一笔画问题
【题目17】城市遍历问题.
【题目18】棋子移动问题
【题目19】求集合元素问题（1,2x+1,3X+1类)
【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行
每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; {放皇后数组}
b:array[2..2*max] of boolean; {/对角线标志数组}
c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
col:array[1..max] of boolean; {列标志数组}
total:integer; {统计总数}
procedure output; {输出}
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; {判断第dep行第i列可放否} begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and (col[i]=true) then ok:=true
end;
procedure try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do {每一行均有max种放法}
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; {/对角线已放标志}
c[dep-i]:=false; {\对角线已放标志}
col[i]:=false; {列已放标志}
if dep=max then output
else try(dep+1); {递归下一层}
a[dep]:=0; {取走皇后,回溯}
b[i+dep]:=true; {恢复标志数组}
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
【测试数据】
n=8 八皇后问题
No.[ 1] 1 5 8 6 3 7 2 4 No.[ 2] 1 6 8 3 7 4 2 5 No.[ 3] 1 7 4 6 8 2 5 3 No.[ 4] 1 7 5 8 2 4 6 3 No.[ 5] 2 4 6 8 3 1 7 5 No.[ 6] 2 5 7 1 3 8 6 4 No.[ 7] 2 5 7 4 1 8 6 3 No.[ 8] 2 6 1 7 4 8 3 5 No.[ 9] 2 6 8 3 1 4 7 5 No.[10] 2 7 3 6 8 5 1 4 No.[11] 2 7 5 8 1 4 6 3 No.[12] 2 8 6 1 3 5 7 4 No.[13] 3 1 7 5 8 2 4 6 No.[14] 3 5 2 8 1 7 4 6 No.[15] 3 5 2 8 6 4 7 1 No.[16] 3 5 7 1 4 2 8 6 No.[17] 3 5 8 4 1 7 2 6 No.[18] 3 6 2 5 8 1 7 4 No.[19] 3 6 2 7 1 4 8 5 No.[20] 3 6 2 7 5 1 8 4 No.[21] 3 6 4 1 8 5 7 2 No.[22] 3 6 4 2 8 5 7 1 No.[23] 3 6 8 1 4 7 5 2 No.[24] 3 6 8 1 5 7 2 4 No.[25] 3 6 8 2 4 1 7 5 No.[26] 3 7 2 8 5 1 4 6 No.[27] 3 7 2 8 6 4 1 5 No.[28] 3 8 4 7 1 6 2 5 No.[29] 4 1 5 8 2 7 3 6 No.[30] 4 1 5 8 6 3 7 2 No.[31] 4 2 5 8 6 1 3 7 No.[32] 4 2 7 3 6 8 1 5 No.[33] 4 2 7 3 6 8 5 1 No.[34] 4 2 7 5 1 8 6 3 No.[35] 4 2 8 5 7 1 3 6 No.[36] 4 2 8 6 1 3 5 7 No.[37] 4 6 1 5 2 8 3 7 No.[38] 4 6 8 2 7 1 3 5 No.[39] 4 6 8 3 1 7 5 2 No.[40] 4 7 1 8 5 2 6 3 No.[41] 4 7 3 8 2 5 1 6 No.[42] 4 7 5 2 6 1 3 8 No.[43] 4 7 5 3 1 6 8 2 No.[44] 4 8 1 3 6 2 7 5 No.[45] 4 8 1 5 7 2 6 3 No.[46] 4 8 5 3 1 7 2 6 No.[47] 5 1 4 6 8 2 7 3 No.[48] 5 1 8 4 2 7 3 6 No.[49] 5 1 8 6 3 7 2 4 No.[50] 5 2 4 6 8 3 1 7 No.[51] 5 2 4 7 3 8 6 1 No.[52] 5 2 6 1 7 4 8 3 No.[53] 5 2 8 1 4 7 3 6 No.[54] 5 3 1 6 8 2 4 7 No.[55] 5 3 1 7 2 8 6 4 No.[56] 5 3 8 4 7 1 6 2 No.[57] 5 7 1 3 8 6 4 2 No.[58] 5 7 1 4 2 8 6 3 No.[59] 5 7 2 4 8 1 3 6 No.[60] 5 7 2 6 3 1 4 8 No.[61] 5 7 2 6 3 1 8 4 No.[62] 5 7 4 1 3 8 6 2
No.[63] 5 8 4 1 3 6 2 7 No.[64] 5 8 4 1 7 2 6 3
No.[65] 6 1 5 2 8 3 7 4 No.[66] 6 2 7 1 3 5 8 4
No.[67] 6 2 7 1 4 8 5 3 No.[68] 6 3 1 7 5 8 2 4
No.[69] 6 3 1 8 4 2 7 5 No.[70] 6 3 1 8 5 2 4 7
No.[71] 6 3 5 7 1 4 2 8 No.[72] 6 3 5 8 1 4 2 7
No.[73] 6 3 7 2 4 8 1 5 No.[74] 6 3 7 2 8 5 1 4
No.[75] 6 3 7 4 1 8 2 5 No.[76] 6 4 1 5 8 2 7 3
No.[77] 6 4 2 8 5 7 1 3 No.[78] 6 4 7 1 3 5 2 8
No.[79] 6 4 7 1 8 2 5 3 No.[80] 6 8 2 4 1 7 5 3
No.[81] 7 1 3 8 6 4 2 5 No.[82] 7 2 4 1 8 5 3 6
No.[83] 7 2 6 3 1 4 8 5 No.[84] 7 3 1 6 8 5 2 4
No.[85] 7 3 8 2 5 1 6 4 No.[86] 7 4 2 5 8 1 3 6
No.[87] 7 4 2 8 6 1 3 5 No.[88] 7 5 3 1 6 8 2 4
No.[89] 8 2 4 1 7 5 3 6 No.[90] 8 2 5 3 1 7 4 6
No.[91] 8 3 1 6 2 5 7 4 No.[92] 8 4 1 3 6 2 7 5 total:92
对于N皇后:
┏━━━┯━━┯━━┯━━┯━━┯━━┯━━┯━━┓
┃皇后N│4 │5 │6 │7 │8 │9 │10 ┃
┠───┼──┼──┼──┼──┼──┼──┼──┨
┃方案数│2 │10 │4 │40 │92 │352 │724 ┃
┗━━━┷━━┷━━┷━━┷━━┷━━┷━━┷━━┛
【题目】排球队员站位问题
┏━━━━━━━━┓图为排球场的平面图，其中一、二、三、四、五、六为位置编号，┃┃二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，┃┃一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻┠──┬──┬──┨手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队┃四│三│二┃员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，┠──┼──┼──┨２号、３号队员不是二传手，３号、４号队员不在同一排，５号、┃五│六│一┃６号队员不是副攻手。
┗━━┷━━┷━━┛编程求每个队员的站位情况。
【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。
【参考程序】
type sset=set of 1..6;
var a:array[1..6]of 1..6;
d:array[1..6]of sset;
i:integer;
procedure output; {输出}
begin
if not( (a[3]in [2,3,4])= (a[4] in[2,3,4])) then
begin { 3,4号队员不在同一排}
write('number:');for i:=1 to 6 do write(i:8);writeln;
write('weizhi:');for i:=1 to 6 do write(a[i]:8);writeln;
end;
end;
procedure try(i:integer;s:sset); {递归过程i:第i个人,s:哪些位置已安排人了} var
j,k:integer;
begin
for j:=1 to 6 do begin {每个人都有可能站1-6这6个位置}
if (j in d[i]) and not(j in s) then begin
{j不在d[i]中,则表明第i号人不能站j位. j如在s集合中,表明j位已排人了}
a[i]:=j; {第i 人可以站j 位}
if i<6 then try(i+1,s+[j]) {未安排妥,则继续排下去}
else output; {6个人都安排完,则输出}
end;
end;
end;
begin
for i:=1 to 6 do d[i]:=[1..6]-[i]; {每个人的站位都与球衣的号码不同} d[1]:=d[1]-[1,5,6];
d[6]:=d[6]-[1,5,6]; {1,6号队员不在后排}
d[2]:=d[2]-[2,5];
d[3]:=d[3]-[2,5]; {2,3号队员不是二传手}
d[5]:=d[5]-[3,6];
d[6]:=d[6]-[3,6]; {5,6号队员不是副攻手}
try(1,[]);
end.
【题目】把自然数Ｎ分解为若干个自然数之和。
【参考答案】
n │total
5 │7
6 │11
7 │15
10 │42
100 │190569291
【参考程序】
var n:byte; num:array[0..255] of byte; total:word;
procedure output(dep:byte);
var j:byte;
begin
for j:=1 to dep do write(num[j]:3);writeln; inc(total); end;
procedure find(n,dep:byte); {N:待分解的数,DEP:深度}
var i,j,rest:byte;
begin
for i:=1 to n do {每一位从N到1去试}
if num[dep-1]<=i then {保证选用的数大于前一位}
begin
num[dep]:=i;
rest:=n - i; {剩余的数进行下一次递归调用}
if (rest>0) then begin find(rest,dep+1);end
else if rest=0 then output(dep);{刚好相等则输出} num[dep]:=0;
end;
end;
begin {主程序}
writeln('input n:');readln(n);
fillchar(num,sizeof(num),0);
total:=0; num[0]:=0;
find(n,1);
writeln('sum=',total);
end.
【题目】把自然数Ｎ分解为若干个自然数之积。
【参考程序】
var path :array[1..1000] of integer;
total,n:integer;
procedure find(k,sum,dep:integer); {K:}
var b,d:Integer;
begin
if sum=n then {积等于N}
begin
write(n,'=',path[1]);
for d:=2 to dep-1 do write('*',path[d]);
writeln;inc(total);
exit;
end;
if sum>n then exit; {累积大于N}
for b:= trunc(n/sum)+1 downto k do {每一种可能都去试}
begin
path[dep]:=b;
find(b,sum*b,dep+1);
end;
end;
begin
readln(n); total:=0;
find(2,1,1);writeln('total:',total);
readln;
end.
【题目】马的遍历问题。在Ｎ＊Ｍ的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。
【参考程序】{深度优先搜索法}
const n=5;m=4;
fx:array[1..8,1..2]of -2..2=((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),
(-2,1),(-1,2)); {八个方向增量}
var
dep,i:byte; x,y:byte;
cont:integer; {统计总数}
a:array[1..n,1..m]of byte; {记录走法数组}
procedure output; {输出,并统计总数}
var x,y:byte;
begin
cont:=cont+1; writeln;
writeln('count=',cont);
for y:=1 to n do begin
for x:=1 to m do write(a[y,x]:3); writeln;
end; { readln; halt;}
end;
procedure find(y,x,dep:byte);
var i,xx,yy:integer;
begin
for i:=1 to 8 do
begin
xx:=x+fx[i,1];yy:=y+fx[i,2]; {加上方向增量,形成新的坐标}
if ((xx in [1..m])and(yy in [1..n]))and(a[yy,xx]=0) then
{判断新坐标是否出界,是否已走过?}
begin
a[yy,xx]:=dep; {走向新的坐标}
if (dep=n*m) then output
else find(yy,xx,dep+1); {从新坐标出发,递归下一层} a[yy,xx]:=0 {回溯,恢复未走标志}
end;
end;
end;
begin
cont:=0;
fillchar(a,sizeof(a),0);
dep:=1;
writeln('input y,x');readln(y,x);
{ x:=1;y:=1;}
if (y>n) or(x>m) then begin writeln('x,y error!');halt;end;
a[y,x]:=1;
find(y,x,2);
if cont=0 then writeln('No answer!') else write('The End!');
readln;
end.
【题目】加法分式分解。如：1/2=1/4+1/4.找出所有方案。
输入：ＮＭＮ为要分解的分数的分母
Ｍ为分解成多少项
【参考程序】
program fenshifenjie;
const nums=5;
var
t,m,dep:integer;
n,maxold,max,j:longint;
path:array[0..nums] of longint;
maxok,p:boolean;
sum,sum2:real;
procedure print;
var i:integer;
begin
t:=t+1;
if maxok=true then begin maxold:=path[m];maxok:=false;end;
write ('NO.',t);
for i:=1 to m do write(' ',path[i]:4); writeln;
if path[1]=path[m] then begin writeln('Ok! total:',t:4);readln;halt;end; end;
procedure input;
begin
writeln ('input N:'); readln(n);
writeln ('input M(M<=',nums:1,'):'); readln(m);
if (n<=0) or (m<=0) or (m>4) or (n>maxlongint)
then begin writeln('Invalid Input!');readln;halt;end; end;
function sum1(ab:integer):real;
var a,b,c,d,s1,s2:real;
i:integer;
begin
if ab=1 then
sum1:=1/path[1]
else
begin
a:=path[1];
b:=1 ;
c:=path[2];
d:=1;
for i:=1 to ab-1 do
begin
s2:=(c*b+a*d);
s1:=(a*c);
a:=s1;
b:=s2;
c:=path[i+2];
end;
sum1:=s2/s1;
end;
end;
procedure back;
begin
dep:=dep-1;
if dep<=m-2 then max:=maxold;
sum:=sum-1/path[dep];
j:=path[dep];
end;
procedure find;
begin
repeat
dep:=dep+1;
j:=path[dep-1]-1;
p:=false;
repeat
j:=j+1;
if (dep<>m) and (j<=max) then
if (sum+1/j) >=1/n then p:=false
else begin
p:=true;
path[dep]:=j;
sum:=sum+1/path[dep];
end
else if j>max then back;
if dep=m then begin
path[dep]:=j;
sum2:=sum1(m);
if (sum2)>1/n then p:=false;
if (sum2)=1/n then begin print;
max:=j;
back;
end;
if (sum2<1/n) then back;
if (j>=max) then back;
end;
until p
until dep=0;
end;
begin
INPUT;
maxok:=true;
for t:=0 to m do path[t]:=n;
dep:=0; t:=0; sum:=0;
max:=maxlongint;
find;
readln;
end.
【题目】地图着色问题
【参考程序１】
const lin:array[1..12,1..12] of 0..1 {区域相邻数组,1表示相邻} =((0,1,1,1,1,1,0,0,0,0,0,0),
(1,0,1,0,0,1,1,1,0,0,0,0),
(1,1,0,1,0,0,0,1,1,0,0,0),
(1,0,1,0,1,0,1,0,1,1,0,0),
(1,0,0,1,0,1,0,0,0,1,1,0),
(1,1,0,0,1,0,1,0,0,0,1,0),
(0,1,0,0,0,1,0,1,0,0,1,1),
(0,1,1,0,0,0,1,0,1,0,0,1),
(0,0,1,1,0,0,0,1,0,1,0,1),
(0,0,0,1,1,0,0,0,1,0,1,1),
(0,0,0,0,1,1,1,0,0,1,0,1),
(0,0,0,0,0,0,1,1,1,1,1,1));
var color:array[1..12] of byte; {color数组放已填的颜色} total:integer;
function ok(dep,i:byte):boolean; {判断选用色i是否可用}
var k:byte; {条件:相邻的区域颜色不能相同}
begin
for k:=1 to dep do
if (lin[dep,k]=1) and (i=color[k]) then begin ok:=false;exit;end; ok:=true;
end;
procedure output; {输出}
var k:byte;
begin
for k:=1 to 12 do write(color[k],' ');writeln;
total:=total+1;
end;
procedure find(dep:byte); {参数dep:当前正在填的层数}
var i:byte;
begin
for i:=1 to 4 do begin {每个区域都可能是1-4种颜色}
if ok(dep,i) then begin
color[dep]:=i;
if dep=12 then output else find(dep+1);
color[dep]:=0; {恢复初始状态,以便下一次搜索}
end;
end;
end;
begin
total:=0; {总数初始化}
fillchar(color,sizeof(color),0);
find(1);
writeln('total:=',total);
end.
【参考程序２】
const {lin数组:代表区域相邻情况}
lin:array[1..12] of set of 1..12 =
([2,3,4,5,6],[1,3,6,7,8],[1,2,4,8,9],[1,3,5,9,10],[1,4,6,10,11], [1,2,5,7,11],[12,8,11,6,2],[12,9,7,2,3],[12,8,10,3,4],
[12,9,11,4,5],[12,7,10,5,6],[7,8,9,10,11]);
color:array[1..4] of char=('r','y','b','g');
var a:array[1..12] of byte; {因有12个区域,故a数组下标为1-12}
total:integer;
function ok(dep,i:integer):boolean; {判断第dep块区域是否可填第i种色} var j:integer; { j 为什么设成局部变量?}
begin
ok:=true;
for j:=1 to 12 do
if (j in lin[dep]) and (a[j]=i) then ok:=false;
end;
procedure output; {输出过程}
var j:integer; { j 为什么设成局部变量?}
begin
inc(total); {方案总数加1}
write(total:4); {输出一种方案}
for j:=1 to 12 do write(color[a[j]]:2);writeln;
end;
procedure find(dep:byte);
var i:byte; { i 为什么设成局部变量?}
begin
for i:=1 to 4 do {每一区域均可从4种颜色中选一}
begin
if ok(dep,i) then begin {可填该色}
a[dep]:=i; {第dep块区域填第i种颜色}
if (dep=12) then output {填完12个区域}
else find(dep+1); {未填完}
a[dep]:=0; {取消第dep块区域已填的颜色}
end;
end;
end;
begin {主程序}
fillchar(a,sizeof(a),0); {记得要给变量赋初值!}
total:=0;
find(1);
writeln('End.');
end.
【题目】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何【参考程序１】
const n=4;
var k,u,v,result:integer;
a:array[1..n,1..n]of char;
procedure printf; {输出}
begin
result:=result+1; {方案总数加1}
writeln('--- ',result,' ---');
for v:=1 to n do begin
for u:=1 to n do write(a[u,v]); writeln end; writeln; end;
procedure try; {填放长条块}
var i,j,x,y:integer; full:boolean;
begin
full:=true;
if k<>trunc(n*n/2) then full:=false;{测试是否已放满}
if full then printf; {放满则可输出}
if not full then begin {未满}
x:=0;y:=1; {以下先搜索未放置的第一个空位置}
repeat
x:=x+1;
if x>n then begin x:=1;y:=y+1 end
until a[x,y]=' ';
{找到后,分两种情况讨论}
if a[x+1,y]=' ' then begin {第一种情况:横向放置长条块} k:=k+1; {记录已放的长条数}
a[x,y]:=chr(k+ord('@')); {放置}
a[x+1,y]:=chr(k+ord('@'));
try; {递归找下一个空位置放}
k:=k-1;
a[x,y]:=' '; {回溯,恢复原状}
a[x+1,y]:=' '
end;
if a[x,y+1]=' ' then begin {第二种情况:竖向放置长条块} k:=k+1; {记录已放的长条数}
a[x,y]:=chr(k+ord('0')); {放置}
a[x,y+1]:=chr(k+ord('0'));
try; {递归找下一个空位置放}
k:=k-1;
a[x,y]:=' '; {回溯,恢复原状}
a[x,y+1]:=' '
end;
end;
end;
begin {主程序}
fillchar(a,sizeof(a),' '); {记录放置情况的字符数组,初始值为空格} result:=0; k:=0; {k记录已放的块数,如果k=n*n/2,则说明已放满} try; {每找到一个空位置,把长条块分别横放和竖放试验}
end.
【参考程序２】
const dai:array [1..2,1..2]of integer=((0,1),(1,0));
type node=record
w,f:integer;
end;
var a:array[1..20,1..20]of integer;
path:array[0..200]of node;
s,m,n,nn,i,j,x,y,dx,dy,dep:integer;
p,px:boolean;
procedure inputn;
begin
{ write('input n');readln(n);}
n:=4;
nn:=n*n;m:=nn div 2;
end;
procedure print;
var i,j:integer;
begin
inc(s);writeln('no',s);
for i:=1 to n do begin
for j:=1 to n do
write(a[i,j]:3);writeln;
end;
writeln;
end;
function fg(h,v:integer):boolean;
var p:boolean;
begin
p:=false;
if (h<=n) and (v<=n) then
if a[h,v]=0 then p:=true;
fg:=p;
end;
procedure back;
begin
dep:=dep-1;
if dep=0 then begin p:=true ;px:=true;end else begin
i:=path[dep].w;j:=path[dep].f;
x:=((i-1)div n )+1;y:=i mod n;
if y=0 then y:=n;
dx:=x+dai[j,1];dy:=y+dai[j,2];
a[x,y]:=0;a[dx,dy]:=0;
end;
end;
begin
inputn;
s:=0;
fillchar(a,sizeof(a),0);
x:=0;y:=0;dep:=0;
path[0].w:=0;path[0].f:=0;
repeat
dep:=dep+1;
i:=path[dep-1].w;
repeat
i:=i+1;x:=((i-1)div n)+1;
y:=i mod n;if y=0 then y:=n;
px:=false;
if fg(x,y)
then begin
j:=0;p:=false;
repeat
inc(j);
dx:=x+dai[j,1];dy:=y+dai[j,2];
if fg(dx,dy) and (j<=2) then begin
a[x,y]:=dep;a[dx,dy]:=dep;
path[dep].w:=i;path[dep].f:=j;
if dep=m then begin print;dep:=m+1;back;end else begin p:=true;px:=true;end;
end
else if j>=2 then back
else p:=false;
until p;
end
else if i>=nn then back
else px:=false;
until px;
until dep=0;
readln;
end.
【题目】找迷宫的最短路径。（广度优先搜索算法）
【参考程序】
uses crt;
const
migong:array [1..5,1..5] of integer=((0,0,-1,0,0), (0,-1,0,0,-1), (0,0,0,0,0), (0,-1,0,0,0), (-1,0,0,-1,0));
{迷宫数组}
fangxiang:array [1..4,1..2] of -1..1=((1,0),(0,1),(-1,0),(0,-1));
{方向增量数组}
type node=record
lastx:integer; {上一位置坐标}
lasty:integer;
nowx:integer; {当前位置坐标}
nowy:integer;
pre:byte; {本结点由哪一步扩展而来}
dep:byte; {本结点是走到第几步产生的}
end;
var
lujing:array[1..25] of node; {记录走法数组}
closed,open,x,y,r:integer;
procedure output;
var i,j:integer;
begin
for i:=1 to 5 do begin
for j:=1 to 5 do
write(migong[i,j]:4); writeln;end;
i:=open;
repeat
with lujing[i] do
write(nowy:2,',',nowx:2,' <--');
i:=lujing[i].pre;
until lujing[i].pre=0;
with lujing[i] do
write(nowy:2,',',nowx:2);
end;
begin
clrscr;
with lujing[1] do begin {初始化第一步}
lastx:=0; lasty:=0; nowx:=1;nowy:=1;pre:=0;dep:=1;end; closed:=0;open:=1;migong[1,1]:=1;
repeat
inc(closed); {队列首指针加1,取下一结点}
for r:=1 to 4 do begin {以4个方向扩展当前结点}
x:=lujing[closed].nowx+fangxiang[r,1]; {扩展形成新的坐标值}
y:=lujing[closed].nowy+fangxiang[r,2];
if not ((x>5)or(y>5) or (x<1) or (y<1) or (migong[y,x]<>0)) then begin
{未出界,未走过则可视为新的结点}
inc(open); {队列尾指针加1}
with lujing[open] do begin {记录新的结点数据}
nowx:=x; nowy:=y;
lastx:=lujing[closed].nowx;{新结点由哪个坐标扩展而来}
lasty:=lujing[closed].nowy;
dep:=lujing[closed].dep+1; {新结点走到第几步}
pre:=closed; {新结点由哪个结点扩展而来}
end;
migong[y,x]:=lujing[closed].dep+1; {当前结点的覆盖范围}
if (x=5) and (y=5) then begin {输出找到的第一种方案}
writeln('ok,thats all right');output;halt;end;
end;
end;
until closed>=open; {直到首指针大于等于尾指针,即所有结点已扩展完}
end.
【题目】火车调度问题
【参考程序】
const max=10;
type shuzu=array[1..max] of 0..max;
var stack,exitout:shuzu;
n,total:integer;
合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。
深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。
所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s
#include
< 人工智能 > 实验报告 3 一、实验目的： 掌握汉诺塔的深度有界搜索求解算法的基本思想。 二、实验要求： 用C语言实现汉诺塔的深度有界搜索求解 三、实验语言环境： C语言 四、设计思路： 含有深度界限的深度优先搜索算法如下： (1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。 (2) 如果OPEN为一空表，则失败退出。 (3) 把第一个节点(节点n)从OPEN表移到CLOSED表。 (4) 如果节点n的深度等于最大深度，则转向(2)。 (5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。 (6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。 五、实验代码： #include
long floor; //记录第几层 } node; node queue[362880 / 2 + 1]; //奇偶各一半 long tail, head; long hash[362880 / 32 + 1]; int main() { void Solve(); while (scanf("%ld", &queue[0].map) && queue[0].map) { memset(hash, 0, sizeof(hash)); queue[0].floor = 1; //(根节点)第一层 tail = head = 0; Solve(); printf("max_floor == %d\n", queue[head].floor); printf("total node == %d\n", head + 1); printf("total node in theory [%d]\n", 362880 / 2); } return 0; } void Solve() { node e; long i, map[9], space; long Compress(long *); int V isited(long *); void swap(long &, long &); while (tail <= head) { e = queue[tail++]; for (i=8; i>=0; i--) { map[i] = e.map % 10; if (map[i] == 0) { space = i; } e.map /= 10; } V isited(map); //根节点要置为访问过 if (space >= 3) { //can up swap(map[space - 3], map[space]); if (!Visited(map)) { queue[++head].map = Compress(map); queue[head].floor = queue[tail - 1].floor + 1;
上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号
一、实验目的： 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境： Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求： 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 四、概要设计： 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include
一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验内容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20
广度优先搜索训练题 一、奇怪的电梯 源程序名LIFT.PAS 可执行文件名 LIFT.EXE 输入文件名 LIFT.IN 输出文件名 LIFT.OUT 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。 样例 LIFT.IN 5 1 5 3 3 1 2 5 LIFT.OUT 3 二、字串变换 [问题描述]: 已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）: A1$ -> B1$ A2$ -> B2$ 规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为B2$ …。例如：A$＝'abcd' B$＝'xyz' 变换规则为： ‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’ 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换，使得 A$ 变换为B$。 [输入]: 键盘输人文件名。文件格式如下： A$ B$ A1$ B1$ \
#include
第五章状态空间搜索策略 搜索是人工智能的一个基本问题，是推理不可分割的一部分。搜索是求解问 题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1．1 盲目搜索策略 1．状态空间图的搜索策略 为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。一般情况下，不同的知识表示对应着不同的求解方法。状态空间表示法是一 种用“状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S ，F， S g )。 利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。 算法5．1 状态空间图的一般搜索算法 ①建立一个只含有初始节点S 0的搜索图G，把S 放入OPEN表中。 ②建立CLOSED表，且置为空表。
③判断OPEN表是否为空表，若为空，则问题无解，退出。 ④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。 ⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解 的这条路径得到。 即可从图G中沿着指针从n到S ⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。 ⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。 ⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2．宽度优先搜索策略 宽度优先搜索是一种盲目搜索策略。其基本思想是，从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面(即将扩展得到的后继节点放于OPEN表的末端)。 宽度优先搜索的盲目性较大，搜索效率低，这是它的缺点。但宽度优先搜索策略是完备的，即只要问题有解，用宽度优先搜索总可以找到它的解。 3．深度优先搜索 深度优先搜索也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的
华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include
{ int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2;
*问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或
若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若
猴子摘香蕉问题的宽度优先搜索和最大深度为5的有界深度优先搜索（注意：括号中的斜体字是我做的说明，不是答案的内容） 解：设一个状态由四元组（W, X, Y , Z ）来表示，其中： 1. W 代表猴子的位置，其取值可为a ，b 和c ； 2. X 代表猴子和箱子的位置关系，取值为0和1，其中0表示猴子在箱子下，而1表示猴子在箱子上面； 3. Y 代表箱子的位置，其取值可为a ，b 和c ； 4. Z 代表是否摘得香蕉，取值为0和1，其中0表示未摘得香蕉而1表示已经摘到了香蕉。 则本问题的初始状态为（a ，0，c ，0），而目标状态为（b ，1，b ，1）(注意：目标状态写为 (U,V,H,1 )也可以，因为我们只关心摘到香蕉)。 本问题中涉及的算符有四个，分别为 1. 移动：Goto （U ），其中U 可取a ，b 和c ，其执行条件为X ＝0（即猴子不在箱子上），其效果如下式 (,0,,)goto()(,0,,)W Y Z U U Y Z ，其中，U ＝a ，b ，c 且U W ≠（注意：加U W ≠是为了减少后面状态图中节点到自身的弧；(,0,,)goto()(,0,,)W Y Z U U Y Z 表示在状态(,0,,)W Y Z 上执行Goto （U ）操作，使得原状态变为状态(,0,,)U Y Z ） 2. 推箱子：Pushbox(U)，其中U 可取a ，b 和c ，其执行条件为W ＝Y （猴子和箱子在同一个位置）且X ＝0（猴子不在箱子上），其效果如下式 (,0,,)Pushbox()(,0,,)V V Z U U U Z ，其中U, V ＝a ，b ，c ，且U V ≠（注意：加U V ≠的作用同上U W ≠） 3. 攀爬：Climb ，其执行条件为W=Y （猴子和箱子在同一个位置）且X ＝0（猴子不在箱子上），其效果如下 (,0,,)Climb(,1,,)U U Z U U Z ，其中U ＝a ，b 或c 4. 摘香蕉：Grasp ，其执行条件为W ＝Y ＝b （猴子和箱子都在b 位置）, X=1（猴子在箱子上）且Z ＝0（猴子未摘得香蕉），其效果如下 (,1,,0)Grasp(,1,,1)b b b b 。 设在同一状态下，检查并应用可应用的必要算符的次序如下：goto(a), goto(b), goto(c), pushbox(a), pushbox(b), pushbox(c), climb, grasp. 则宽度优先搜索树如下图所示，其中状态左上角的数字代表该状态被扩展的顺序（是“生孩子”的顺序而不是 “出生”的顺序）：
2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 深度优先搜索： 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 下面图中的数字显示了深度优先搜索顶点被访问的顺序。 "* ■ J 严-* 4 t C '4 --------------------------------- --- _ 为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则： (1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。 (2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。 (3) 如果不能执行规则1和规则2，就完成了整个搜索过程。 广度优先搜索： 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中， 算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区 域。它是用队列来实现的。 下面图中的数字显示了广度优先搜索顶点被访问的顺序。 实现广度优先搜索，也要遵守三个规则: ⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。（2）如果因为已经没有未访问顶点而不能执行规则1 图的广度优先搜索的应用 ◆内容提要 广度优先搜索是分层次搜索，广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。本讲座就最短路径问题、分酒问题、八数码问题三个典型的范例，从问题分析、算法、数据结构等多方面进行了讨论，从而形成图的广度优先搜索解决问题的模式，通过本讲座的学习，能明白什么样的问题可以采用或转化为图的广度优先搜索来解决。在讨论过程中，还同时对同一问题进行了深层次的探讨，进一步寻求解决问题的最优方案。 ◆知识讲解和实例分析 和深度优先搜索一样，图的广度优先搜索也有广泛的用途。由于广度优先搜索是分层次搜索的，即先将所有与上一层顶点相邻接的顶点搜索完之后，再继续往下搜索与该层的所有邻接而又没有访问过的顶点。故此，当某一层的结点出现目标结点时，这时所进行的步骤是最少的。所以，图的广度优先搜索广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。 本次讲座就几个典型的范例来说明图的广度优先搜索的应用。 先给出图的广度优先搜索法的算法描述： F:=0;r:=1;L[r]:=初始值; H:=1;w:=1;bb:=true; While bb do begin H:=h+1;g[h]:=r+1; For I:=1 to w do Begin F:=f+1; For t:=1 to 操作数do Begin ⑴m:=L[f]; {出队列}； ⑵判断t操作对m结点的相邻结点进行操作;能则设标记bj:=0,并生成新结点;不能,则设标记bj:=1; if bj:=0 then {表示有新结点生成} begin for k:=1 to g[h]-1 do if L[k]=新结点then {判断新扩展的结点是否以前出现过} begin bj:=1;k:=g[h]-1 一：单选题 1. 人工智能的目的是让机器能够（D），以实现某些脑力劳动的机械化。 A. 具有完全的智能 B. 和人脑一样考虑问题 C. 完全代替人 D. 模拟、延伸和扩展人的智能 2. 下列关于人工智能的叙述不正确的有（C）。 A. 人工智能技术它与其他科学技术相结合极大地提高了应用技术的智能化水平。 B. 人工智能是科学技术发展的趋势。 C. 因为人工智能的系统研究是从上世纪五十年代才开始的，非常新，所以十分重要。 D. 人工智能有力地促进了社会的发展。 3. 自然语言理解是人工智能的重要应用领域，下面列举中的（C）不是它要实现的目标。 A. 理解别人讲的话。 B. 对自然语言表示的信息进行分析概括或编辑。 C. 欣赏音乐。 D. 机器翻译。 4. 下列不是知识表示法的是（A）。 A. 计算机表示法 B. 谓词表示法 C. 框架表示法 D. 产生式规则表示法 5. 关于“与/或”图表示知识的叙述，错误的有（D）。 A. 用“与/或”图表示知识方便使用程序设计语言表达，也便于计算机存储处理。 B. “与/或”图表示知识时一定同时有“与结点”和“或结点”。 C. “与/或”图能方便地表示陈述性知识和过程性知识。 D. 能用“与/或”图表示的知识不适宜用其他方法表示。 6. 一般来讲，下列语言属于人工智能语言的是（D）。 A. VJ B. C# C. Foxpro D. LISP 7. 专家系统是一个复杂的智能软件，它处理的对象是用符号表示的知识，处理的过程是（C）的过程。 A. 思考 B. 回溯 C. 推理 D. 递归 8. 确定性知识是指（A）知识。 A. 可以精确表示的 B. 正确的 C. 在大学中学到的知识 D. 能够解决问题的 9. 下列关于不精确推理过程的叙述错误的是（B）。 A. 不精确推理过程是从不确定的事实出发 B. 不精确推理过程最终能够推出确定的结论 C. 不精确推理过程是运用不确定的知识 D. 不精确推理过程最终推出不确定性的结论 10. 我国学者吴文俊院士在人工智能的（A）领域作出了贡献。 A. 机器证明 B. 模式识别 C. 人工神经网络 D. 智能代理 基于C语言的广度优先搜素算法的实现 1.算法说明 广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形： （1）把根节点放到队列的末尾。 （2）每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 （3）找到所要找的元素时结束程序。 （4）如果遍历整个树还没有找到，结束程序。 本次算法的应用中，我用这个队列来保存最短路径。首先我定义队列为“真进假出”，所谓“真进”就是当添加一个元素时，把元素放置队尾，然后rear++, 而“假出”就是当删除一个元素时，并没有真的删除队首元素，只是front++。 通过比较搜索所得的所有可行路径的长度，这样我们就可以从队列中获取一条最短路径！ 2.代码及结果 #include 第五章状态空间搜索策略搜索是人工智能的一个基本问题，是推 理不可分割的一部分。搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1．1 盲目搜索策略 1．状态空间图的搜索策略 为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。一般情况下，不同的知识表示对应着不同的求解方法。状态空间表示法是一种用“状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S，F， 0S)。g利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。 算法5．1 状态空间图的一般搜索算法 ①建立一个只含有初始节点S的搜索图G，把S放入OPEN表中。00表，且置为空表。CLOSED②建立 ③判断OPEN表是否为空表，若为空，则问题无解，退出。 ④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。 ⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S的这条路径得到。0⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。 ⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。 ⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2．宽度优先搜索策略 宽度优先搜索是一种盲目搜索策略。其基本思想是，从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排 *问题描述： 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若广度优先搜索和深度优先搜索
图的广度优先搜索的应用
人工智能复习题(答案)
基于C语言的广度优先搜索
人工智能第五章状态空间搜索策略山东大学期末考试知识点复习
邻接矩阵表示图_深度_广度优先遍历
相关主题
文本预览