货郎担问题java代码,货郎担问题例题

用探索（穷举）法求解货郎担问题

没明确的解答过程 路线是1-2-4-3-1

2,3,4中3到1最短

2,4中4到3短

2到4比2到其他数短

成立

类似反证

其他自己搞定吧

相关问答

Q1: 货郎担问题算法(哈密尔顿回路算法) pascal 程序

资料：

1857年，英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上著名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权汉密尔顿问题进行解决；因此，赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中，枚举法的计算量巨大，对于n个点的问题存在(n－1)!条汉密尔顿回路，当n比较大时，枚举法显然是行不通的，为此，优化专家们提出了启发式算法[1]，以期求得该问题的近似最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。其中应用比较广泛的有Clarke和Wright的C－W算法，Norback和Love的几何算法[2]，在此，称这些算法为经典启发式算法，简称经典算法，这些算法的一个共同特点就是非优化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的汉密尔顿回路进行优化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情况下都能求得最优解则尚待证明。

所谓赋权汉密尔顿回路最小化问题是指，给定n个点及n个点两两之间的距离(或权数)，求一条回路，使之经过所有的点，且经过每个点仅一次，而整条回路(也称路径或边界)的总距离(或总权数)最小。

这一问题总是可以通过枚举法求出其解的，但由于枚举法的计算量过大，达到(n－1)!的数量级，因而，不是可行的方法。由此，人们提出了启发式算法来求解问题的近似解。所谓启发式算法，一般地讲，就是发现某些最优解所具备的特征或不应具备的特征，对应有特征而言，求出含应有特征的可行解；对不应有特征而言，从解空间中剔除不应有特征的解，再从剩余空间中找一个解。因而，启发式算法可以定义为：从最优解的必要条件出发，设计一个有效算法，使之求出的解满足这些必要条件。

就一般算法的本质而言，它是提供一种规范的过程，经由该过程得出的解满足问题最优解的充分条件，即算法应该是问题最优解的充分条件的一种规范实现过程；而算法设计本身要求，算法必须给出解，因此，算法实际上还要满足最优解的必要条件，即算法可以定义为：算法是问题最优解的充分必要条件的一种规范实现过程。

启发式算法只满足了算法的必要性条件，而没有满足其充分性条件，就一般意义而言，其结果不是问题的最优解。基于这一思路，经典启发式算法的做法就是从满足必要条件的解空间中找出一个解，这就产生了一个问题：这样的解是否还可以按某种规则改进?这就涉及局部极值或重叠应用启发式算法的问题。如果存在局部极值或进一步优化的规则，那么，在已有解的基础上继续运用这些规则会极大改进算法的性能，这就是本算法的基本思路。

依据上述局部优化的算法思想，对赋权汉密尔顿最小化问题进行分析。对该问题的一般形式(包括平面和非平面)给出一条规则：最优路径上各点在插入路径时，其路径变化量最小。

这是本文给出优化算法的基础。关于该规则，用反证法可以简单地证明，即若最优路径上有某一点在插入路径时，其路径变化量不是最小，那么，至少还有一种插入法的路径变化量更少，则以路径变化量更小的插法来代替原插入方法，由此形成的回路其路径更短，而这与原路径最短的假设矛盾，所以，规则成立。

依据上面的分析，给出相应的算法。

算法：

算法设计分为两步：(1)运用经典算法求出一条汉密尔顿回路；(2)运用本文算法对该回路进行优化。在此，不讨论由经典算法找出一条回路的方法，讨论依据上面原则对已有回路进行优化的算法。

优化方法：

第0步，确定一个初始的循环起点。即以汉密尔顿回路上的某一点作为循环的起点，以该起点为当前点，转入第1步。

第1步，跨线切割形成孤立点。即在已形成的汉密尔顿回路上，以当前点为跨线的起点，按路径方向作跨线，用跨线切割中间点，使该中间点成为孤立点，而该跨线成为一条边；此时，回路的路径上不包含全部点，故非然汉密尔顿回路，转入第2步。

第2步，将孤立点重新连入路径中。按路径变化量最小原则，将被切割下来的孤立点重新连入回路中；连入之后，回路的路径中包括全部点，故又形成汉密尔顿回路，转入第3步。

第3步，如果产生了路径的变化，则以新路径取代旧路径，但以原跨线的起点为循环的新起点，也为当前点，返回第1步，继续计算；否则，走向下一点，以下一点为当前点，转入第4步。

第4步，判断一个循环是否完成，即当前点是否是循环的起点。如是，则算法结束；如不是，则转入第1步。(算法描述完毕)

当算法结束时，回路上的每一个点相对于其它点都是最优，即回路达到其局部极值。

对平面问题，为简化计算，当跨线为内连线时，不作变动，向下一点走；当跨线为外连线时，切割其中间点，然后再将被切掉的中间点重新连入路径中。

概念：

跨线：在回路中，连线两个不相邻点，且中间只有一个点，这个中间点是该连线的起点和终点的相邻点，该连线称跨线。例如，在回路A－B－C－D－E－F－G－A中，A与B、B与C等都是相邻点，则连线AC连接了不相邻点A和C，且其中间只有一个点B，而点B是A的相邻点，也是C的相邻点，故连线AC是跨线。

边：两个相邻点之间的连线，如上面A与B的连线，B与C的连线都是边。

