古蔺网站建设,个人备案的网站可以做商城,网站建设步骤图片素材,专业制作外贸网站的公司文章目录八数码难题普通BFS算法全局择优算法#xff08;A算法#xff0c;启发式搜索算法#xff09;单源最短路径问题装载问题算法思想#xff1a;队列式分支限界法优先队列式分支限界法布线问题最大团问题批处理作业调度问题分支限界法与回溯法的区别#xff1a; #x…
文章目录八数码难题普通BFS算法全局择优算法A算法启发式搜索算法单源最短路径问题装载问题算法思想队列式分支限界法优先队列式分支限界法布线问题最大团问题批处理作业调度问题分支限界法与回溯法的区别 1求解目标不同回溯法的求解目标是找出解空间树中满足约束条件的所有解而分支限界法的求解目标则是找出满足约束条件的一个解或是在满足约束条件的解中找出在某种意义下的最优解。 2搜索方式的不同回溯法以深度优先的方式搜索解空间树而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
BFS框架queue.add(起点)
while(队列不为空)
{ 取出队首点if(如果达到目标) 结束 for(当前结点可拓展选择) {if (判重检测通过)queue.add(新扩展结点)}
}常见的两种分支限界法 1队列式(FIFO)分支限界法 按照队列先进先出FIFO原则选取下一个节点为扩展节点。 2优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 八数码难题
在 3*3 的方格棋盘上分别放置了标有数字1、2、3、4、5、6、7、8的八张牌初始状态S0目标状态Sg。
可以使用的操作有空格左移空格上移空格右移空格下移即只允许把位于空格左、上、右、下方的牌移入空格寻找从初始状态到目标状态的移动棋子步数最少的解路径。普通BFS算法
1 从初始布局出发先把移动一步后的布局全部找出检查是否有目标布局若有一定是最少移动步骤 2 若没有再从这些一步的布局出发找到移动两步后的所有布局再检查是否有目标布局。若有一定是最少移动步骤如此继续直到找到目标布局。 3 由于是按移动步数从少到多产生布局的所以找到的第一个目标布局一定是最少步骤的。
全局择优算法A算法启发式搜索算法
设估价函数为: fndnWn 其中d(n)表示节点 n 在搜索树中的深度 w(n)表示节点 n 中“不在位”的数码个数。
一般来说某节点中的“不在位”的数码个数越多说明它离目标节点越远。 对初始节点 S0由于 dS0 0WS0) 3 因此有 fS0033
单源最短路径问题
问题描述在下图所给的有向图G中每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 算法思想 算法从图G的源顶点s和空优先队列开始。结点s被扩展后它的儿子结点被依次插入堆中。 此后算法从极小堆中取出具有最小当前路长的结点作为当前扩展结点并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达且从源出发途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。
剪枝策略 在算法扩展结点的过程中一旦发现一个结点的下界不小于当前找到的最短路长则算法剪去以该结点为根的子树。在算法中利用结点间的控制关系进行剪枝。从源顶点s出发2条不同路径到达图G的同一顶点。由于两条路径的路长不同因此可以将路长长的路径所对应的树中的结点为根的子树剪去。
装载问题
问题描述有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船其中集装箱i的重量为Wi且满足下列条件装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有找出一种装载方案。 实质就是要求第1艘船的最优装载。 算法思想队列式分支限界法
在算法的while循环中首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点由于队列中每一层结点之后都有一个尾部标记-1故在取队首元素时活结点队列一定不空。当取出的元素是-1时再判断当前队列是否为空。如果队列非空则将尾部标记-1加入活结点队列算法开始处理下一层的活结点。
while (true) {// 检查左儿子结点if (Ew w[i] c) // x[i] 1Ew表示当前扩展结点相应的重量EnQueue(Q, Ew w[i], bestw, i, n); //将活结点加入活结点队列// 右儿子结点总是可行的直接加入EnQueue(Q, Ew, bestw, i, n); // x[i] 0Q.Delete(Ew); // 取下一扩展结点if (Ew -1) { // 同层结点尾部if (Q.IsEmpty()) return bestw;Q.Add(-1); // 同层结点尾部标志Q.Delete(Ew); // 取下一扩展结点i;} // 进入下一层 } }
算法的改进 节点的左子树表示将此集装箱装上船右子树表示不将此集装箱装上船。 设bestw是当前最优解ew是当前扩展结点所相应的重量r是剩余集装箱的重量。则当ewrbestw时可将其右子树剪去因为该子树不可能产生更优解。 另外为了确保右子树成功剪枝应该在算法每一次进入左子树的时候更新bestw的值。
算法的改进// 检查左儿子结点Type wt Ew w[i]; // 左儿子结点的重量if (wt c) { // 可行结点if (wt bestw) bestw wt;// 加入活结点队列if (i n) Q.Add(wt);
}
// 检查右儿子结点if (Ew r bestw i n)Q.Add(Ew); // 可能含最优解Q.Delete(Ew); // 取下一扩展结点
构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解算法必须存储相应子集树中从活结点到根结点的路径。为此目的可在每个结点处设置指向其父结点的指针并设置左、右儿子标志。
class QNode{ QNode *parent; // 指向父结点的指针bool LChild; // 左儿子标志Type weight; // 结点所相应的载重量
}找到最优值后可以根据parent回溯到根节点找到最优解。// 构造当前最优解
for (int j n - 1; j 0; j--) {bestx[j] bestE-LChild; //被选中的集装箱 bestE bestE-parent; //回溯到该路径中的上层结点
}
优先队列式分支限界法
算法思想 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中一旦有一个叶结点成为当前扩展结点则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
布线问题 算法思想队列式分支限界法 求解方法 1起始位置a第一个扩展 2依次考虑距a距离为1、2、3、…、的方格并作标记并存入活结点队列 3从活结点队列取结点扩展一直搜索到目标方格b或活结点队列为空时为止。 二维数组 grid[i][j]:表示方格阵列 初始时 grid[i][j] 0该方格允许布线 grid[i][j] 1该方格被封锁不允许布线 边界处理四周用方格阵列围起来作为处理的边界。
for (int i 0; i m 1; i) { grid[0][i] grid[n 1][i] 1; } //顶部和底部
for (int i 0; i n 1; i) { grid[i][0] grid[i][m 1] 1; } //左翼和右翼
方格的方位offset沿四个方向的移动分别记为offset[0]~offset[3]Position offset[4]; //offset是四个移动方向的相对位移矩阵
offset[0].row 0; offset[0].col 1; // 右
offset[1].row 1; offset[1].col 0; // 下
offset[2].row 0; offset[2].col -1; // 左
offset[3].row -1; offset[3].col 0; // 上
算法将起始距离标记为2因0,1用于表示状态
grid[start.row][start.col] 2; //起始点距离为2
here.row start.row; // here为正在布线的方格初始值为start。
here.col start.col;
do { // 标记可达相邻方格for (int i 0; i NumOfNbrs; i){ // NumOfNbrs为相邻方格数nbr.row here.row offset[i].row; // here是正在走线的方格nbr.col here.col offset[i].col; nbr是可考虑走线方格if (grid[nbr.row][nbr.col] 0) { // 该方格未标记grid[nbr.row][nbr.col] grid[here.row][here.col] 1;// grid[][]中记录该方格距离起始方格距离if ((nbr.row finish.row) (nbr.col finish.col)) break; // 完成布线Q.Add(nbr);} //队列中加入新的扩展结点}
}找到目标位置后可以通过回溯方法找到这条最短路径。
构造最短路径 从终点finish出发开始向起始方格方向回溯。 每次向标记距离比当前方格标记距离少1的相邻方格移动直至到达起始方格时为止。搜索时比较相邻4个方格的标号。
最大团问题
给定无向图G(VE)。如果U∈V且对任意uv∈U有(uv)∈E则称U是G的完全子图。 G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 上界函数
用变量cliqueSize表示与该结点相应的团的顶点数
level表示结点在子集空间树中所处的层次
用cliqueSize n-level1作为顶点数上界upperSize的值。
在此优先队列式分支限界法中upperSize实际上也是优先队列中元素的优先级。
算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。算法思想
子集树的根结点是初始扩展结点对于这个特殊的扩展结点其cliqueSize的值为0。 算法在扩展内部结点时首先考察其左儿子结点。在左儿子结点处将顶点i加入到当前团中并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连则相应的左儿子结点是可行结点将它加入到子集树中并插入活结点优先队列否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时右子树中可能含有最优解此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n1层结点)成为当前扩展结点。批处理作业调度问题
给定n个作业的集合J{J1,J2,…,Jn}。每一个作业Ji都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理然后再由机器2处理。 作业Ji需要机器j的处理时间为tjii1,2,…,nj1,2。 对于一个确定的作业调度设是Fji是作业i在机器j上完成处理的时间。 则所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业制定最佳作业调度方案使其完成时间和达到最小。
