论文标题
物理启发的多商品流动动力学
Physarum-Inspired Multi-Commodity Flow Dynamics
论文作者
论文摘要
在湿的实验中，粘液模具物理多头可以证明其解决最短路径问题和设计有效网络的能力。对于最短的路径问题，可以提供用于粘液演化的数学模型，并且已经在计算机实验中显示了动力学解决最短路径问题的数学分析。在本文中，我们引入了网络设计问题的动态。我们将网络设计作为构建有效支持多商品流问题的网络的问题。我们研究计算机模拟中的动态和分析。模拟表明，动态能够构建高效且优雅的网络。在理论部分中，我们表明动态最大程度地将目标结合了网络成本和通过网络路由需求的成本。我们还提供了最佳解决方案的替代表征。
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution.
