人类前进的步伐逐渐加快,无处不在的网络规模逐渐增大,作为图论中最基本的问题之一的最短路径搜索也随之面临挑战：在大规模网络中,经典求解算法的复杂度太高。因此,针对大规模网络的最短路径求解问题,本文结合了商空间理论的粒度分层思想,给出了分层求解算法,在不同粒度空间上跳转的过程中,求解最短路径问题。商空间理论模型是张铃教授和张钹院士在对人类思考问题的方式进行深入剖析之后提出的。该理论在表示问题时用的是一个三元组(x,f,T),再通过粒度的转换,将问题转换成新的三元组([X],[f],[T])表示的问题。在不同的粒度空间跳转,将原有问题简化,解答,最终构造出原粒度空间下的问题的解。这种问题求解的思想正是基于人类的思维方式——可以在观察和分析问题时,对问题构造出极不相同的粒度空间,而且往返自如。划分原粒度空间下的大型网络成若干个子网络,再将这些个子网络映射到较粗粒度空间下的新网络中,经过这个映射过程,网络的规模得以大大缩小。新网络和原网络构成了不同层次上的网络。在对原问题进行粒度粗化,以及对在新网络中求得的解细化到原空间的过程中,实现了不同粒度空间之间的跳转。基于商空间理论的两大基本原理,本文的最短路径求解算法解决了传统算法复杂度过高的问题。本文的主要工作为：1.研究不同类型网络的社团划分方法。在无权网络和加权网络两种情况中,结合Newman等人给出的不同模块度函数,以模块度函数作为划分依据,将规模较大的网络划分成相对规模较小的网络。这一划分标准在现今的网络划分算法的研究中,是受到广泛认可的,并被用于验证新算法是否具有有效性。2.在网络划分的基础上,构造不同粒度空间下的层次网络。对划分得到的若干个子网络,分别用新的节点代替,即在粒度选择中以是否处于同一社团为等价关系；根据原网络中各社团之间的边连接情况,保持原有的连通关系,构造出粗粒度空间下的网络,这一新网络所处的层次相对较高。3.在不同的粒度空间下的网络间跳转,实现最短路径的近似求解。原空间中的最短路径问题,经过网络的抽象,转换到在新网络中求解,得到的解需要回归到原网络中。而最终解的构造是在粒度空间的细化过程中给出的。这样就实现了原问题的求解在不同粒度空间的跳转。文章利用计算机生成的网络中检验分层求解算法的有效性,基于这一基础验证,再进一步将此算法应用到美国的三个不同规模州、区的城市交通网络图中,进行最短路径的求解。该过程有效地解决了经典算法不适用于大规模网络的问题,然而由于原网络在经过划分子网这一抽象过程之后,原本全局性的一部分信息会随之丢失,而只保持局部性质,所以最终得到的解并不一定是原问题的最佳解,很可能只是较佳解。可是,若从实际应用的角度来说,这一较佳解已经能够满足我们的需要。因此,我们用精度换来的时间是完全可以被接受并得到广泛运用的。
