局域搜索与随机搜索,概要,爬山法随机搜索模拟退火法局域射线搜索遗传算法,搜索问题,已知：一个状态（或构形）集：S=X1,XM,一个评估每个状态的函数：Eval(X).求解：寻找全域极值：寻找X*使得Eval(X*)比所有其它Eval(Xi)都更大，Xi是所有可能的值。,实例,超大规模集成电路（VLSI）布局图：X=组件放置+连接路由Eval=组件间距离+没用的组件%+路由长度,放置铺设安排信道路由封装,实例,调度：已知m个机器，n个任务X=给机器的任务安排Eval=这n个任务完成时间的极小化其它：车辆路由、设计、处理排序、,任务,机器,时间,挑战性,感兴趣的问题：构形集太大，不能显式列举。计算Eval(.)可能很昂贵。没有用来寻找Eval(.)极大值的有效算法。对于要解决的问题，Eval(.)值相似的解被认为是等同的。不关心怎样得到X*，仅关心对X*构形的描述。这是与以前介绍的搜索问题的一个关键不同。,实例：旅行推销商问题（TSP）,寻找一个经过每个结点一次，且长度最小的旅行路线。,Eval(X1)Eval(X2),X1=1,2,5,3,6,7,4,X2=1,
