- 上一篇：基于Kinect的人体运动姿态捕捉和识别技术研究
- 下一篇：社会标签系统挖掘研究中文博客标签及标签云图的自动生成研究
本文通过构建与计算机学术界和华人影视界同构的计算机模型，模拟两个圈子的社会关系,并利用这些分析各自圈子内社会关系，尝试发现和解释两个圈子的各自组织特点，行为方式，个性特征等，以推进这两个圈子内更好的信息共享和数据合作。
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的最短路径。按此方法，可以同时求得所有顶点对之间的最短路径。
-
jsp+mysql企业人事管理系统的设计和实现
-
C#和SQLServer的宿舍管理系统的开发
-
C#和sqlserver学生管理系统设计
-
计算机音乐分类辨识研究
-
基于网页分析和抓取技术的金融数据采集系统
-
asp.net+sqlserver学生选课管理系统设计和源代码
-
asp.net+sqlserver奔驰汽车汽车...
java+mysql车辆管理系统的设计+源代码
乳业同业并购式全产业链...
当代大学生慈善意识研究+文献综述
杂拟谷盗体内共生菌沃尔...
河岸冲刷和泥沙淤积的监测国内外研究现状
中考体育项目与体育教学合理结合的研究
酸性水汽提装置总汽提塔设计+CAD图纸
电站锅炉暖风器设计任务书
大众媒体对公共政策制定的影响
十二层带中心支撑钢结构...