分子算法在公交网络问题中的应用  

Application of the Molecular Algorithm in Public Transport Network Problem

作　　者：张倩[1] 王振晔[1] 董亚非[1,2] 

机构地区：[1]陕西师范大学生命科学学院,西安710062 [2]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机科学》2012年第2期258-261,267,共5页Computer Science

基　　金：国家自然科学基金(60970005);陕西省自然科学基金(2007F46);陕西师范大学2008年重点项目;陕西师范大学研究生培养创新基金(2010CXS019)资助

摘　　要：分子生物计算是一门很有潜力的发展中学科。首次尝试将其用于解决公交网络问题。通过对公交网络问题的分析,巧妙地将该出行优化问题转化成一个赋权图问题,综合考虑道路长度、拥堵系数、换乘等因素,并结合自组装的思想对其进行建模。在此基础之上,以西安市局部公共交通网络图为例,给出了该分子计算模型的详细生化操作步骤,显示了分子生物计算的可行性及巨大的优越性。该算法大大降低了公交网络计算的复杂性,同时扩展了分子生物计算的研究领域。Molecular bio-computation is a developing subject with good potentiality.This is a first try to apply a public transport network into this field.Based on the analysis of transport network problems,we ingeniously transformed the optimized travel problem into a weighted graph issue.Firstly,integrating the self-assembly idea,we built a molecular bio-computational model of it,three factors were involved——the length of the road,congestion coefficient and transfer.Secondly,taking the public transport network graph of local area of Xi＇an for example,we gave a detailed description in the biochemical operating steps.It shows the feasibility and great superiority for the molecular algorithm applied in the transit network research.Based on the algorithm,the complexity of the transport network problem can be obviously reduced,also the research fields of the molecular bio-computation can be extended.

关 键 词：公交网络 最优路径 分子算法 自组装 生物操作 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]