几类路径问题算法探索

Exploration of Algorithms for Several Path Problems

摘要: 通过仿真模拟老鼠觅食的行为，先用极限逼近的思想寻找老鼠在3 × 3的格子中找到食物的期望时间，从枚举法开始寻找老鼠在3 × 3的格子中找到食物的最短路径，再使用极限逼近方法寻找最短路径，随后将此情景进行推广，例如n × n的格子或者更复杂的情况，说明该方法可以适用于任意一个网络找任意节点间最短路，举出一个在实际生活的例子中，应用极限逼近的方法找到其所需的最短路径。得出当一个问题的实质是最短路时，都可以使用极限逼近的思想。

Abstract: By simulating mice’s foraging behavior, the idea of limit approximation can be used to work out the expected time for mice finding food in a 3 × 3 grid. The author firstly employs enumeration method to look for the shortest path for mice’s foraging in 3 × 3 grids, and then uses the limit approximation method to find the shortest path. Subsequently, the author extends this scenario, for example, trying to find the shortest path in an n × n grid or more complex cases. It is shown that this method can be applied to any grids to find out the shortest path between any nodes. An example is given in real life where the method of limit approximation is used to find the shortest path required. When the essence of a problem is to find out the optimal path, the idea of limit approximation can be always employed.