基于三值光学计算机的旅行商问题的求解实现  

Solving TSP based on ternary optical computer

作　　者：沈云付[1] 樊孝领[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机应用研究》2011年第6期2184-2187,共4页Application Research of Computers

基　　金："211"工程重点建设项目

摘　　要：根据三值光计算机具有的巨并行性特点,对给定城市数的旅行商问题进行研究。首先将旅行商问题进行预处理,并转换为改进的符号数(modified signed-digit,MSD)表示形式;然后根据三值光学计算机的位数众多和MSD加法的无进位过程,建立了相应的计算方法,用自主开发的三值逻辑光处理器系统进行求解。结果表明,在数据量同样的情况下,与电子计算机相比,三值光学计算机需较少的计算步数就可以解决旅行商问题,显示出三值光学计算机潜在的优势。Through the ternary optical computer,this paper studied the traveling salesman problem with arbitrarily definite number of nodes.The traveling salesman problem was first preprocessed and transformed into the form of modified signed-digit（MSD） data format.Then based on the characteristic of giant parallelism of the ternary optical computer and the MSD addition of non-carry process,established a calculation to solve the problem using the self-developed ternary optical processor system.Experiments show that under the same amount of data,as compared with the electronic computer,ternary optical computer can solve the traveling salesman problem with less number of steps,which demonstrates the potential advantages of ternary optical computer.

关 键 词：三值光学计算机 巨并行性 改进的符号数 旅行商问题 

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