第6讲(局部及随机有哪些信誉好的足球投注网站策略).pptVIP

组合优化问题举例 TSP问题 从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？ 约束机器排序问题 n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。 指派问题 一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？ 组合优化问题举例 0-1背包问题 设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？ 装箱问题 如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？ SAT问题 称 判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。 组合优化问题举例 皇后问题 在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？ TSP问题 从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？ 时间复杂性函数比较-数值说明 大规模组合优化问题的求解策略 一些难以求解的组合优化问题，至今尚未找到多项式时间算法来获得问题的最优解，如旅行商问题。 实际上，在很多情况下追求最优解不一定有意义，一个满意解就可以了。如买西瓜。 求满意解的基本思想是：引入随机因素，每次运行并不能保证求得问题的最优解，但经过多次运行后，一般总能得到一个与最优解相差不太大的满意解，以放弃每次必然找到最优解的目标，来换取算法时间复杂度的降低，以适合于求解大规模的优化问题。 常见的几种邻域 一维空间中 点x1附近的一个小区间 二维空间中 点x1,y1附近的一个小区域 三维或多维空间中 邻域可定义为该点为中心的一个圆球体，即 N(x’1,…,x’n)={x1,…,xn: (x1 –x’1)2 +…+(xn –x’n)2=r} 或定义与该点的欧氏距离，即： N(x’1,…,x’n)={x1,…,xn : |(x1 –x’1)| +…+ |(xn –x’n)|=d} 旅行商问题的邻域-示例 以5城市TSP为例，可以用一个城市序列S表示一个可能解c1,c2,c3,c4 ,c5 ，其中ci表示第i个城市。 定义映射N为交换城市序列中的任意两个城市，即S中任意两个元素交换位置，这样可得到S的所有邻居，所有邻居的集合就是S的邻域。 以S=1,2,3,4,5,为例，其邻域N(S) = {2,1,3,4,5, 3,2,1,4,5, 4,2,3,1,5 ,5,2,3,4,1, 1,3,2,4,5, 1,4,3,2,5, 1,5,3,4,2, 1,2,4,3,5, 1,2,5,4,3, 1,2,3,5,4} 旅行商问题的邻域-示例 以1,2,3,4,5,交换为1,4,3,2,5后路径变化示意图如下： 旅行商问题的邻域-示例 还可以定义映射N‘为逆序交换获得S的所有邻居，即S中任意两个元素之间的城市逆序重排。 以S=1,2,3,4,5,为例，将城市2和5之间的城市逆序重排，得：1,2,4,3,5 以1,2,3,4,5,交换为1,2,4,3,5后路径变化示意图如下： 爬山算法 1, n := s; 2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS); 3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)} 4, IF h(n)h(nextn) THEN EXIT(Fail); 5, n:=nextn; 6, GO LOOP; 该算法在单峰的条件下，必能达到山顶。 求解TSP问题-过程 第1次循环 P’={从P中随机选择一个元素},设为x1=(a,c,b,d,e),则f(x1)=42， f(x1) f(xb),P=P- {x1}={ (a,d,c,b,e), (a,e,c,d,b), (a,b,d,c,e), (a,b,e,d,c), (a,b,c,e,d)} 第2次循环 P’={从P中随机选择一个元素},设为x2= (a,d,c,b,e),则f(x2)=45， f(x2) f(xb), P=P- {x2}={ (a,e,c,d,b), (a,b,d,c,e), (a,b,e,d,c), (a,b,c,e,d)} 第3次循环 P’={从P中随机选择一个元素},设为x3= (a,e,c,d,b),则f(x