2014上海公务员考试备考排列组合之最短路径解题方法

给人改变未来的力量2014上海公务员考试备考排列组合之最短路径解题方法中公教育上海分校（）制作微信：shoffcn中公教育公务员考试研究与辅导专家高肖肖上海市公务员考试的一种必考题型是排列组合问题，因为排列组合问题不仅可以自身单独出题，还可以结合概率相关的知识进行出题。纵观上海市考历年真题我们发现，在上海市考中有一种题型，在国考及其他省考中从未出现过的一种出题方式，那就是最短路径问题。什么是最短路径呢？顾名思义，从一个地点到达另一个地点，路径要求最短，问的是这时候方法总数是多少，也就是说最短路径不只是一条也不是一种走法，这种题型应该怎么来解题呢？我们通过一道例题来看一下这类题的解法。例：某城市街区由16个矩形组成，如图所示，其中实线表示马路，如果只能在马路上行走，那么从A点到B点的最短路径有多少条？A.20B.36C.70D.126解析：看到这种题目，大部分人的做法就是开始各种数，各种算，发现根本数不清楚到底多少，这时候怎么做呢？那我们可以来看一下，要想从A点到达B点应该怎么做，从A到到B肯定要向左走，也要向上走，走法挺多，但是题目中既然问的是最短路径，肯定要数最短路径的数量，肯定不能往回走，那么既然这么限制了，那么就意味着向上至少要走4步，向左也要走4步，也就是说最短路径肯定是要走8步，而且必须左4步，上4步，区别就是哪4步向上走哪4步向右走，只要选定了4步向右走或者向上走，那么另外的4步走法就已经确定了，选法不同也就是意味着走法不同，题目瞬间转化为8步里面任意选出4步向上走，就转化为一个组合问题，8个里面任意选4个的方法数是多少就AB给人改变未来的力量等于最短路径有多少种，所以最段路径的条数为4870C，答案为C选项。这种问最短路径的题目，就是首先要确定到底怎么走法是最短的，一般都是要两个能够去走，两个方向分别走多少，然后总的步数就已经确定了，然后就是从总的方法数里面挑选其中一个方向的走法，也就转化为了一个普通的排列组合问题，解题就变的非常容易了。接下来我们来看一下上海市考的一道真题。例：如图所示，某城镇共有6条东西方向的街道和6条南北方向的街道，其中有一个湖，街道在此变成一个菱形的环湖大道。现在要从城镇的A处送一份加急信件到B处，为节省时间，要选择最短的路线，共有（）种不同走法。【2010-上海】A.35B.36C.37D.38解析：这道题目拿到之后，和前面讲的一样要确定如何走是最短的，可以出是有两种走法，第一种走法就是A→CF→B，第二种就是A→DE→B，而且数了一下发现两种走法路径是一样的，所以根据排列组合的分类分步，我们知道这属于两类，总的方法数等于两类方法数相加。所以从A点到B点，要选择最短的距离有：①A→CF→B。A→C有5种方法；F→B有1种方法。共5×1=5种方法。②A→DE→B。A→D有10种方法；E→B有3种方法。共10×3=30种方法。从A到B的最短路线总共有5+30=35种走法。答案为A选项。从上面的例题和解题方法我们可以看出，很多题目用排列组合的方法来做事非常简单的，最短路径的只是其中一种，关键是题型的提取和转化过程比较难，所以平时做题的时候一定要学会思考和总结，这样子考试才能事半功倍，一举成“公”。给人改变未来的力量2014年上海公务员考试交流群：72362471电话：[phone]微博账号是“上海中公教育”上海公务员考试网（）。