按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
∞
634
0
∞
412
∞
4
2
…2
0
…1
φ
φ
16
∞
21
05
∞
10
5
∞
→
0
…1
154
∞
6
043
∞
5
43
∞
φ
5
0
…4
7545
∞
3101
∞
31
∞
0
。
。1
得不考虑环路下的最优方案：
1→2，2→4，4→1，3→5，5→3
所走总距离为：
1＋3＋1＋1＋4=10
可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。
第三步 出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的
各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。
本例中，出现两个环路，1→2→4→1和3→5→3，打开节点数少的环路，分别令
d（3；5）=∝和d（5；3）=∝求解。
（1）当d（3；5）=∝时；用匈牙利法求解
0
φ
∞
1743
∞
0632
∞
62
。
。
。
。
。
。
…1
…2
…1
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
→
。
。
。
。
。
。。
φ
φ
2
∞
634
0
∞
412
∞
4
0
φ
16
∞
2
∞
05
∞
1
∞
5
∞
∞
→
0
…1
…4
154
∞
6
043
∞
5
43
∞
φ
5
∞
0
7545
∞
3101
∞
31
0
。1 。
2
可得无环路的最优方案： 5→3→4→1→2→5
12…9
所走总距离为： 1＋4＋2＋1＋4=12
（2）当d（5；3）=∝时；用匈牙利法求解
。
∞17 4 3
2∞6 3 4
1 6∞2 1
1 5 4∞6
7 5∞5∞
。
…1
。
∞0 6 3 2
0∞4 1 2
0 5∞1 0
0 4 3∞5
2 0∞0∞
。
。
0
332
。
∞
。。。。。
。。。。。
。。。。。
。。。。。
112
∞
0
…2
…1 →
…1
41
∞
0
→
4
0
5
∞
…5
。。。。。0。
。
3
得路线： 1→2；2→1；3→5；4→3；5→4
总距离： 1＋2＋1＋4＋5=13
可以看到：
20
∞
∞
上述方案出现环路1→2→1和3→5→4→3；如果打开环路求解；其总距离一定不小于13；而已
经得到总距离为12的路线；故不必再作计算；
因此得上述旅行商的最优路线为：5→3→4→1→2→5；总距离为12。
12。2。4 旅行商问题的神经网络求解
虽然可以应用匈牙利算法求解旅行商问题，但是该方法需要进行多次试探，只适用于
小规模的问题，而随着距离矩阵维数的增加，求解的时间将大量增长，求解的复杂度也急
剧增加，该方法变得不再适用，此时可采用人工智能的方法——神经网络方法进行求解。
1。连续Hopfield神经网络模型
连续Hopfield神经网络模型如图12…1所示。第i个神经元的输入为ui ，输出状态为vi；
运算放大器模拟神经元的转移函数g（其中g为sigmoid函数），跨导T ij模拟神经元之间互连的
突触特性，电容c i 及电阻R i用来模拟生物神经元的输出时间常数。设有n个神经元互连，则
可用下述非线性微分方程描述：
（a）Hopfield神经元
。。。。。
。。。。。
φ
φ
12…10
（b）Hopfield神经网络
图12…1 连续时间神经网络模型
n
。
dui
（t） ui
（t）
。ci
=ΣTijv
j
（t） 。＋
Ii
。 dt =1 Ri
（12。3）
。v
（t） =
g（u ）（i）
。 ii
对式（12。3）可以定义系统的能量函数为：
11 v
E =。Σ（n） Σ（n） Σ（n） Σ（n） i
（v）dv
（12。4）
2 i
j
iiR11111i
∫
==
。
==
＋。iijiijgvITvv0
可以证明，对于该能量函数，恒有
dE≤
0 ，即当t→∞，网络达到稳态。显然应用网
dt
络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成
（12。4）式的形式，然后应用式（12。3）运算到网络收敛即可。通常在用Hopfield神经网络求
解实际问题时，一般忽略能量式中的积分项，将能量函数简化为下式（12。5），以便目标函
数的映射。
E =。 1 ΣΣn（n） Tijviv
j
。Σ（n） viIi
（12。5）
2 i=1 j=1 i=1
2。神经网络求解旅行商问题
对于n个用户的TSP问题，任何一个用户在最终访问路径上的访问次序可用一个n维向量
表示，因此每一个用户可用n个神经元表示。下面仍以例12…3为例说明，如果用户1第3个被
访问，则表示为00100，即第三个神经元输出为1，其余为0。为了表示n个用户，可简单地
用n╳n换位矩阵表示，如表12…14所示。
表 12…14 换位矩阵
用户
次序 1 2 3 4 5
1 0 0 1 0 0
2 0 1 0 0 0
3 1 0 0 0 0
4 0 0 0 1 0
5 0 0 0 0 1
上述换位矩阵表示巡回线路为：3→2→1→4→5
巡回距离为：distance=d（3；2）＋d（2；1）＋d（1；4）＋d（4；5）
12…11
显然，一条换位距阵可表示一条有效路径，如果要构成一条有效的最短巡回路线，必然要求满足下列条件：
（1）换位矩阵中每行只能有一个为“1”； （2）换位矩阵中每列只能有一个为“1”； （3）换位矩阵中元素“1”之和应为n； （4）所构造的函数的极小值对应。 ΣΣΣΣΣΣΣΣE（。）＋＋vvvvvn=（n） （n） （n） （n） xixjxiyixi2221i1jii111i1≠≠x===x=yxx==（n） nΣΣΣd（）（）＋＋xyvvv；i1＋y；；式（12。5）中第1、2、3项对应于换位矩阵的条件（1）、（2）、（3），第4项对应于条件（4），即使路径最短的目标要求。A、B、C、D为4个正常系数，将式（12。6）写成如IT（12。5）所表示的Hopfield能量函数标准形式，得的表达式和的值如下：xiyixi；。。。由（12。6） 得Hopfiled网络运行方程式如式（12。8）： （n） （n）
用n╳n=25个神经元的输出 vxi
（1 ≤x
≤
n；1 ≤
i
≤
n） 表示换位矩阵中的某一元素（取值
为“0”或“1”），其中x表示用户，i表示访问次序，则可以写出与本问题对应的计算能
量函数为：
n
nn
A
BC
2
（12。6）
D
xi
1 yi。
2 x=1 y≠
xi=1
Txi； yi
=。Aδxy
（1。δij
） 。
Bδij
（1。δ
xy
） 。
C
。
Dd（x； y）（δ
j；i＋1 ＋δ
j；i。1）（1。δ
xy
）
（12。7）
I
xi
=
CN
其中δxy
=
1 if
x
=
y
0
。。
。
nn
nnn
xi
xi
du
=。
u
。
C（ΣΣvxj
。
n） 。
AΣvxj
。
BΣvyi
。
DΣd（x； y）（vy；i＋1 ＋
vy；i。1）
（12。8）
dt
τx=1 j=1 j≠iy≠xy≠x
v
。。
。
。。
=
g（uxi
） x
1；2；L；n； i
=；2；L；n；
=
xi
作用函数 g选用sigmoid函数 g（uxi
） =12
（1＋
th（uxi
/ u0 ）） ；网络初始值可置为
uxi
=
1/ n；在选择适当的系数A；B；C；D； τ；进行迭代运算，得网络收敛稳定输出vxi
，即可
获得巡回配送的最短路径。
12。3 网络流问题
12。3。1图的基本概念
考虑6个城市间的交通路线图；如图12…12所示；图中的点V1、V2、V3、V4、V5、V6代表6
个城市，又称为顶点，连接各顶点的弧记作（V1、V2）、（V2、V3）、。。。等。这种表明各点
之间连接关系的图形，通常称为图。
从一个顶点沿着弧、顶点、弧、顶点的顺序，回到出发点的路线称为回路，如图12…2
中，V1→V2→V4→V3→V1、V4→V5→V6→V4都是回路，不含回路、各顶点又相互连通的图称为
树，如图12…3就是一个树。
V1 V2
V2
V3
V4 V3
V4
VB5
VB6
VB5
VB6
图12…2 回路 图12…3树
12…12
10（5）
3（2）
5（1）
10（5）
3（2）
5（1）
在实际问题中，对于一个图，总要考虑它们代表的各城市间道路的交通流量、流动方
向，因此需在各顶点弧上标明流动方向和流量限制，这种表示流动方向和流量限制的图称
为网络或网络流，如图12…4。
V1 V2
V3
V4
V5
V6
图12…4
在网络流中有些点只有发出，称不发点或源点，如图12…4中的V 1；有些点只有收入，
无发出，称为收点或汇点，如图12…4中的V 6，还有些顶点既有收入又有发出，称为中间
点。
12。3。2 网络最大流问题
1。问题的提出
已知连接产地V1与销地Vn的交通网，每一弧（Vi；Vj）代表从Vi到Vj的运输线，产品经由
Vi输送到Vj，弧旁括号外的数字Cij为弧的容量，括号内的数字Xij为Vi到Vj的货运量，要求合
理安排Xij，使V1到V n的货运量最大。这种问题称为最大流问题，如图12…5所示。
V4
V2 6（3）
11（6）
10（5）
2（3）
V1
V6
17（2）
8（3）
6（3）
图12…5
2。寻求最大流的标号法
对于包含n个顶点V1，V2。。。；Vn的网络流，V 1为发点，Vn为收点，各段弧（V i；Vj）上容量为
Cij，设｛Xij｝是一个可行流，如果存在一条从V1到Vn的路线，这条路线具有以下特点：
（1）所有正向弧（弧的方向与流向一致）上 Xij0。
则称此条路线为可行流｛Xij｝的一个增广链，记
ε1=min｛cij…xij｜ 当（v i；vj）为正向弧｝
（12。8）
ε2=min｛xij｜ 当 （v i；vj）为反向弧｝ （12。10）
ε=min｛ε1； ε2｝ （12。11）
由增广链的特点可知ε》0；按如下公式调整可行流｛x ij｝为｛x ’ij｝：
当（vi；vj）是增广链的正向弧
当（vi；vj）是增广链的反向弧 （12。12）
当（vi；vj）不在增广链上
V3
V5
12…13
。x
＋ε
ij
x'ij
=
。。
xij
。ε
。
。
xij
显然；此时｛x’ij｝仍为可行流；且它的值比｛x ij｝增加了ε。
由此不难看出；对于可行流｛x ij｝；判断它是否最大流及对它进行调整；关键在于求出其增
广链；标号法就是基于此来寻求最大流的；其具体步骤如下：
第1步 给发点以标号（0；＋）
第2步设v i已经有了标号；与v i相邻的点vj尚未标号。若在弧（v i；vj）上； x ij0；则给v j以标号（i；…）。继续这个步骤，直到给收点v n以
标号为止。
第3步利用“反向追踪”，找出