按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
巡回距离为：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步利用“反向追踪”，找出v 1到vn的增广链，例如设v n的标号为（k；＋），则在增广
链上vn前面的一点为v k；且弧（vk；vn）是正向弧，接下来检查v k，若其标号为（i；＋），则找出正
向弧（vi；vk）；若标号为（i；…）；则找出反向弧（v k；vi），依此下去，一直追踪至具有标号（0；＋）
的发点v1，得到由v1到vn的一个增广链。
第4步 调整过程，由式（12。9）至（12。11）得出增广链的调整量ε；根据式（12。12）得出
新的可行流｛x ’ij｝；令可行流｛x ij｝=｛x’ij｝；去掉所有标号；重新上述标号、寻找增广链及调整
过程，如果标号过程进行不下去，而v n尚未标号，则说明再也找不出增广链，当前可行流
即为最大流。
例12…4 求出图12…5的最大流
解：
第1步 首先给v 1标上（0；＋）
第2步 检查v 2，在弧（v1；v2）上，x12=5