Mizrahi Alice, Marsh Thomas, Hoskins Brian, Stiles M D
National Institute of Standards and Technology, Gaithersburg, Maryland, USA.
Maryland NanoCenter, University of Maryland, College Park, Maryland, USA.
Phys Rev Appl. 2018 Dec;10(6). doi: 10.1103/physrevapplied.10.064035.
Finding the shortest path in a graph has applications in a wide range of optimization problems. However, algorithmic methods scale with the size of the graph in terms of time and energy. We propose a method to solve the shortest-path problem using circuits of nanodevices called memristors and validate it on graphs of different sizes and topologies. It is both valid for an experimentally derived memristor model and robust to device variability. The time and energy of the computation scale with the length of the shortest path rather than with the size of the graph, making this method particularly attractive for solving large graphs with small path lengths.
在图中寻找最短路径在广泛的优化问题中都有应用。然而，算法方法在时间和能量方面会随着图的规模而扩展。我们提出了一种使用称为忆阻器的纳米器件电路来解决最短路径问题的方法，并在不同大小和拓扑结构的图上进行了验证。它对于实验推导的忆阻器模型是有效的，并且对器件变化具有鲁棒性。计算的时间和能量随着最短路径的长度而扩展，而不是随着图的大小，这使得该方法对于解决具有短路径长度的大图特别有吸引力。
