中国学术界和华人影视界X度空间理论初探(4)
时间:2017-06-19 21:55 来源:毕业论文 作者:毕业论文 点击:次
本文通过构建与计算机学术界和华人影视界同构的计算机模型，模拟两个圈子的社会关系,并利用这些分析各自圈子内社会关系，尝试发现和解释两个圈子的各自组织特点，行为方式，个性特征等，以推进这两个圈子内更好的信息共享和数据合作。 2 课题研究所采用的算法及工具 2.1 相关算法介绍 2.1.1最短路径算法 本次课题中为了计算学术界中任何两个人之间最短距离的平均值，我选用图这种数据结构来构建社交网路，并使用Dijkstra及floyd算法分别进行单源最短路径以及所有点对间最短路径的计算，因此下面简单介绍一下折算法。 Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN，CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。其具体原理如下所述。 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v，vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v，vk)，或者是(v，vj，vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v，vi)上的权值，或者是D[k](vk∈S)和弧(vk，vi)上的权值之和。 迪杰斯特拉算法描述如下：1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G，v)，i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。 Floyd算法 Floyd算法是解决图中所有点对间最短路径问题的一个形式简单的算法，它的基本思想是这样的： 假设求从顶点vi到顶顶vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长为arcs[i][j]的路径，该路径不一定是最短路径，尚需要n次试探。首先考虑路径(vi，v0，vj)是否存在（即判别弧(vi，v0)和(v0，vj)是否存在）。如果存在，则比较(vi，vj)和(vi，v0，vj)的路径长度并取长度较短者为从vi到vj的中间顶点序号不大于0的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果(vi，…，v1)和(v1，…，vj)分别是当前找到的中间顶点的序号不大于0的最短路径，由此，路径(vi，…，v1，…，vj)就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推。在一般情况下，若(vi，…，vk)和(vk，…，vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将(vi，…，vk，…，vj)和已经得到的从vi到vj且中间顶点的序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次的比较之后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得所有顶点对之间的最短路径。 (责任编辑：qin) |