《数模常用算法简介》.ppt

该【《数模常用算法简介》 】是由【相惜】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【《数模常用算法简介》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数模常用算法简介精选课件根本算法穷举法与直接法顾名思义,就是从所有可行解中筛选最优解的方法。 该方法最大的优点是取得的解一定是全局最优解,而且可以筛选出多个等价的全局最优解。需要注意的两个方面:能否在理论上决定所求解问题的全部可行解集。亦即所有可行解是否可以用一致的算法列举出来。在运算规模上是否能够接受,很多问题用穷举的复杂度上界都是阶数的指数函数,对于这种问题一定要慎用穷举法。精选课件根本算法递归与分治策略分治法的根本思想是将一个规模为n的问题分解为k个规模小于n的较小的子问题,这些子问题相互独立且与原问题相同。递归地求解子问题,然后用各子问题的解合并到原问题的解。核心在于将原问题分解,如果可以做到,那么问题的复杂度将比用穷举法下降很多。如果是这样的问题,不妨在论文里多写点算法相关的东西。例子:快速排序、合并排序、FFT、汉诺塔、矩阵相乘精选课件根本算法贪婪算法顾名思义,贪心算法总是做出在当前看来最好的选择。因此,他做出的选择往往只是在某种意义下〔即贪婪准那么〕的局部最优选择。对于很多问题贪婪算法得到的局部最优解就是全局最优解。举例:Dijkstra、Prim、Kruskal、Huffman编码。即便得到的仅仅是局部最优,通常也是很好的近似解。NP类问题的首选求解方法。核心问题:构造合理的贪婪准那么精选课件根本算法动态规划算法与分治法类似,其根本思想也是将带求解问题分解成假设干个子问题,先求解子问题,再从子问题得到原问题的解,与分治法不同的是,适用该方法的问题,经分解后的子问题往往不是相互独立的。注意:并不是动态规划问题才可以用动态规划算法解!举例:01背包问题核心问题:找到最优子结构精选课件根本算法回溯法有“通用的解题法〞之称。在包含问题的所有解空间书中按照深度优先的策略,从根节点出发搜索解空间树。配以合理的定界估计,可有效缩小全局最优解可能存在的解空间。优点:通用,易实现,一定找到全局最优解,即便中止能得到近似解。缺点:算法的执行时间很大程度取决于找到的头几个可行解。最糟糕的情况下与穷举法复杂度相同。核心问题:定界函数以及解空间的划分精选课件根本算法分支定界法与回溯法类似,但分支定界法通常得到的第一个可行解就是全局最优解。搜索策略为广度&最优存在可能优先。优点:不依赖初始解,可求得全局最优。缺点:最糟糕的情况下时间及空间复杂度都非常大,此外,如果中止算法,你啥也得不到。核心问题:对可行解的“定界〞估计函数精选课件根本算法概率算法通常也称之为计算机模拟。构造一个概率问题,让某个统计量的数学期望等于所求问题的解。精选课件根本算法线性规划与网络流这个大家都是行家精选课件现代算法模拟退火法〔不推荐〕禁忌搜索遗传算法〔推荐〕优点:任何优化问题都可以用之求解缺点:没有统一的形式,对于每一类问题都几乎得从头构造生成、变异、交叉算法。当最优解在解空间的边界附近时比较头疼。人工神经网络工程上应用已经很普遍蚁群算法〔不了解〕精选课件