多边形序列的最短路径算法

给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q,近似地计算一条最短路径使得它开始于p点,然后按指定的次序访问每个多边形,最后终止于q点.如果多边形是两两不相交且是非凸的,那么此问题至今还没有算法解.应用一种R算法,给出复杂性为κ(ε).O(n)的一种近似算法,这里n是给定多边形的顶点总数,函数κ(ε)定义为L0与L的差与ε的商,其中L0是初始路径长度,L是最优路径长度,ε是计算精确度.给定的R算法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为κ(ε).O(k),这里k是含有所给定的障碍物的堆的层数.

城市物资配送路径寻优的算法比较

本文围绕物资运送至城市到达站后选择何种路线对配送点进行配送的问题展开讨论.首先, 在平面直角坐标系中, 确定配送点的位置坐标, 然后通过建立最短巡回径路模型, 设计遗传算法与蚁群算法分别对数值实例进行求解, 得到最短巡回径路, 最后比较这两种算法对寻求最短巡回径路问题的求解质量与收敛速度.