深度搜索算法
在计算机科学和信息技术学院目录第四次课中，深度搜索算法被引入作为解决某些问题的方法。当我们遇到一些问题时，我们不能确切地找到数学模型，即找不到一种直接求解的方法，这时我们可以采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）。
深度搜索算法的要点包括：
1. 初始状态
2. 重复产生新状态
3. 检查新状态是否为目标，是结束，否则转（2）
深度搜索算法可以分为两种：宽度优先搜索和深度优先搜索。宽度优先搜索是以接近起始状态的程序依次扩展状态的，而深度优先搜索是扩展是首先扩展新产生的状态。
深度优先搜索算法用一个数组存放产生的所有状态。该算法的步骤包括：
1. 把初始状态放入数组中，设为当前状态
2. 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态
3. 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态
4. 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法
5. 如果数组为空，说明无解
6. 转到（２）
深度优先搜索算法可以使用递归实现，例如使用Pascal语言，可以自动实现回溯（利用局部变量）。非递归实现的算法也可以使用。
一个简单的迷宫问题可以使用深度优先搜索算法解决，例如 tìm一条通路从左上角入口到右下角出口。下面是一个使用Pascal语言编写的深度优先搜索程序：
const
11 10 101 1 1 1 1 0 0 0 1 1
d:array[1..4,1..4]of integer=((1,1,0,0),(0,1,1,1),(1,1,0,1),(0,1,1,1));
c:array[1..4,1..2]of -1..1=((0,1),(0,-1),(1,0),(-1,0));
var
a:array[1..16,1..2]of integer;
i,j:integer;
procedure play(k:integer);
var
i:integer;
begin
if (a[k,1]=4)and(a[k,2]=4) then
begin
for i:=1 to k do
write('(',a[i,1],',',a[i,2],')');
writeln;
readln;
exit;
end;
for i:=1 to 4 do
if (a[k,1]+c[i,1]>0)and(a[k,1]+c[i,1]<5) and(a[k,2]+c[i,2]>0)and(a[k,2]+c[i,2]<5) then
if d[a[k,1],a[k,2]]=1 then
begin
d[a[k,1],a[k,2]]:=2;
a[k+1,1]:=a[k,1]+c[i,1];
a[k+1,2]:=a[k,2]+c[i,2];
play(k+1);
end;
end;
该程序使用了深度优先搜索算法来解决迷宫问题，它可以找到一条通路从左上角入口到右下角出口。
VIP享7折，此内容立减4.47元 
