“标数法”搞定 【最短路径数】类考题

　　本文由步知公考风暴羚羊老师原创“标数法”搞定 【最短路径数】类考题，考生可参考学习。

　　下图中的线段表示的是汽车所能经过的所有马路，这辆汽车从A走到B处共有多少条最短路线?

　　说解法前，先来看看这个最短路线怎么确定?

　　从A到B要最短，至少要走过三条横向马路，两条纵向马路，因此需要走5步(如图)。注意，每一步的方向都是由A向B移动，即往右走和往上走，不走回头路，那么，才会形成最短路线，其中，满足5步的路线非常多条，如何确定它的具体数量?

　　要算出数量有两种解法，一种简单粗暴，名为“标数法”;一种逻辑严谨、高大上，名为“排列组合”。我们一一来试试。

　　标数法，简单明了，从距离A 近的点开始，算出从A点到每一点的最短路线的数量a，从而，最后算出到B点的数量。

　　1、 先算与A相邻的点(如图，C和D)的最短路线的数量，毋庸置疑，数量自然是1，标注在相应点上，

　　2、 计算与已得出数量的点相邻的下一个点，如E、F、H三点。你会发现，从A到这三点，要走最短路线，就只能是向右走或向上走，那么必须要先走AC或AD，因此，去往这三条的路线数就依赖于C和D这两点。

　　A到E，只能经过C，所以，到E的最短路线数量=到C的数量=1;同理，可得从A到H点的最短路线数量=到D的数量=1。

　　A到F，由于F点相邻的点有C和D两点，所以从这两个方向都是最短路线，那么，到F点的最短路线的数量=到C点的+到D点的=1+1=2。

　　3、 继续选择与已得出数量的点相邻的下一个点，如G点。到G点的最短路线数=到F点的+到H点的=2+1=3。同理可得剩余所有点的最短路线数。具体数量如下图。

　　(PS：注意数量为6的这个点，切记不要算漏了)

　　为了便于大家记忆，不搞混。这里可以借用对角线来辅助解题。如下图，画出对角线后，对角线上两点的数量和=靠近B点的直角上的点的数量。这样子就不用担心会有遗漏。

　　从A地到B地的道路如图所示，所有转弯均为直角，问如果要以最短路线到达B地，有多少种不同的走法?

　　标数法的实质是列举法，通过累加的方式求出列举的所有情况数，原理虽粗暴，但简单实用。

　　套用排列组合10秒搞定最短路线数题

　　下图中的线段表示的是汽车所能经过的所有马路，这辆汽车从A走到B处共有多少条最短路线?

　　说解法前，先来看看这个最短路线怎么确定?

　　从A到B要最短，至少要走过三条横向马路，两条纵向马路，因此需要走5步(如图)。注意，每一步的方向都是由A向B移动，即往右走和往上走，不走回头路，那么，才会形成最短路线，其中，满足5步的路线非常多条，如何确定它的具体数量?

　　要算出数量有两种解法，一种简单粗暴，名为“标数法”;一种逻辑严谨、高大上，名为“排列组合”。本文主要分析高大上但速度快的排列组合法。

　　思路1：分类原理

　　我们知道，只要确定了A到B的纵向上是走的哪2条马路，就能确定最短路线的数量。但这2条纵向马路不能是随机从现有的8条中选出2条。如上图，如果不巧选了DF和CE，那么，整体的路线是AD—>DF—>FC—>CE—>EL—>LM—>MB(共7步>5步)，由于其中走了DF—>FC这段回头路，所以路线就变为了7步，显然不是最短路线。

　　所以，根据实际情况，最短路线的数量 需要分类考虑：

　　1) 纵向路线，下方选择AC，那么，第二条纵向马路可以是上方四条中任意一条，共4种最短路线。

　　2) 纵向路线，下方选择DF，那么，第二条纵向马路只能选择FL、GM、KB中一条，共3种。

　　3) 纵向路线，下方选择HG，那么，第二条纵向马路只能选择GM、KB中一条，共2种。

　　4) 纵向路线，下方选择JK，那么，第二条纵向马路只能选择KB，1种。

　　分类用加法，四类情况一共有4+3+2+1=10种。

　　思路2：分析最短路线的情况，直接用公式，10秒钟搞定

