第四篇 如何用随机算法求解组合优化问题（六） 清华大学计算机系 马少平 第六节：模拟退火算法的参数选择 小明：艾博士，从您的介绍看，参数选择对于模拟退火算法是否能找到最优解起关键的作用，如何合理地设置模拟退火算法的参数呢？ 艾博士：接下来我们就介绍模拟退火算法中一些参数的选择原则。 从上面的分析我们
Published on 2025-03-08
第四篇 如何用随机算法求解组合优化问题（五） 清华大学计算机系 马少平 第五节：模拟退火算法 小明：如何利用退火过程的这些现象，改进局部搜索算法呢？ 艾博士：在退火过程中，遇到一个高内能状态时，会以一定的概率转移到该状态，相当于在局部搜索中以一定的概率接受差解，这正是解决局部搜索算法中存在局部最优值
Published on 2025-03-08
第四篇 如何用随机算法求解组合优化问题（四） 清华大学计算机系 马少平 第四节：退火过程及分析 小明：刚才您提到模拟退火算法，听起来这个算法怎么还和物理有关呢？ 艾博士：模拟退火算法是为了解决局部搜索算法存在的问题,受物理中金属退火现象的启发而提出的一个随机算法。作为求解复杂组合优化问题的一种有效的
Published on 2025-03-08
第四篇 如何用随机算法求解组合优化问题（三） 清华大学计算机系 马少平 第三节：局部搜索算法存在的问题 小明：请问艾博士，局部搜索算法存在哪些问题呢？ 艾博士：局部搜索算法主要的问题是不能保证找到全局最优解，当待求解问题具有多个极值点时，该问题更加突出。下面我们具体分析一下都与哪些具体的因素有关。
Published on 2025-03-08
第四篇 如何用随机算法求解组合优化问题（二） 清华大学计算机系 马少平 第二节：局部搜索算法 艾博士：在讲解求解组合优化问题的随机算法之前，我们先从局部搜索算法开始讲起。 在第三篇中我们讲解过寻找最佳路径的A*算法。A*算法寻找的是从初始位置a到达目标位置b的最佳路径，也就是说我们知道目标位置，也知
Published on 2025-03-08
第四篇 如何用随机算法求解组合优化问题（一） 清华大学计算机系 马少平 艾博士导读 在实际问题中经常遇到求解给定约束条件下的最佳解问题，当可能解的数量是有限个时这类优化问题被称为组合优化问题。由于组合优化问题可能解的数量是有限个的，当问题规模不大时，可以通过穷举的方法求解其最优解。但是由于组合优化问
Published on 2025-03-08
第三篇 计算机是如何找到最优路径的（九） 清华大学计算机系 马少平 第九节：总结 最后，在艾博士的建议下，小明对本篇内容做了一个总结： 首先介绍了路径搜索问题的基本概念，以如何去香山举例说明了什么是路径搜索问题，很多问题也可以转化为路径搜索问题求解，比如八数码问题。 介绍了什么是宽度优先搜索算法，在
Published on 2025-03-08
第三篇 计算机是如何找到最优路径的（八） 清华大学计算机系 马少平 第八节：拼音输入法问题 艾博士：就如同前面曾经提到过的，最短路径问题不只是单纯的可以求解狭义的路径问题，很多问题可以转化为最短路径问题。比如拼音输入法问题。 小明：什么是拼音输入法问题？拼音输入法与最短路径问题又是什么关系？ 艾博士
Published on 2025-03-08
第三篇 计算机是如何找到最优路径的（七） 清华大学计算机系 马少平 第七节：动态规划与Viterbi算法 艾博士：动态规划是求解决策过程最优化的一种方法，Viterbi算法是其中一种常用的算法，是针对篱笆型有向图最短路径问题而提出的一种有效方法。从理论上来说，Viterbi算法与h=0时的A*算法是
Published on 2025-03-08
第三篇 计算机是如何找到最优路径的（六） 清华大学计算机系 马少平 第六节：迭代加深式搜索算法 小明：深度优先搜索算法虽然比较节省内存，但是不能保证找到最优解，能找到最优解的宽度优先搜索算法、A*算法等占用空间又比较大，如果需要找到最优解，空间又不够用时怎么办呢？ 艾博士：一种解决办法就是将深度优先
Published on 2025-03-07
Published on 2025-03-07
第三篇 计算机是如何找到最优路径的（三） 清华大学计算机系 马少平 第三节：迪杰斯特拉算法 小明：在单位代价下，宽度优先搜索算法可以找到代价最小的路径，但是很多问题并不是单位代价的。比如说对于八数码问题，如果移动将牌的代价为将牌的数码，如数码为5的将牌移动一次的代价为5，每个将牌的数码不一样，移动的
Published on 2025-03-07
