电工电子基础Ⅰ教学大纲Read.doc

《算法设计与分析》实验指导书
课程编号：09110112
课程名称：算法设计与分析
英文名称：Algorithms Design and Analysis

适应专业：计算机科学与技术
执 笔 人：沙莎
实验指导书名称：计算机算法基础

实验一 分治法
1、 基本要求
1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。
2）掌握分治法的一般控制流程
DanC(p,q)
global n，A[1:n]; integer m,p,q; // 1£p£q£n
if Small(p,q) then return G(p,q);
else m=Divide(p,q); // p£m<q
return Combine(DanC(p,m),DanC(m+1,q));
endif
end DanC
3）实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

2、 实验内容
1） 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。
2） 输入10组相同的数据，验证排序结果和完成排序的比较次数。
3） 与复杂性函数所计算的比较次数比较。
4） 用表格列出比较结果。
5） 给出文字分析。

3、 归并排序算法和快速排序算法
归并排序算法
procedure MERGESORT(low，high)
//A(low；high)是一个全程数组，它含
有high-low+1≥0个待排序的元素//
integer low，high；
if low<high；
then mid← ， //求这个集合的分割点//
call MERGESORT(low，mid) //将一个子集合排序//
call MERGESORT(mid+1，high) //将另一个子集合排序
call MERGE(low，mid，high) //归并两个已排序的子集合//
endif
end MERGESORT
归并两个已排序的集合
procedure MERGE(low，mid，high)
//A(low：high)是一个全程数组//
//辅助数组B(low；high)//
integer h，i，j，k；
h←low；i←low；j←mid+1；
while h≤mid and j≤high do //当两个集合都没取尽时//
if A(h)≤A(j) then B(i) ←A(h)；h←h+1
else B(i) ←A(j)；j←j+1
endif
i←i+1
repeat
if h>mid then
for k←j to high do //处理剩余的元素//
B(i) ←A(k)；i←i+1
repeat
else for k←h to mid do
B(i) ←A(k)；i←i+1
repeat
endif
将已归并的集合复制到A
end MERGE

快速排序算法
QuickSort(p,q)
//将数组A[1:n]中的元素
A[p], A[p+1], ¼ , A[q]按不降次序排列，
并假定A[n+1]是一个确定的、且大于
A[1:n]中所有的数。//
int p,q; global n, A[1:n];
if p<q then
j=Partition(p, q+1); // 划分后j成为划分元素的位置
QuickSort(p,j-1);
QuickSort(j+1,q);
endif
end QuickSort
procedure PARTITION(m，p)
//退出过程时，p带着划分元素所在的下标位置。//
integer m，p，i；global A(m：p-1)
v←A(m)；i←m //A(m)是划分元素//
loop
loop i←i+1 until A(i)≥v repeat //i由左向右移//
loop p←p-1 until A(p)≤v repeat //p由右向左移//
if i<p
then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位//
else exit
endif
repeat
A(m) ←A(p)；A(p) ←v //划分元素在位置p//
End PARTITION

实验二 贪心法

1、 基本要求
1） 优化问题
有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。
2） 贪心法求优化问题
算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。
2）一般方法
① 根据题意，选取一种量度标准。
② 按这种量度标准对这n个输入排序
③ 依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
procedure GREEDY(A，n) /*贪心法一般控制流程*/
//A(1：n)包含n个输入//
solutions←φ //将解向量solution初始化为空／
for i←1 to n do
x←SELECT(A)
if FEASIBLE(solution，x)
then solutions←UNION(solution，x)
endif
repeat
return(solution)
end GREEDY

3） 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。

2、 实验内容
1） 编程实现背包问题贪心算法和最小生成树prim算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。
2） 输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。
3） 将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。

3、 背包问题贪心算法和prim算法
背包问题的贪心算法
procedure KNAPSACK(P，W，M，X，n)
//P(1：n)和W(1；n)分别含有按
P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值
和重量。M是背包的容量大小，而x(1：n)是解向量//
real P(1：n)，W(1：n)，X(1：n)，M，cu；
integer i，n；
X←0 //将解向量初始化为零//
cu←M //cu是背包剩余容量//
for i←1 to n do
if W(i)>cu then exit endif
X(i) ←1
cu←cu-W(i)
repeat
if i≤n then X(i) ←cu/ W(i)
endif
end GREEDY-KNAPSACK
procedure prim(G,)
status←“unseen” // T为空
status[1]←“tree node” // 将1放入T
for each edge(1,w) do
status[w]←“fringe” // 找到T的邻接点
dad[w] ←1; //w通过1与T建立联系
dist[w] ←weight(1,w) //w到T的距离
repeat
while status[t]≠ “tree node” do
pick a fringe u with min dist[w] // 选取到T最近的节点
status[u]←“tree node”
for each edge(u,w) do
修改w和T的关系
repeat
repeat