路径变化量：将某一点连入路径中，就是要把该点与路径中的某一条边的起点和终点相连，以这两条新的边取代原来的边；这样，新的两条边长(权重)之和与原来边长(权重)的差就是将该连入路径后引入路径长(总权重)的变化量，称路径变化量。例如，将点D插入回路A－B－C－E－F－G－A的边EF中，实际上就是将ED和DF相连，用新的边ED和DF取代原来的边EF，由此引起的路径变化量，即回路A－B－C－E－F－G－A与回路A－B－C－E－D－F－G－A的总长度(总权重)之差等于两条新边的长度(权重)之和减原来边的边长(权重)，即等于ED＋DF－EF。

路径变化量最小原则：从上面路径变化量的定义可以看出，将一个点插入路径中，可以有多条边供选择，而插入不同的边，所引起的路径变化量各不相同；但其中有一条边，当将要插入的点插入该边时，其路径的变化量最小，则选择将该点插入该边。

几点说明和补充：

(1)某些经典启发式算法的结果未进行必要的优化，这在局部优化规则可行的条件存在着解空间的浪费，对这些结果进行优化可以极大的改进算法的性能，本算法正是这一思想的体现。

(2)本文未对赋权汉密尔顿回路最小化问题的解空间的极值数进行论证，只是给出了以经典算法为起点，求其局部极值的算法；因而，算法的结果未必总是问题的最优解。只有当解空间的极值点唯一时，才能保证本算法的结果是全局最优解；所以，本算法的解是否总能保证是全局最优解，尚需论证问题的解空间。

(3)即使问题的解空间有多个极值点，但是，如果原经典算法的解进入全局最优解的领域，本算法的解也是最优解。

(4)上面计算中，当跨线为外连线时切割点，为内连线时不切割点，减少了计算量。由经典几何算法的规则[2]可知，任意内连线所引起的路径变化均可由外连线完成，故，对平面的赋权汉密尔顿问题只选择外连线儿为切割线是合理的；而当问题是非平面问题时，则不存在连线内外的概念，所有跨线均切割中间点，均需重做计算和连入。

(5)本算法是半多项式算法，即一个进步的计算量是多项式的，但算法的进步有多少与初始解有关，因而不可预知。一个进步指找到一个比当前解更优的解，本算法中，一个进步的计算量不超过n2。若设定进步数的上限为m次，则：或者极大改进了结果，计算量为(m×n2)；或者在小于(m×n2)的计算内达到局部极值而对原结果有所改进；或者因初始回路即为极值而只做了1个循环，计算量为n2。因计算路径是优化轨迹，即每一次循环至少有一个进步；所以，算法的收敛速度很快。

(6)本算法是以有向图给出的，因而，在计算路径变化量时运用了严格的符号顺序，其方向为：左边是线段的起点，右边是线段的终点，例如，线A－B表示A为起点而B为终点。但算法也适用于无向图，所给实例即为无向图。

(7)算法的结束条件。算法过程自动保证了算法不会在两个不同路径长度的图之间来回计算，当存在相同最小路径变化量的不同路径时，算法选取首次得到的路径为最优(旧图优先)，从而保证了算法不会产生抖动问题，即不会没有终点。

(8)在极值点有多条路径时，在极值点会出现路径长度相同但路径不同的情况；而上述算法结束时，优化路径集中只有一条路径。如果对上面算法略作修改，当存在相同最小路径变化量的不同路径时，记录所有这些路径，从这些路径中剔除优化路径集中已存在的路径，剩余路径补进优化路径集中；以此算法对上述算法的结果进行重新计算，当优化路径集中的全部路径计算完毕，而没有路径数目的增长时，就得到全部的极点解。

Q2: 求货郎担问题的matlab算法

货郎担问题有很多解法，模拟退火，遗传算法，动态规划等。

基于matlab TSP问题遗传算法的实现

%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序

%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，

%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定

%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大

%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0

%R为最短路径,Rlength为路径长度

function [R,Rlength]=geneticTSP(D,n,C,m,alpha)

[N,NN]=size(D);

farm=zeros(n,N);%用于存储种群

for i=1:n

farm(i,:)=randperm(N);%随机生成初始种群

end

R=farm(1,:);%存储最优种群

len=zeros(n,1);%存储路径长度

fitness=zeros(n,1);%存储归一化适应值

counter=0;

while counterc

for i=1:n

len(i,1)=myLength(D,farm(i,:));%计算路径长度

end

maxlen=max(len);

minlen=min(len);

fitness=fit(len,m,maxlen,minlen);%计算归一化适应值

rr=find(len==minlen);

R=farm(rr(1,1),:);%更新最短路径

FARM=farm;%优胜劣汰，nn记录了复制的个数

nn=0;

for i=1:n

if fitness(i,1)=alpha*rand

nn=nn+1;

FARM(nn,:)=farm(i,:);

end

end

FARM=FARM(1:nn,:);

[aa,bb]=size(FARM);%交叉和变异

while aan

if nn=2

nnper=randperm(2);

else

nnper=randperm(nn);

end

A=FARM(nnper(1),:);

B=FARM(nnper(2),:);

[A,B]=intercross(A,B);

FARM=[FARM;A;B];

[aa,bb]=size(FARM);

end

if aan

FARM=FARM(1:n,:);%保持种群规模为n

end

farm=FARM;

clear FARM

counter=counter+1

end

Rlength=myLength(D,R);

function [a,b]=intercross(a,b)

L=length(a);

if L=10%确定交叉宽度

W=1;

elseif ((L/10)-floor(L/10))=randL10

W=ceil(L/10);

else

W