最大收益问题 问题分析 经过分析，又根据最大流最小割定理，最大流的流值等于最小割容量。即：实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、 算法设计 构建网络。根据输入的数据，添加源点和汇点，从源点s到每个实验项目E…

配对方案问题 问题分析 先了解几个概念。 二分图：又称二部图。设G=(V,E)是一个无向图，如果结点集V客分割为两个互不相交的子集（V1,V2），并且图中的每条边（i,j）所关联的两个结点i和j分别属于这两个不同的结点集（i∈V1，j∈V2…

优化扩展——重贴标签算法ISAP 首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。 贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1…

线性规划问题 遇到一个线性规划问题，该如何解决呢？ 1. 确定决策变量。 2. 确定目标函数。 3. 找出约束条件。 4. 求最优解。 一般线性规划问题可以表示为如下形式。 约束条件为： 变量满足约束条件的一组值成为线性规划问题的一个可行解…

旅行商问题 问题分析 带权邻接矩阵g[][]如下所示，空表示为无穷，即没有路径。 15 30 5 15 6 12 30 6 3 5 12 3 算法设计 可以使用优先队列分支限界法，加快搜索速度。 设置优先级：当前已走过的城市所有的路径长度c…

广度优先 广度优先搜索，其实就是层次遍历，程序采用队列来实现。 算法思想 从根开始，常以BF或以最小耗费（即最大收益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表，接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有…

最优加工顺序 问题描述 现在有3个机器零件{J1,J2,J3}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的…

着色问题 问题分析 假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。 算法设计 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,…

回溯法 回溯法的思想是：能进则进，进不了换，换不了退。 隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。 关键步骤是： 1. 定义解空间； 2. 确定解空间的组织结构（子集树、排列数、m叉树等）； 3. 搜索…