也谈货郎担问题

<正> 本刊80年六期刊登的“图数方阵优选法”一文,提出了货郎担问题的一个解法,从解题的思路看,属于“穷举法”范畴。当货郎为了推销产品而访问的城镇数并不很多时,它确实是寻找最短送货路线的方法之一。可是也要看到,虽然现代的计算机的运算速度已经可以达到毫微秒(10~(-9))级,但对于许多图论问题或任何组合学上的问题,如果不考虑计算方法,很快就会发     

货郎担问题的几何解法

本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（n²/m），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数．     

用遗传算法解多货郎担(2-货郎担)问题

给出了多货郎担问题的基本定义,对2-货郎担问题进行了简单的数学描述,并对利用遗传算法解多货郎担问题提出一些基本思路。     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

求解货郎担问题的量子进化算法

货郎担问题属于NP完全问题,对它的近似求解方法主要是智能算法及线性规划,但其中的基本量子进化算法易陷于局部最优解。为此,提出一种新的量子进化算法,结合乡村货郎运输问题,对算法进行测试。结果表明,该算法在全局寻优能力及种群多样性方面均比传统算法有所改进,是求解乡村货郎担问题的一种有效算法。     

货郎担问题最优并行启发式算法

本文给出了满足三角不等式的货郎担问题的并行启发式算法，在ＳＩＭＤ ＣＲＥＶ ＰＲＡＭ并行机上该算法使用Ｏ（ｎ＾３／ｌｏｇ＾２ｎ）台处理器需Ｏ熄ｌｏｇ＾２ｎ）时间，这里ｎ是给定城市的个数，因而该并行算法是最优的。     

对“货郎担问题”的深入解析

The Traveling Salesman Problem(TSP) is one of the most difficult problems that many scholars all over the world are studying.This paper points out the disparity between the definition and the classical solution of TSP and its practical applications,and the presents a new definition of TSP and its effective algorithm conforming to practical applications,thus making TSP practically more valuable.     

调运、指派和货郎担问题的通用解法的研究——算法设计及其程序实现

本文介绍求解运输调运问题、指派问题和货郎担问题的通用方法的算法设计及其程序实现,这个通用方法就是元素判别值分配法。     

货郎担问题的几何分块算法及ChinaTSP问题的最终解决

本文提出了货郎问题后一种新的求解方法，即几何分块算法，用该方法找到了ＣｈｉａｎＴＳＰ问题的最短路径，并分析了求解中的一些策略问题。     

改进匈牙利法求解货郎担问题(TSP)

提出了一个改进匈牙利法,给出了数学推导,以Hamilton回路选独立零,并给出终止条件,通过二个例子,与C-W节约算法和几何法比较,提出的方法精度比高。     

基于Visual Prolog的TSP(货郎担)问题实现

货郎担问题是一个典型的易于描述却难以处理地NP完全问题。而Visual Prolog语言的匹配合一、递归和回溯等特点非常适合求解这类问题。本文利用Visual Prolog实现了简单的货郎担问题。     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

遗传算法和Hopfield模型求解货郎担问题的比较和分析

文章简要介绍了运用遗传算法和Hopfield网络求解货郎担问题的模型,讨论了两种算法中有代表性的实现途径,并给出了两种方法的具体算法。文中根据实验数据,着重对两种算法的性能进行了比较和分析。     

求解货郎担问题(TSP)的佳点集遗传算法

文章针对求解货郎担问题（ＴＳＰ）,给出了一种佳点集遗传算法。通过对ＣＨＮ１４４实例的仿真求解,取得了令人满意的结果,可以看出该算法不仅提高了求解的效率和精度,还有效地避免了“早熟”现象。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

Josephus问题的算法设计与应用研究

Josephus问题是组合数学的发展源头之一。关于Josephus问题的描述形式甚多。文章通过实验和分析,总结了一个通用性的描述形式,并给出了基于循环链表的算法设计。算法的数据源从文本文件中获取,增强了算法的实用性;根据数据元素值的递增顺序建立循环链表,能够有效地分类数据,使Josephus数据序列均匀分布且不重复。文章还给出了Josephus问题的若干个应用实例,包括将Josephus问题应用于通用试题库的组卷算法和找出一组数据中某个指定范围的数据序列等。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

关于网页设计与制作问题的研究

伴随信息技术的发展,各类企业单位都推出自己的网站,本文针对网页设计过程中如何做到不失主题又体现特色的问题进行研究,首先要针对企业特点明确网页设计的任务,在设计过程总要遵循一定的原则的基础上,阐述了网页设计与制作的过程。从而做到实用性与艺术性的统一。     

关于网页设计与制作问题的研究

伴随信息技术的发展,各类企业单位都推出自己的网站,本文针对网页设计过程中如何做到不失主题又体现特色的问题进行研究,首先要针对企业特点明确网页设计的任务,在设计过程总要遵循一定的原则的基础上,阐述了网页设计与制作的过程。从而做到实用性与艺术性的统一。     

几何设计约束的表示与满足问题研究

对于智能ＣＡＤ系统来说，具有解决几何设计约束的功能是重要的。本文提出了一种面向对象的几何设计约束表示方法，它可以通过两种方式来表达。文中给出了一个约束传播算法，用于解决约束满足问题。