配对方案问题 问题分析 先了解几个概念。 二分图：又称二部图。设G=(V,E)是一个无向图，如果结点集V客分割为两个互不相交的子集（V1,V2），并且图中的每条边（i,j）所关联的两个结点i和j分别属于这两个不同的结点集（i∈V1，j∈V2），则称图G是一个二分图。 匹配：在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共结点。 最大匹配：一个图所有匹配中，边数最多的匹配，成为这个图的最大匹配。 最佳推销员配对方案要求两个推销员男女搭配，相当于男女推销员形成了两个不相交的集合，可以配合工作的男女推销员有连线…

优化扩展——重贴标签算法ISAP 首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。 贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进。我们找到了1-2-4-6。 我们再次从源点开始搜索，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进，h(1)=3,h(2)=2，走到这里无法走到4号结点，因为没有邻接边，3号结点不近没有邻接边，而且高度…

线性规划问题 遇到一个线性规划问题，该如何解决呢？ 1. 确定决策变量。 2. 确定目标函数。 3. 找出约束条件。 4. 求最优解。 一般线性规划问题可以表示为如下形式。 约束条件为： 变量满足约束条件的一组值成为线性规划问题的一个可行解。 所有可行解构成的集合成为线性规划的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值成最优值。 线性规划解的情况： - 有唯一最优解。 - 有无数多个最优解。 - 没有最优解。 线性规划的标准型 标准型如下： 四个要求： 目标函数为最大值（即为max）…

旅行商问题 问题分析 带权邻接矩阵g[][]如下所示，空表示为无穷，即没有路径。 15 30 5 15 6 12 30 6 3 5 12 3 算法设计 可以使用优先队列分支限界法，加快搜索速度。 设置优先级：当前已走过的城市所有的路径长度cl。cl越小，优先级越高。 从根节点开始，以广度优先的方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有的孩子结点，判断孩子结点是否满足约束条件和限界条件，如果满足，将其加入到队列中，反之，舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时…

广度优先 广度优先搜索，其实就是层次遍历，程序采用队列来实现。 算法思想 从根开始，常以BF或以最小耗费（即最大收益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表，接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃哪些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，直到找到所需的解或活结点表为空时为止。每一个活结点最多只有一次机会成为扩展结点。 算法步骤 算法解题步骤为…

最优加工顺序 问题描述 现在有3个机器零件{J1,J2,J3}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？ 问题分析 我们通过分析可以发现，第一台机器可以连续加工，而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。 实际上就是找到n个机器零件的一个排列，使总的加工时间最短。 算法设计 定义问题的解空间。解的形式为n元组：{x1,x2,.…

着色问题 问题分析 假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。 算法设计 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,x2,...,xi,...,xn}，每个分量取值为1,2,3,...,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x1,x2,...,xi,...,xn}，其中显约束为xi=1,2,...,m。 确定解空间的组织结构：一颗满m叉树，树的深度为n。 搜索解空间 约束条件…