本文研究内容

(1)了解并熟识省高速公路路网的分布情况以及现况。

(2)了解多路径的有效解决方法。

(3)要对Prim算法和Kruskal算法有深刻的认识。

(4)对遗传算法进行研究，并通过省的高速公路路网实例来对Prim算法、Kruskals算法以及遗传算法的优缺点进行分析。

本文主要研究内容

本文在一开始介绍了图论里面关于支撑树的相关概念，我们在解决多路径问题时，采用的办法时将一般的网络图转化为一个支撑树，由于支撑树的两个点之间的路径是唯一的，所以我们只需要在该图的余边集上设置标识站。我们将实际的问题转化为求一个网络图的支撑树的问题，

接着，我们分别比较了最常用的求支撑树的方法：Prim算法和Kruskal算法。最后又提出了采用遗传算法求最小支撑树的想法，并通过省高速公路路网情况对三者进行了比较。

最后，我们通过增加冗余的方式来提高了整体系统的稳定性和可靠性。

总结

随着我国的综合实力的提升，我国在高速公路这一方面的发展会更加的突飞猛进，随之产生的势必是路网的越来越复杂，环路也越来越多，拆分也越来越困难，我们通过对标识站的合理布设，从而来对汽车的真实路径做出了精确的识别，同时也解决了拆分难现象，达到了我们所要实现的目标。在这个过程中，我们做了一下这些工作：

1、首先我们分析问题，了解到出现这种情况的根本原因就是高速公路路网上存在着路径的多样性。我们巧妙的利用到图论中支撑树的知识，因为支撑树具有良好性质，主要是它的路径是唯一的。从而我们把一个抽象的问题变成寻找路网的支撑树。

2、基于对省高速公路路网的标识站优化工作，我们采用遗传算法来寻求最小支撑树，并且对路网进行了标号。通过初始化第一代，交叉算子以及变异算子，我们最终找到了我们想要的最优解。在最后，还将Prim算法、kruskal算法同遗传算法做了比较，结果是在路网情况很简单的时候，三者几乎没什么差别，但是当路网为我们所要研究的高速公路路网时，由于路网及其复杂，这导致Prim算法以及Kruskal算法会陷入局最部优，而对于遗传算法则不同，它是从整个全局去寻求，并且我们可以从遗传算法最终的结果中，再结合现有的龙门架，从而寻一个以现有情况为前提的最优解，而这一点正是Prim算法以及Kruskal算法的弊端。

3、在找到所要布设标识站的路段后，为了提高整个系统的可靠性，我们又通过增加冗余标识站来达到此目的。通过增加冗余标识站来提高整个系统的可靠性有两种方法，分别为重复式布设和分布式布设。最后并通过有利的情况说明，我们最终采取重复式布设来提高整体的可靠性。