实验三 动态规划
1、 基本要求
1） 理解最优子结构的问题。
有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。
对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。
最优子结构性质：原问题的最优解包含了其子问题的最优解。
子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。
2） 理解分段决策Bellman方程。
每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。

us 初始值，uj第j段的最优值。
3） 一般方法
① 找出最优解的性质，并刻画其结构特征；
② 递归地定义最优值（写出动态规划方程）；
③ 以自底向上的方式计算出最优值；
④ 根据计算最优值时得到的信息，构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。
2、 实验内容
1） 编程实现多段图的最短路经问题的动态规划算法。
2） 图的数据结构采用邻接表。
3） 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。
4） 验证算法的时间复杂性。

3、 多段图算法
procedure FGRAPH(E，k，n，P)
//输入是按段的顺序给结点编号的，有n个结点
的k段图。E是边集，c(i，j)是边<i,j>的成本。
P(1：k)是最小成本路径。//
real COST(n)，integerD(n一1)，P(k)，r，j，k，n
COST(n)← 0
for j←n-1to 1by－1do //计算COST(j)//
　设r是一个这样的结点，(j，r)ÎE且使c(j，r)+COST(r)取最小值
　COST(j)←c(j，r)+COST(r)
D(j)←r
repeat //向前对j-1进行决策//
P(1)←1；P(k)←n；
for j←2 to k-1 do //找路径上的第j个节点//
P(j)←D ( P(j-1) )
repeat
end FGRAPH

实验四 深度优先搜索
1、 基本要求
1） 理解深度优先搜索策略
是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点v，如果边（v，w）是还未探测的边，则沿（v，w）继续搜索下去。当所有的边（v，w）都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。
2） 理解深度优先搜索过程中顶点的三种状态
还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。
2、 实验内容
1） 编程实现深度优先搜索算法。
2） 修改算法使之可以找出图的所有树。
3） 修改算法使之可以判断图是否为一棵树。
4） 修改算法使之可以判断图是否存在一个环。

3、 深度优先算法

procedure DFS(G);
for 每个顶点u∈G do
color[u]← White;
repeat
for每个顶点u∈G do
if color[u]=White
then DFS_Visit(G,u);
end;

procedure DFS_Visit(u);
color[u]←Gray;
for (u,w)∈E do //探寻边(u,w)
if color[w]=White
then DFS_Visit(w);
repeat
color[u]←Black; //完成后置u为黑色
end;

实验五 回溯法
1、 基本要求
1） 理解可用回溯法求解的问题
问题P通常要能表达为对已知的、由n元组(x1，…，xn)组成的状态空间E={(x1，…，xn)| xiÎSi,i=1,2,…n}，给定关于n元组中的分量的一个约束集D，求满足D的全部约束条件的所有n元组。 Si 是 xi 的定义域且Si 是有穷集，称E中满足D 的全部约束条件的所有n元组为问题P的一个解。
2） 理解回溯法的基本思想
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法的形式描述：
procedure BACAKTRACE(n)
k =1 ;
while (k>0) do
if Tk (x1，x2，…， x k-1)的值还未取遍 then
{xk←Tk (x1，x2，…， x k-1)中未取遍过的值；
if Bk (x1，x2，…， x k) then
{(x1，x2，…， x k)被激活；
if k ==n then 输出(x1，x2，…， x n)；
else k =k+1； // 深度扩展搜索
}
}
else k = k -1 // 试探完了所有的x k，回溯
end BACAKTRACE

2、 实验内容
1） 编程实现n皇后算法。
2） 用图形输出中间过程。
3） 在程序中添加统计扩展节点数，估计算法的复杂性。
3、 n皇后算法
procedure NQUEENS(n)
X(1)←0；k←1 //k是当前行；X(k)是当前列//
While k>0 do //对所有的行执行以下语句//
{ X(k)←X(k)+1 //移到下一列//
While X(k)≤n and not PLACE(k) do
X(k)←X(k)十l
if X(k)≤n //找到一个位置//
then if k=n //是一个完整的解吗//
then print(X) //是，打印这个数组//
else {k←k+1；X(k)←0；}
else k←k－1 //回溯//
}
end NQUEENS
8