加入步行的路径 并给定权值 由于每两点之间均有步行路径每次扩展都将涉及 到所有顶点复杂度增加不少 改进的办法 预处理找到两个相邻顶点之间路径的最小值, 如果它加上两个顶点的权值之后后,仍然小于 些其它的路径,就可以将其它路径删除这样至少 可以删除不少步行路径 考虑实际情况,可设定步行时间的上限
• 由于每两点之间均有步行路径,每次扩展都将涉及 到所有顶点,复杂度增加不少 • 改进的办法 – 预处理 找到两个相邻顶点之间路径的最小值, 如果它加上两个顶点的权值之后后,仍然小于一 些其它的路径,就可以将其它路径删除.这样至少 可以删除不少步行路径 – 考虑实际情况,可设定步行时间的上限. 5 6 7 a c 加入步行的路径 并给定权值 20
算法的总结 关键在于如何解决换乘的耗时 扩展节点的策略与经典算法不同 算法实际用到了分支界限法的思想 类似于回溯法,但是求解的目标不同 ·目标:找到使目标函数取极值的解
算法的总结 • 关键在于如何解决换乘的耗时 • 扩展节点的策略与经典算法不同 • 算法实际用到了分支界限法的思想 • 类似于回溯法，但是求解的目标不同。 • 目标：找到使目标函数取极值的解
分支界限法思想 ·以广度优先或以最小耗费(最大效益) 优先的方式搜索问题的解空间树 从一个点开始,每次以一定的策略扩展 些结点。每一个活结点一成为扩展 结点,就一次性产生其所有子结点,并 从活节点中移除。在产生的子结点中 导致不可行解或导致非最优解的子结点 被舍弃,其余的加入活结点表中
分支界限法思想 • 以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树 • 从一个点开始，每次以一定的策略扩展 一些结点。每一个活结点一旦成为扩展 结点，就一次性产生其所有子结点，并 从活节点中移除。在产生 的子结点中， 导致不可行解或导致非最优解的子结点 被舍弃，其余的加入活结点表中
选择扩展的节点 从活结点表中选择下一扩展结点可能有 不同的方式 ·队列式分支限界法:先入先出的原则 ·优先队列式分支限界法:选择优先级最 高的节点进行扩展 最大效益问题:最大值堆 ·最小耗费问题:最小值堆
选择扩展的节点 • 从活结点表中选择下一扩展结点可能有 不同的方式 • 队列式分支限界法：先入先出的原则 • 优先队列式分支限界法：选择优先级最 高的节点进行扩展 • 最大效益问题：最大值堆 • 最小耗费问题：最小值堆
个简单的例子 印刷电路板将布线区域划分为n×m个方 格阵列 精确的电路板布线问题要求确定连接方格 a的中点到方格b的中点的最短布线方案。 布线时电路只能沿直线或直角布线 为避免线路相交,已布线方格做上封闭标 记,其他线路布线不允许穿过封闭区域
一个简单的例子 • 印刷电路板将布线区域划分为n×m个方 格阵列 • 精确的电路板布线问题要求确定连接方格 a的中点到方格b的中点的最短布线方案。 • 布线时电路只能沿直线或直角布线。 • 为避免线路相交，已布线方格做上封闭标 记，其他线路布线不允许穿过封闭区域