一个格点最短路径问题的思考

金晓阳

【摘要】将平面格点最短路径问题，放在平面直角坐标系中研究比较便捷.本文用三种不同的方法解决了一种平面格点最短路径问题，进而将问题推广到空间情形.通过对问题的探究，最终成功推广了组合数性质.

【关键词】

格点；最短路径；概率；组合数性质

图一格点最短路径问题是十分有趣的数学问题.它与高中数学中的排列组合、概率等概念有很大关联，让我们先来做一道这样的问题：

例1 如图一所示，在平面直角坐标系中有一动点P，t0时刻位于原点处，之后每一秒内，点P沿x轴正方向或y轴正方向运动一个单位，两种运动方式的概率相等.请问6秒后，点P运动了6个单位的路程，到达（3，3）的概率为多少？

分析：由于整个运动过程可能的路径即基本事件数是有限的，且向右运动1个單位与向上运动1个单位为等可能事件，即每个基本事件出现的可能性相等，故该模型符合古典概型.

图二解法一 点P到达某个格点之前，必然经过与该格点相邻的左方一个格点或下方一个格点，即到达某格点的最短路径数等于到达左方与之相邻格点的最短路径数和到达下方与之相邻格点的最短路径数之和.若到达x轴上的某个格点，之前必然由原点O开始不断沿着x轴正方向运动，这是唯一的选择，故到达x轴上每个格点的最短路径数都是1，同理可得，到达y轴上每个格点的最短路径数也都是1.由此可计算出到达任意格点的最短路径数.

6秒后，点P一共移动了6个单位，可能到达（6，0）、（5，1）、（4，2）、（3，3）、（2，4）、（1，5）、（0，6），可由以上方法求出6秒后运动到这些格点的最短路径条数（如图二所示），这些路径中任意两条出现的概率相等.

由此，我们成功地推广了组合数性质.