SAT数学寻路问题的两种思路

如下图，从A点到B点，只能沿着直线走，最短的路径有几条，这样的问题，本文称之为寻路问题。本文会介绍两种基本的解法。

 1. 排列法

从A点到B点的走法，可以用画图和语言的方法共同表示，比如：

有兴趣的同学可以自己画一画，不管怎么画，从A点到B点，只能是四个汉字“右、右、上、上”的排列，所以熟练掌握排列组合知识的同学可以直接用公式法写答案：

上式中的分子 表示“右、右、上、上”四个字母进行排列所得到的总情况，因为，两个右字是一样的，重复出现的，所以要额外除掉这两个字母的排列 ，同理两个上也是重复的，所以要再除一次 。

用排列法的优点是，如果地图扩大，变成3×3或者4×4，甚至 n× n的方格，再解法上不会有太大的变动，以n×n的方格举例，答案为：

2. 做图法

如上图所示，用箭头表示出每一小段路程的运动方向，因为题目要求最短路程，所以凡是水平的线段，只能向右，所有竖直的线段，只能向上。画完线段以后，给连接起点A的两条线段标上数字1，各自表示从A出发的一中路线。然后凡是遇到线段相交的地方，法箭头想象成是水流，所有流出交点的箭头的数字为所有流入交点的箭头的数字和，表示到这个交点不同的走法数量。

为了大家更好的理解上面的方法，再给出3×3方格的走法：

用作图法比较适用于地图大小比较小的时候，画图比较方便，或者是题目有额外的限制条件，比如必须要经过地图的某点，或者某条路坏了，不能走之类。有兴趣的同学可以自己给自己出题然后画着玩一下。

SAT推荐阅读：