　　本题的最快的解法：从3+2=5条马路中选出2条马路，有多少种选法就有多少种最短路线，所以，答案是共C(5,2)=5×4/2=10种。

　　为什么用C(5,2)，你需要看懂以下四点：

　　第1、从A到B要最短，至少要走过三条横向马路，两条纵向马路

　　第2、只要确定了A到B的纵向上是走的哪2条马路，就能确定最短路线的数量。但根据上面的分类原理思路，知道这两条纵向不能随意选，要符合一定规律。

　　第3、每条纵向马路都与一条横向马路相连，那么，如果将“每一条横向马路我们看成与之右侧相邻的一条纵向马路”，比如将AD直接看成与它右侧相连的DF，简单来说，抽象层面上将横向马路也看做一条纵向马路。

　　第4、从抽象层面上的3条纵向(实际上三条横向马路)和实际意义上的2条纵向马路，共5条马路上任意选出2条，即确定走哪两条纵向马路，一种选法对应一种最短路线走法。因此，一共多少种选法，既有多少种最短路线数。共C(5,2)=5×4/2=10种。

　　为了更好地让大家理解，接下来，将 “5条马路上任意选出2条”对应的具体路线图用列举法进行演示。(已懂C(5,2)思路的同学可不看)

　　三条横向马路分别代表是不同的步，用a、b、c表示这三步，两条纵向马路用d、e表示。如下图：

　　一、抽出的2条若是a和d，代表的路线如图。因为有d(上方某纵向路线)在，所以此时a代表是下方的某一条纵向马路，因此a指a方位的最底端的横向马路，对应的纵向路线是它右端的纵向马路，上方d对应的是与下方纵向路线相连的纵向马路。如下图。

　　同理，若选择c和d，路线如图：

　　(同理可得选择b和d的路线图，这里暂不演示，同学们自己画一画)

　　二、选出a和e，代表的路线如图，a此时指a方位的中间位置的横向马路。同理可得选b和e 、或选c和e对应的路线。(为什么是这样，因为有e在，此时a代表是上方的它右侧的纵向马路，e是它下方与它左边相连的纵向马路)

　　(选b和e 、选c和e对应的路线 ，同学们自己画一画)

　　三、选出a和b，代表路线如图，靠近A的a选择a方位底端的马路(代表它右侧的纵向马路)。靠近B的b选择b方位中间的马路(代表它右侧的纵向马路)。从而确定一种最短路线的走法。

　　同理，若选择a、c，路线如图：

　　同理，若选择b、c，路线如图：

　　四、若选择d和e，即不走a、b、c三个方位的底端或中间位置的任一条横向马路。直接从连接A点的左侧经过。

　　这样子把四大类的示意图一画，大家就清楚为什么“C(5,2)”就能求出所有的最短路线数，所以下次再用“排列组合公式”求最短路线数时，千万不要再怀疑自己书写的组合式子中的n、m到底对不对，只要原理对，那你就能做对。当然，这里要提醒一下，排列组合只适合求解这种规则的田字格式样的路线图的最短路线数，像之前的标数法求最短路线数的文中最后一道例题就不适合用排列组合公式。

　　练习环节：

　　如下图所示，某镇共有6条东西方向的街道和6首南北方向的街道，其中有一个湖，街道在此变成一个菱形的环湖大道。现要从城镇的A处送一份加急信件到B处，为节省时间，要选择最短的路线，共有(　)种不同走法。

　　A、35

　　B、36

　　C、37

　　D、38

　　解析：本题求最短路线的数量。城镇的A处送一份加急信件到B处，要路线最短，那么必须要走菱形的环湖大道，要么经过CF，要么是经过DE，所以要分类考虑：

　　① A→CF→B ：A→C有C(5,1)=5种走法;F→B有1种走法;共5×1=5种走法。

　　② ②A→DE→B：A→D有C(5,2)=10种走法;E→B有C(3,1)=3种走法;共10×3=30种走法。

　　分类用加法，从A到B的短程线总共5+30=35种走法。故答案为A。

　　本文为步知网原创文章，任何公司、媒体、网站或个人未经授权不得转载、链接、转贴或以其他方式使用。已授权许可的媒体、网站，在使用时必须注明"稿件来源：步知网"，违者本网站将依法追究责任。