计算机图论中查找路径算法分析线路布局

-- 以哈密尔顿环(Hamiltun Cycle)作为分析实例






作者开发了两套计算机图形历遍算法,一个是不重复路径历遍算法;一个是不重复路径与顶点算法。作者利用第二套算法对布线拓扑结构进行分析,并以155年前哈密尔顿提出的著名哈密尔顿环作为分析实例,展开论述。通过改变其中某两个顶点的路径状态,得出具体的数据,在这些数据的基础上,给出结论。

先看哈密尔顿环的具体图形,和作者给出的标号。


作者先给出正常状态下哈密尔顿环的查找路径结果:

只有8 个顶点的盲路: 6
只有9个顶点的盲路:6
只有 10个顶点的盲路: 12
只有 11个顶点的盲路: 42
只有 12个顶点的盲路: 60
只有 13个顶点的盲路: 108
只有 14个顶点的盲路: 246
只有 15个顶点的盲路: 360
只有 16个顶点的盲路: 462
只有 17个顶点的盲路: 636
只有 18个顶点的盲路: 630
只有 19个顶点的盲路: 390

完整 20个顶点的路径: 162占总数量的5.192%

总共查找出的路径数量: 3120

我们以三个数据指标:“完整 20个顶点的路径数量”,“占总数量的百分比”,“总共查找出的路径数量”来评估我们改变图形后的效果。

第一个改变:将点v15到v6的通路改成v15到v6的单行线,即只能由v15到v6,禁止v6到v15,我们将挑选v16、v17、v18、v19、v20以及v15和v6作为评估点运行程序后,得出以下结果:


完整 20个顶点的路径数量
总共的路径数量
百分比(%)
v6
108
2080
5.192
v15
162
3120
5.192
v16
108
2600
4.153
v17
110
2306
4.77
v18
106
2410
4.398
v19
112
2450
4.571
v20
123
2551
4.822

从数据对比看,改动一条通路为单行线,所造成的结果是整体的完整通路比重下降1个百分点,总体路径却减少18%到33.3%。

第二个改变:而我们在原有的基础上,为v15增加一条单行线到v6的话,因为存在了回路查找出的路径将超过20个点,我们依然计入完成路径数目,结果如下:

完整 20个顶点的路径数量
总共的路径数量
百分比(%)
v6
658
5200
12.65
v15
162
3120
5.192
v16
318
3640
8.73
v17
282
3697
7.627
v18
279
3687
7.567
v19
294
3688
7.971
v20
270
3695
7.307

这回可以是大跌眼镜,作为v6来说,为它增加一条到该点的单行线,却演变成增加从该点历遍的总体路径数目,增加67.7%的路径,而增加的完整路径只占12.7%。同时以v6点形成162条回路。占到比重的3.1%。但搜索的代价却要高出4倍之多。

从我们日常的经验看,v15应该是最大的收益者,这次依然是不变。

而其它点的路径总数增加16.7%到18.5%不等,而完整路径的比重却增加了2%到3.5%不等,但花费的代价却要高出7到5不等。

这说明如果将v6作为线路处理的中心点,就再合适不过了。V15的情况却说明一条道理:有时候生活常识是会出问题的!

第三个改变:而我们在原有的基础上,为v15增加一条通路线到v6的,因为存在了回路查找出的路径将超过20个点,我们依然计入完成路径数目,结果如下:

完整 20个顶点的路径数量
总共的路径数量
百分比(%)
v6
1658
7280
22.77
v15
1658
7280
22.77
v16
1326
5674
23.37
v17
1392
6072
22.92
v18
1344
5860
22.94
v19
1360
5914
23.00
v20
1377
6008
22.92

增加一条通路,产生效果巨大的改变,v6,v15路径总数增加133%,完整路径比重上升到22%,但不要高兴得太早,回路的比重上升到9.05%。

其它点的情况都差不多。

第四个改变:我们再做一个“飞线”的实验,原有的图形关系不变,从v20飞线一条通路到最远的v1,结果如下:

完整 20个顶点的路径数量
总共的路径数量
百分比(%)
v6
276
5180
5.328
v15
222
5102
4.351
v16
276
5188
5.32
v17
230
5100
4.509
v18
218
5114
4.263
v19
274
5128
5.343
v20
177
3990
4.436

结果目不忍睹,路径总数增加66%,可完整的路径比重却上升的不到1%,下降的却有1%。搜索代价提高了66%。
【计算机图论中查找路径算法分析线路布局】
生活常识又骗了我们一次,增加通路未必是好事,关键要对路。

    推荐阅读