基于矩阵的公交查询高效算法

引入最小乘车次数矩阵Q,直达信息矩阵,直达信息转置矩阵,充分利用矩阵Q进行宏观的判断,用后两个矩阵进行精细的查找,并设计寻找和组装最优方案的算法,进而在最小换乘算法的基础上设计了高效公交查询算法。该算法不仅缩短了查询时间,且使查询结果更加人性化,可给出最少换乘次数为3的出行线路查询结果。     

XML在跨网络的异构数据交换中的应用

在分布式异构环境下实现异构数据的交换,是当前研究的热点问题,并已提出了多种跨网络数据交换实现技术。但当前技术运用于松散耦合,跨地域的分布环境均存在这样或那样的问题,共有的问题主要包括耦合度大、成本高、实施复杂等。XML和Web服务（Web Servcies）技术的出现带来了新的实现方法。XML作为独立格式是数据交换的理想介质。而Web服务提供了简单、廉价适用的信息交换机制。本文给出了XML在跨网络的议购数据交换中的应用。     

旅行商问题的较优可行解的搜索算法的设计

利用问题本身的特点和相关的已有结论,结合最近邻法和深度优先搜索算法设计了产生旅行商问题较优可行解的方法.首先,将与每个城市关联的城市由近到远排序,并将城市之间距离较远的边删除.然后选择一个城市作为出发地,按排序利用深度优先搜索算法在有限步内搜索可行解.若搜索到多个可行解,从中选择较优的作为以该城市为出发地的可行解;否则,重新选择出发地开始新的搜索.对经典的st70、a280问题依次将每个城市作为出发地进行实验,该方法产生的可行解的性能明显优于随机搜索算法,但仍不及最近邻法.     

旅行商问题的近似求解算法

在最近邻法、k-变换策略和贪心算法的基础上,尝试设计效率较高的产生旅行商问题较优可行解的方法。将3变换邻域分成两种结构(称为3_1和3_2变换邻域)考虑,设计以下算法:利用最近邻法产生初始当前最优解;然后依次在当前最优解的3_2、3_1、2变换邻域中寻找更优的局部最优解成为当前最优解,直到结果没有改进。利用算法对一些经典的实例进行实验,依次将每个城市作为出发地,在多项式时间O(n4)得到的最优解与给定的最优解相对误差在1%内。