A new approach to shortest paths on networks based on the quantum bosonic mechanism
A new approach to shortest paths on networks based on the quantum bosonic mechanism
复制标题
DOI：
10.1088/1367-2630/13/1/013022
复制
发表时间：
2011
影响因子：
3.3
通讯作者：
Xin Jiang;Hailong Wang;Shaoting Tang;LiLi Ma;ZhanLi Zhang;Zhiming Zheng
中科院分区：
文献类型：
--
作者：
Xin Jiang;Hailong Wang;Shaoting Tang;LiLi Ma;ZhanLi Zhang;Zhiming Zheng
本文提出了量子玻色子最短路径搜索（QBSPS），一个自然的，实用的和高度启发式的物理算法推理网络结构识别的量子动力学。QBSPS是基于一个类似安德森的巡回玻色子系统，其中玻色子的绿色功能被用作导航指针，一个准确地接近终端。通过严格的数学和物理证明以及大量的仿真，证明了QBSPS可以作为一种贪婪路由来寻求不同位置之间的最短路径。在方法论上，它是一种有趣的新算法，它植根于量子机制而不是组合学。在实际应用中，对于N个顶点的随机无标度网络中的所有对最短路问题，QBSPS的运行时间为O（μ（N）ln ln N）。在应用中，我们建议，相应的实验实现是可行的，考虑路径搜索在量子光通信网络中，在这种情况下，该方法执行一个纯粹的本地搜索网络，而不需要全局结构，是必要的，目前的图算法。
This paper presents quantum bosonic shortest path searching (QBSPS), a natural, practical and highly heuristic physical algorithm for reasoning about the recognition of network structure via quantum dynamics. QBSPS is based on an Anderson-like itinerant bosonic system in which a boson's Green function is used as a navigation pointer for one to accurately approach the terminals. QBSPS is demonstrated by rigorous mathematical and physical proofs and plenty of simulations, showing how it can be used as a greedy routing to seek the shortest path between different locations. In methodology, it is an interesting and new algorithm rooted in the quantum mechanism other than combinatorics. In practice, for the all-pairs shortest-path problem in a random scale-free network with N vertices, QBSPS runs in O(μ(N) ln ln N) time. In application, we suggest that the corresponding experimental realizations are feasible by considering path searching in quantum optical communication networks; in this situation, the method performs a pure local search on networks without requiring the global structure that is necessary for current graph algorithms.