计算机图论查找路径算法分析城市布局
作者开发了两套计算机图形历遍算法，一个是不重复路径历遍算法；一个是不重复路径与顶点算法。作者利用第二套算法对城市布局结构进行分析，并以常见的城市交通环城高速作为分析实例，展开论述。通过改变其中路径状态，得出具体的数据，在这些数据的基础上，给出结论。
先看模拟布局图形和作者给出的标号。
作者先给出正常状态该图形的查找路径结果：
顶点总数：15
内层点的查询结果：
只有6个顶点的盲路： 2
只有7个顶点的盲路： 4
只有8个顶点的盲路： 14
只有9个顶点的盲路： 30
只有10个顶点的盲路：82
只有11个顶点的盲路：168
只有12个顶点的盲路：280
【计算机图论查找路径算法分析城市布局】只有13个顶点的盲路：354
只有14个顶点的盲路：336
完整15个顶点的路径：234
路径总数：1504
中间层点的查询结果
Number of Loop:4625
只有6个顶点的盲路：0
只有7个顶点的盲路：4
只有8个顶点的盲路：16
只有9个顶点的盲路：36
只有10个顶点的盲路： 64
只有11个顶点的盲路： 120
只有12个顶点的盲路： 228
只有13个顶点的盲路： 240
只有14个顶点的盲路： 264
完整15个顶点的路径： 196
路径总数：1168
外层点的查询结果：
只有6个顶点的盲路：2
只有7个顶点的盲路：4
只有8个顶点的盲路：14
只有9个顶点的盲路：30
只有10个顶点的盲路：82
只有11个顶点的盲路：168
只有12个顶点的盲路：280
只有13个顶点的盲路：354
只有14个顶点的盲路： 336
完整15个顶点的路径： 234
路径总数：1504
我们抽取三样指标作为我们考察的数据指标，即：“完整顶点的路径数量”、“完整顶点的路径数量的比重”和“路径总数”。以上内中外层的指标性数据如下：
| 顶点 |
完整顶点的路径数量 |
路径总数 |
完整路径的比重（%） |
| 内层点： |
234 |
1504 |
15.56 |
| 中层点： |
196 |
1168 |
16.78 |
| 外层点： |
234 |
1504 |
15.56 |
从数据我们可以看出“二环”的完整路径的比重最高，事实上是迷路的可能性最低，但通路少于内环和外环，交通状态最差劲。所以这地方最适合城市中使用率低的地方。比如大型体育馆之类的。
第一我们假设在内环改善交通，在v4与v1间架设一条高架桥。情况会怎样呢？我们抽取一些典型的样板做分析，看结果：
| 顶点 |
完整顶点的路径数量 |
路径总数 |
完整路径的比重（%） |
| V1 |
257 |
1987 |
12.93 |
| V2 |
350 |
2457 |
14.24 |
| V4 |
257 |
1987 |
12.93 |
| V6 |
224 |
1932 |
11.59 |
| V7 |
311 |
1907 |
16.31 |
| V12 |
352 |
2414 |
14.58 |
| V13 |
292 |
2482 |
11.76 |
首先完整路径的比重数据恶化，比重下降很快，多一条路反而因复杂度提高而出问题，直接架设高架桥的v4与v1的两点并没有捞到实际好处，反而比重下降接近3个百分点。就是说我们迷路的可能性增加了。好处在于通路的数量增加了近10%。令人吃惊的是改善最好的反而是靠近增加路径的V2点，通路数量增加53%。外层点增加的数量远比内层和中层点要高。改善最好的是v7，通路的增加近59%，迷路指数居然接近未增加时的状态。
第二我们假设在增加一条高架桥，由v4到v2，还是这些点，我们看看结果如何
| 顶点 |
完整顶点的路径数量 |
路径总数 |
完整路径的比重（%） |
| V1 |
375 |
3140 |
11.94 |
| V2 |
375 |
3140 |
11.94 |
| V4 |
280 |
2470 |
11.34 |
| V6 |
281 |
2887 |
9.73 |
| V7 |
466 |
2914 |
15.99 |
| V12 |
479 |
3619 |
13.23 |
| V13 |
358 |
3768 |
9.50 |
我们先看迷路指数，都在升高，路多了自然很容易迷路，这符合我们日常的经验。最倒霉的是v6和v13，迷路指数大幅上升，意味着在那里开公司，请个外地司机帮你开车能气死你。但增加的通路呢？收益最大的是v1点，通路比第一种情况增加60%。大家要注意在那里开超市啊！而v4增加的幅度不大，只有9%。V7拿到的实惠最多，迷路指数增加不快，通路较第一种情况增加50%，是彻底的大赢家。V13不温不火，迷路指数和通路都增加接近20%。
通路改善最显著的是v6，较第一中状况，通路增加70%。
第三我们决定在市政中心建一个中心广场，向巴黎学习，所有车辆在中心广场绕圈找路口出去。这样我们在中心点加多一个v16，连接v1，v2，v3，v4和v5点。我们看结果：
| 顶点 |
完整顶点的路径数量 |
路径总数 |
完整路径的比重（%） |
| V16 |
1170 |
7520 |
15.56 |
| V1 |
1292 |
8954 |
14.43 |
| V2 |
1292 |
8954 |
14.43 |
| V4 |
1292 |
8954 |
14.43 |
| V6 |
1122 |
8232 |
13.62 |
| V7 |
1122 |
8232 |
13.62 |
| V12 |
1332 |
10608 |
12.56 |
| V13 |
1332 |
10608 |
12.56 |
巴黎就是巴黎，增加一个关键点带来的效益就吓死人。迷路指数接近我们一开始的环城高速模式，并没有因为增加了5条道路而带来快速下降，通过中心广场节点的调节，带来了高效益。其他各点的通路增加近460%，接近5倍的增加。
这回你可以思考城市道路布局了吧！
推荐阅读
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- 历史上的今天|【历史上的今天】2 月 16 日（世界上第一个 BBS 诞生；中国计算机教育开端；IBM 机器人赢得智能竞赛）
- 计算机网络基础TCP\HTTP\HTTPS
- 超好用的PubMed文献查找管理插件—Scholarscope
- Elasticsearch|Elasticsearch 简介
- 计算机网络|计算机网络——DHCP协议详解
- android|android today上下卡片,【精品文档】关于计算机专业大学生安卓系统有关的外文文献翻译成品（基于Android（安卓）的考勤管理系统（中英文双语对照）
- 计算机与时间
- 中国农业大学计算机就业薪资,2020年工资出炉，这个行业倒数第一，不过这类大学专业有金矿可挖...
- 网络|简单聊聊压缩网络