旅行商问题 问题分析 带权邻接矩阵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。 搜索解空间 约束条件…

回溯法 回溯法的思想是：能进则进，进不了换，换不了退。 隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。 关键步骤是： 1. 定义解空间； 2. 确定解空间的组织结构（子集树、排列数、m叉树等）； 3. 搜索解空间。 回溯法阶梯的关键是设计有效的显约束和隐约束。 大卖场购物（0-1背包问题） 问题举例 每个物品重量w和价值v如下表所示，购物车容量为W，求不超过购物车重量的最大价值。 w[] 1 2 3 4 2 5 4 2 w[] 1 2 3 4 6 3 5 4 问题分析 解空间={x…

题目1 二维数组中的查找 题目描述 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 题目解析 其实这个题目是非常有规律的，所以才可以用复杂度更小的方法来实现。由于其每行自左向右递增，每列自上而下递增，所我们可以设置一个初始位置，让他不在(0,0)的位置，而是第一列最后一个位置，如果实际数比它大了，那就向右查找，否则向上查找。 代码 bool Find(int target…

1.为复习题5描述的类提供方法定义，并编写一个小程序来演示所有的特性。 bankacc.h #ifndef BANKACC_H_1 #define BANKACC_H_1 class Bank { char name[30]; char account[7]; double debt; public: Bank(); Bank(const char *co, const char *ac, double db = 0.0); ~Bank(); void show() const; void deposit(cons…