数模的算法精讲

讲述了数模的各种算法，有优化TSP 问题是组合优化问题中最为典型的 NP 难题之一精确解算法 的时间是关于问题规模的指数函数存在指数爆炸的问题。解决 TSP 问 题我们最直观的想法就是遍历整个图找出所有的 Hamilton 回路再进行 比较、寻优。对于一个具有 n 个顶点的对称完全图而言要从 2)!1(− n 个 可能的解中找出最小解需要进行 12)!1(−− n 次比较。如果我们使用每 秒运算一亿次的计算机当 n 等于 10 的时候只需 0.0018 秒而当 n 等 于 20 的时候就需要 19 年当 n 等于 30 的时候所需时间则猛增到 15 104.1× 年这是我们所无法接受的。因此实际求解我们一般使用近似解算法。 传统的算法有动态规划法、分支限界法、最近邻法、蚁群算法、最近插 入法、双极小树生成法等。但这些算法仍有些须不足或时间性能不理 想或寻优性能不佳。在这里我们首先介绍一下蚁群算法和分支限界 法的原