《给定数量线圈的网络布局.docx》由会员分享，可在线阅读，更多相关《给定数量线圈的网络布局.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、给定数量线圈的网络布局（系统工程杂志）2014年第四期全网可测的基本线圈布局优化支撑树算法交通的出行起点和终点统称形心点，而其他的节点则被称为非形心点或普通节点。假设网络中除了形心点外，不存在其他节点度为或的节点。为了更好的利用一般节点处的流量守恒条件，以及网络中总的出行产生量与吸引量之间的平衡关系，需对对一般交通网络进行转换。经转换的网络将只含一个虚拟的形心点。在构造只含一个虚拟形心点的网络时，假如在起点处仅有向外发散的路段，那么将这些路段的起点转为新添加的虚拟形心点，但不改变路段的方向。然后将从网络中删除。进一步来讲，假如由该起点向外发散的路段数多于一条，为了附带获得该起点处的出行产生量，
2、在把该起点转变为虚拟小区形心点之前，需要统计与其相关联路段上的流量。类似的方法可以以用于终点，在此不再赘述。有时一个节点可能既是起点又是终点，因而在该节点处既有发散又有会聚的路段。假如只要一条发散和一条会聚路段，能够将这两条路段的端点与虚拟形心点相连；或者增加两条不同方向的路段来连接该节点与虚拟形心点。在只含有一个虚拟形心点的交通网络中，所有节点处都能够应用流量守恒方程。在只含有一个虚拟形心点的交通网络中，假如与某一节点相关联的路段中只要一条路段的流量未知，那么通过流量守恒条件可确定该未知流量。假如能依次在每个节点处应用流量守恒，一步一步获得各条路段上的流量信息，直至最后获取所有路段的流量信息
3、，那么我们的全网路段流量观测问题即得以解决。可利用如下算法求解全网可测的线圈布局问题：为只含有一个虚拟形心点的交通网络构建一个支撑树，将支撑树中所包含的路段标记为“不需要安装线圈的路段，将其余的路段标记为“安装线圈的路段。：搜索支撑树或该支撑树的余图，令是度为的节点的集合。执行如下操作：假如是空集，则算法终止；假如不是空集，则需要进行如下步骤：从中任意选取一个节点，在节点处，应用流量守恒计算出属于该支撑树并与节点相关联路段的流量或支撑树的余图中流量未知路段的流量。：从集合和支撑树或支撑树的余图中同时删除节点并从支撑树或支撑树的余图中删除连接节点与支撑树或支撑树的余图的路段。假如此时集合不是空集
4、，返回；否则，再次搜索支撑树或支撑树的余图找到一个新的集合，然后进入。由于利用了网络的支撑树，因而我们称上述算法为全网可测的支撑树算法。引理假如图是一个连通图，是图中的任意一个回路，删除中的一条路段，图还是连通的。定理每一个连通图都有支撑树。证实设图是连通图，假如不含回路，那么本身是一个树，进而是它本身的一个支撑树；假如含回路，任取一个回路通过引理可知从中任意去掉一条边，得到图的子图是连通的，假如这个子图中不存在回路，那么其就是支撑树；假如这个子图中仍存在回路，那么至少存在一个回路，从中任意去掉一条边，得到图的子图还是连通的。重复上述步骤，直到最后得到的子图中不含回路。由于在这一经过中并没有删
5、除图的节点，所以包含了的每一个节点。因而是的一个支撑树。定理存在一个安装线圈数量最少的路段集合，基于该集合中的路段检测流量可揣测出网络全部路段的流量，但是该路段集合并不唯一。证实由定理可知，只含一个虚拟形心点的交通网络是连通的，因而该网络有支撑树。根据支撑树算法，支撑树的余图中所包含的路段就构成了安装线圈的路段集合路段数最少，由此存在性得证。从只含一个虚拟形心点的交通网络的构建经过可知必然存在一条由连接原始网络的一对的一条途径路段的起讫点可能变为了虚拟形心点和可能新增的虚拟路段与上述途径相连构成的回路。由定理的证实可知，在回路中选择不同的路段进行删除，进而能够得到不同的支撑树，由此解的多样性得
6、证。定理在只含有一个虚拟形心点的交通网络中，分别用和表示路网中的路段数和节点数。在知足可揣测出全部路段流量的条件下，路网中需要安装线圈的路段数最少为条，不需要安装线圈的路段数最多为条。证实给定正整数，任意一个含有个节点的树都包含条路段。由于支撑树包含了经改造后交通网络中的所有节点，并且有条路段。假如增加任意一条路段到支撑树中，则至少构成一个回路。假如将回路中所有路段的流量都增加或减少一定量，那么在所有节点处流量守恒条件仍然成立。但是这将使得一部分路段的流量无法被推断出来的。因而不需要安装线圈的路段数最多为条。又由于该交通网络中有条路段，因而在能够推断出全部路段流量的前提下，需要安装线圈的路段数
7、最少为条。给定数量线圈的布局优化分析定理对于图中任何一个由度大于或等于的节点组成的连通子图回路，其路段流量是无法确定的。证实将连通子图分成两类：第一类是由度等于的节点构成；第二类是由度大于或等于的节点构成，并且至少有一个节点的度大于。假设是任意一个属于第一类且至少含有个节点的子图，考虑下面的算法：从中选择一条路段，令和是的两个端点。：当和不一样时，重复步骤，：选择与相关联的路段，并且：令是路段的另一个端点。：令，该算法最终一定会终止，由于子图是连通的并且节点的个数是有限的。当算法终止时，包含了中所有节点的一个回路就出现了。事实上这个回路就是本身。假如回路中每条路段的流量均增加或减少一定量，由于
8、流量守恒在所有节点处仍然成立，因而第一类子图的路段流量都是无法确定的。对于第二类子图，当利用节点流量守恒条件时，易知未知数数目大于方程数目，因而根据线性方程理论可知问题的解不唯一。这里方程数对应节点数目，未知数对应网络的路段数目。交通网络中对于给定数量的线圈的布局优化问题，其本质在于通过所安装的线圈能够推断出更多路段的流量。影响线圈布局的因素主要有两个：给定线圈的数量；线圈布局的拓扑特性。考虑上述两个因素，在交通网络中，对于给定个线圈的布局优化问题给出如下算法：应用上节给出的支撑树算法，构造的支撑树用和分别表示和的余图中路段的集合；用表示的子图中能够构成回路的路段集合。假如，则转至；否则，转至
9、。：在中，选择任意的条路段，在其上安装线圈，然后将安装了线圈的路段从支撑树中删除，转至。：令为图的一个子图并且与一样。用和分别表示图中路段和节点的集合，表示一个空的路段集合，图中所有路段的权都分配为。令，并且定义为集合的基数。当时，反复执行如下步骤：仅考虑中的路段并计算其节点度，将中度为的节点添加到集合中。：对于任意一个节点，都会存在一条连接节点与的余图的路段，并将的权设为：令。从中删除集合中的所有节点，并且从中删除连接集合中节点与图的所有路段。然后更新图，令：反复执行下述步骤次：从中选择一条路段与从中选择的其他路段进行比拟，将添加到中，在此经过中会得到权最小的：将从中删除，并添加到中，更新：
10、除了最终得到的图中包含的路段，其余的路段就构成了安装给定的个线圈的路段集合，也就是对于给定个线圈的优化布局。需要十分指出的是一个连通图能构建出多个支撑树。算法中用到的支撑树只是诸多支撑树中的一个，因而线圈的优化布局也会多种方案。然而至今还没有有效的方法能够将一个图的支撑树全部都列举出来。例如一个含有个节点的完全图，就能构建出个支撑树。因而，现实有效的方法就是将算法应用于不同的支撑树，综合比拟产生的结果，进而选择一个最佳的线圈布局方案。根据定理，假如，则能够推断出交通网络中所有路段的流量；假如，遭到线圈数量的限制，部分路段的流量是无法推断出来的。由定理的证实可知，假如一条路段处于回路中，那么其流
11、量也是无法推断出来的。在使用支撑树算法时，可采取向支撑树中添加路段序列的方法来计算未安装线圈路段上的流量。当一条路段处于回路中时，该路段会阻碍接下来的路段流量推断，因而应该先计算出其流量。这就是为什么要使最终的权重最小，并且当构成回路不可避免时，应尽量使新添路段处于已有回路或与已有回路中的路段构成新的回路。算例分析图所示交通网络中包含了个形心点、条路段和个节点。节点和是出行起点，节点和是出行终点。图中经转换后的网络仅含有一个标记为的虚拟形心点，条路段和个节点。对于基本的问题，由于利用支撑树算法能够得到不同的安装策略。由路段、构成图中网络的一个支撑树；路段、构成另一支撑树。上述任一支撑树包容的路
12、段均可作为不需要安装线圈的路段集合完成全网流量的检测。在图所示的网络中，对于给定的个线圈进行优化布局。根据定理，为了能够推断出全部路段的流量，安装线圈的路段数最少应为：条。很显然这个数字比大，因而该网络中有部分路段的流量是无法推断出来的。利用第节提出的算法，首先构建包含路段、的支撑树，然后添加路段序列、或、到以上不需要安装线圈的路段集合中，最后路段、或、构成了不需要安装线圈的路段集合。棋中、或、五条路段的流量是无法推断出来的。但是假如构建一个包含路段、的支撑树，并且添加路段序列、到以上路段集合中，最终会有、共六条路段的流量无法推出。比拟以上构建不同支撑树而得到的结果，很显然第一种基础支撑树的选择优于第二种。