算法_贪心算法

1、第 5 章 5.1 贪心算法概述贪心算法概述 5.2 贪心算法的理论基础贪心算法的理论基础 5.3 删数字问题删数字问题 5.4 背包问题背包问题 5.5 覆盖问题覆盖问题 5.6 图的着色问题图的着色问题 5.7 遍历问题遍历问题 5.8 最小生成树最小生成树 5.9 哈夫曼编码哈夫曼编码 其他贪心算法： Dijkstra最短路径 5.1.1 贪心算法 找零钱问题，希望用数目最少的硬币找零 假设提供了数目不限的面值为2 5美分、1 0美分、 5美分、及1美分的硬币。 假设需要找6 7美分，25+25+10+5+1+1，共6枚。 假设提供了数目不限的面值为1 1美分、5美分及1 美分的硬币？找

2、零15美分 11+1+1+1+1，共5枚（贪心算法） 5+5+5，共3枚（非贪心算法） 5.1 贪心算法概述贪心算法概述 贪心算法通过一系列的局部选择来得到一个问题的解。所作的每一 个选择都是当前状态下“最优”的选择。 要依照某种策略。策略“只顾眼前，不管将来”，称之为“贪心策 略”。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择 贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是 作一个使局部最优的贪心选择，不断把将问题转化为规模更小的子 问题。 贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上 的局部最优选择。这样处理，对大多数优化问题来说能得到最优解， 但

3、也并不总是这样。 在一些情况下，即使贪心算法不能得到整体最优解，其在一些情况下，即使贪心算法不能得到整体最优解，其 最终结果却是最优解的很好近似。最终结果却是最优解的很好近似。 5.1.2. 贪心算法的基本思想贪心算法的基本思想 贪心算法的基本思想是通过一系列选择步骤来构造问题贪心算法的基本思想是通过一系列选择步骤来构造问题 的解，每一步都是对当前部分解的一个扩展，直至获得问题的解，每一步都是对当前部分解的一个扩展，直至获得问题 的完整解。所做的每一步选择都必须满足：的完整解。所做的每一步选择都必须满足： (1) 可行的：可行的：必须满足问题的约束。必须满足问题的约束。 (2) 局部最优：局部

4、最优：当前所有可能的选择中最佳的局部选择。当前所有可能的选择中最佳的局部选择。 (3) 不可取消不可取消: 选择一旦做出，在后面的步骤中就无法改选择一旦做出，在后面的步骤中就无法改 变了。变了。 贪心算法是通过做一系列的选择来给出某一问题的最优贪心算法是通过做一系列的选择来给出某一问题的最优 解，对算法的每一个决策点，做一个当时（看起来）是最佳解，对算法的每一个决策点，做一个当时（看起来）是最佳 的选择。这种启发式策略并不总是能产生出最优解。的选择。这种启发式策略并不总是能产生出最优解。 例例5.1 5.1 删除数字问题删除数字问题 键盘输入一个高精度的正整数N，去掉其中任意S 个数字后剩下的

5、数字按原左右次序将组成一个新 的正整数。编程对给定的N和S，寻找一种方案使 得剩下的数字组成的新数最小。输出应包括所去 掉的数字的位置和组成的新的正整数(N不超过100 位)。 数据结构设计：将输入的高精度数存储为字符串 格式。 实例(s=3) ： n1=“1 2 4 3 5 8 6 3” 贪心策略 在位数固定的前提下，让高位的数字尽量小其值 就较小； 删除高位较大的数字； 具体地相邻两位比较若高位比低位大则删除高位。 n1=“1 2 4 3 5 8 6 3” 4比3大 删除4 “1 2 3 5 8 6 3” 8比6大 删除8 “1 2 3 5 6 3” 6比3大 删除6 “1 2 3 5 3

6、” 再一个实例： n2=“2 3 1 1 8 3” 3比1大 删除 3 “2 1 1 8 3” 2比1大 删除 2 “ 1 1 8 3” 8比3大 删除 8 “ 1 1 3” 由实例1，相邻数字只需要从前向后比较；而从实 例2中可以看出当第i位与第i+1位比较，若删除第若删除第 i i位后，必须向前考虑第位后，必须向前考虑第i-1i-1位与第位与第i+1i+1位进行比较位进行比较， 才能保证结果的正确性。 n3=”1 2 3 4 5 6 7” s=3 由这个实例看出，经过对n3相邻比较一个数字都没有 删除，这就要考虑将后三位进行删除；当然还有可能， 在相邻比较的过程中删除的位数小于s时，也要进

7、行相 似的操作。 n4=”1 2 0 0 8 3” s=3 2比0大 删除2 “1 0 0 8 3” 1比0大 删除1 “ 0 0 8 3” 8比3大 删除8 “ 0 0 3” 由这个实例子又能看出，当删除掉一些数字后， 结果的高位有可能出现数字“0”，直接输出这个 数据不合理，要将结果中高位的数字“0” 删除 掉，再输出。特别地还要考虑若结果串是“0000” 时，不能将全部“0”都删除，而要保留一个“0” 最后输出。 #includestdio.h #include string.h main() int i,j,k,m,n,x,a200;char b200; gets(b); for (n

8、=0,i=0;bi!=0;i+) n+;ai=bi-48; scanf(%d, i=0;m=0;x=0; while(kx if(ai-1ai) /* 出现递增出现递增,删除递增的首数字删除递增的首数字 */ printf(%d ,ai-1); for(j=i-1;j=n-x-2;j+) aj=aj+1; x=x+1; /* x统计删除数字的个数统计删除数字的个数 */ i=0 ; /* 从头开始查递增区间从头开始查递增区间 */ if(i=n-x-1) m=1; /* 已无递增区间已无递增区间,m=1脱离循环脱离循环 */ printf(n删除后所得最大数删除后所得最大数: ); for(i

9、=1;i=n-k;i+) /* 打印剩下的左边打印剩下的左边n-k个数字个数字 */ printf(%d,ai-1); 例例5.2 5.2 数列极差问题数列极差问题 在黑板上写N个正整数排成一个数列，进行如下操作:每 一次擦去其中的两个数a和b，然后在数列中加入一个数ab+1， 如此下去直至黑板上剩下一个数，在所有按这种操作方式最后 得到的数中，最大的记作max，最小的记作min，则该数列的 极差定义为M=max-min。 如：如： 对三个具体数据对三个具体数据3，5，7讨论，可能有以下三种结果：讨论，可能有以下三种结果： (3*5+1)*7+1=113,(3*7+1)*5+1=111, (5

10、*7+1)*3+1=109 结论：结论：先运算小数据得到的是最大值，先运算大数据得到的先运算小数据得到的是最大值，先运算大数据得到的 是最小值。是最小值。 显然此问题适合用贪婪策略显然此问题适合用贪婪策略, ,不过在求最大值时，要先选择不过在求最大值时，要先选择 较小的数操作。求最小值时，要先选择较大的数操作。这是一较小的数操作。求最小值时，要先选择较大的数操作。这是一 道两次运用贪心策略解决的问题。道两次运用贪心策略解决的问题。 1）不断从现有的数据中，选取最大和最小的两个数，计算后的）不断从现有的数据中，选取最大和最小的两个数，计算后的 结果继续参与运算，直到剩余一个数算法结束。结果继续参

11、与运算，直到剩余一个数算法结束。 2) 选取最大和最小的两个数较高效的算法是用二分法完成，选取最大和最小的两个数较高效的算法是用二分法完成， 这这 里仅用简单的逐个比较方法来求解。注意到由于找到的两个数里仅用简单的逐个比较方法来求解。注意到由于找到的两个数 将不再参与其后的运算，其中一个将不再参与其后的运算，其中一个用它们的计算结果代替用它们的计算结果代替，另，另 一个一个用当前的最后一个数据覆盖用当前的最后一个数据覆盖即可。所以不但要选取最大和即可。所以不但要选取最大和 最小，还必须记录它们的位置，以便将其覆盖。最小，还必须记录它们的位置，以便将其覆盖。 3）求）求max、min过程必须独立

12、，即求过程必须独立，即求max和和min都必须从原始都必须从原始 数据开始数据开始,否则不能找到真正的否则不能找到真正的max和和min。 1)1)由设计由设计2 2）、）、3 3）知，必须用）知，必须用两个数组同时存储初始数据两个数组同时存储初始数据。 2)2)求最大和最小的两个数的函数至少要返回两个数据，方便求最大和最小的两个数的函数至少要返回两个数据，方便 起见用起见用全局变量全局变量实现。实现。 int s1,s2; main() int j,n,a100,b100,max,min; printf(How mang data?); scanf(%d, printf(input thes

13、e data); for (j=1;ja2,令s1=1,s2=2;否则 s1=2,s2=1; 数组再增加一个元素j（下标）时： if (ajas1) s2=s1; s1=j; else if (ajas2) s2=j; max2(int a,int n) int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;jas1) s2=s1; s1=j; else if (ajas2) s2=j; int calculatemin(int a,int n) int j; while (n2) max2(a,n); as1= as1* as2+1;

14、as2=an; n=n-1; return(a1* a2+1); min2(int a ,int n) int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;j=n;j+) if (ajas1) s2=s1; s1=j; else if (aj2) min2(a,n); as1= as1* as2+1; as2=an; n=n-1; return(a1* a2+1); 贪心算法例子：设计一个算法，贪心算法例子：设计一个算法， 把一个真分数表示为埃及把一个真分数表示为埃及 分数之和的形式。所谓埃及分数，是指分子为分数之和的形式。所谓埃及分数

15、，是指分子为1 1的分数。如：的分数。如： 7/8=1/2+1/3+1/24。 基本思想：基本思想：逐步选择分数所包含的最大埃及分数，这些埃及逐步选择分数所包含的最大埃及分数，这些埃及 分数之和就是问题的一个解。分数之和就是问题的一个解。 如：如：7/81/2， 7/8-1/21/3， 7/8-1/2-1/3=1/24。 过程如下：过程如下： 1)1)找最小的找最小的n（最大的埃及分数（最大的埃及分数1/n），使分数），使分数f1/n； 2)2)输出输出1/n； 3)3)计算计算f=f-1/n； 4)4)若此时的若此时的f f是埃及分数，输出是埃及分数，输出f, ,算法结束算法结束, ,否则返

16、回否则返回1）。）。 森林里进行一场装背包比赛： 参加者：黑熊 猴子 啄木鸟 每个比赛者一个背包，背包的载重量为20公 斤。 给定N个物品，每个物品有一定的重量和价值。 20k g 5 .3背包问题 森林里进行一场装背包比赛 规则： 物品可切一部分放入； 背包里装的物品的总重量不超过背 包的载重量； 背包里装的物品的价值最高者获胜。 黑熊 黑瞎子掰棒子的策略：价值高的优先放入。 物品n=3，背包的载重量C=20 各个物品的价值(v1,v2,v3)=(25,24,15) 各个物品的重量( w1,w2,w3)=(18,15,10)。 物品1 物品2 1 2/15 (25,18) (24*2/15,

17、2) 计算器计算器 25+24*(2/15) = 28.2 物品3 物品2 1 2/3 猴子 耍小聪明策略：重量小的优先放入。 物品n=3，背包的载重量C=20 各个物品的价值(v1,v2,v3)=(25,24,15) 各个物品的重量( w1,w2,w3)=(18,15,10)。 计算器计算器 15+24*(2/3) = 31 啄木鸟 算盘子策略：单位重量价值高的优先放入。 物品n=3，背包的载重量C=20 各个物品的价值(v1,v2,v3)=(25,24,15) 各个物品的重量( w1,w2,w3)=(18,15,10) 单位价值 (v1/w1, v2/w2, v3/w3)=(1.39,1.

18、6,1.5) 物品2 物品3 1 1/2 计算器计算器 24+15*(1/2) = 31.5 啄木鸟算盘子策略的时间复杂度? 第一步第一步: :选出单位重量价值最高者装入。选出单位重量价值最高者装入。 n n个中取最大值个中取最大值 第二步第二步：删除该物品。删除该物品。 第三步第三步: :重复重复1,21,2步步, ,直至再装入就超出背包的载重量为止。直至再装入就超出背包的载重量为止。 第四步第四步: :把最后选择物品的一部分装入背包把最后选择物品的一部分装入背包: : 剩余载重量剩余载重量/ /最后选择物品的重量最后选择物品的重量 O(n) O(n2) O(n) 啄木鸟算盘子策略 能否改进

19、? 时间复杂度? 第一步第一步: :按照单位重量价值递减排序。按照单位重量价值递减排序。 n n个数排序个数排序 第二步第二步: :按排序顺序依次装入直至再装入就超出背包的按排序顺序依次装入直至再装入就超出背包的 载重量为止。载重量为止。 第三步第三步: :把最后选择物品的一部分装入背包把最后选择物品的一部分装入背包: : 剩余载重量剩余载重量/ /最后选择物品的重量最后选择物品的重量 O(nlogn) O(nlogn) O(n) 背包问题 该问题就是背包问题： 已知：给定n种物品和一个背包。 物品i重量是Wi，其价值为Vi，背包容量为C。 求解：如何选择装入背包的物品，使得装入背包如何选择装

20、入背包的物品，使得装入背包 中物品总价值最大中物品总价值最大? ? 每个物品xi 可以不被装入背包，也可以部分装入背包, 0 xi1 每个物品的价值和重量值都大于0，总共有n个物 品，vi0，wi0，1in 约束条件:背包载重量是C，因此选入背包中物品 的总重量不得超过C C ni1 i x i w 背包问题的形式化描述背包问题的形式化描述 问题的求解目标:背包中的物品总价值最大。 目标函数: max nii x i v 1 物品可拆背包问题物品可拆背包问题C程序设计代码如下：程序设计代码如下： for(i=1;i=n-1;i+) /* 对对n件物品按单位重量的效益从大到小件物品按单位重量的效

21、益从大到小 排序排序 */ for(j=i+1;j=n;j+) if(pi/wipj/wj) h=pi;pi=pj; pj=h; h=wi;wi=wj; wj=h; cw=c;s=0; /* cw为背包还可装的重量为背包还可装的重量 */ for(i=1;icw) break; xi=1.0; /* 若若w(i)cw,装入一部分装入一部分x(i) */ s=s+pi*xi; No Image printf(装包：装包：); /* 输出装包结果输出装包结果 */ for(i=1;i=n;i+) if(xi0 printf(n 所得最大效益为：所得最大效益为：%7.1f ,s); 二分图是一个无向

22、图，它的二分图是一个无向图，它的n n 个顶点可二分为集个顶点可二分为集 合合A A和集合和集合B B，且同一集合中的任意两个顶点在图中无，且同一集合中的任意两个顶点在图中无 边相连（即任何一条边都是一个顶点在集合边相连（即任何一条边都是一个顶点在集合A A中，另中，另 一个在集合一个在集合B B中）。当且仅当中）。当且仅当B B中的每个顶点至少与中的每个顶点至少与A A 中一个顶点相连时，中一个顶点相连时，A A的一个子集的一个子集A A 覆盖集合覆盖集合B B（或（或 简单地说，简单地说，A A 是一个覆盖）。覆盖是一个覆盖）。覆盖A A 的大小即为的大小即为 A A 中的顶点数目。当且仅

23、当中的顶点数目。当且仅当A A 是覆盖是覆盖B B的子集中的子集中 最小的时，最小的时，A A 为为最小覆盖最小覆盖。 5.4 5.4 覆盖问题覆盖问题 如下图所示：如下图所示：A=1,2,3,4;B=5,6,7,8,9,10,11;选择选择 A 的一个最小覆盖子集的一个最小覆盖子集A，使，使 B中的每个顶点至少与中的每个顶点至少与A 中一个顶点相连。中一个顶点相连。 算法设计如下：算法设计如下： 先构造邻接矩阵，如图先构造邻接矩阵，如图1可以构造如下：可以构造如下： 图图1图图2 计算计算a各个顶点的度，从中选择度最大的顶点，加入各个顶点的度，从中选择度最大的顶点，加入 到子集中，如第一次，

24、各个顶点度为到子集中，如第一次，各个顶点度为4，2，4，2，可，可 以将结点以将结点1加入到子集。加入到子集。 修改邻接矩阵，将结点修改邻接矩阵，将结点1从从a集合中去掉，与集合中去掉，与1所连的所连的 边都抹掉。如图边都抹掉。如图2。 重复上面过程，直到邻接矩阵值都为重复上面过程，直到邻接矩阵值都为0，则找到一组，则找到一组 解，否则失败。解，否则失败。 该算法的时间复杂度取决于数据的存储方式，若使该算法的时间复杂度取决于数据的存储方式，若使 用邻接矩阵，则需花用邻接矩阵，则需花(n2 ) 的时间来寻找图中的边，的时间来寻找图中的边， 若用邻接链表，则需若用邻接链表，则需(n+e) 的时间。

25、故覆盖算法总的时间。故覆盖算法总 的复杂性为的复杂性为O( n2)或或O (n +e) 1、 活动安排问题 活动安排问题就是要在活动安排问题就是要在所给的活动集合中选所给的活动集合中选 出最大的相容活动子集合，出最大的相容活动子集合，是可以用贪心算法有是可以用贪心算法有 效求解的很好例子。该问题要求高效地安排一系效求解的很好例子。该问题要求高效地安排一系 列争用某一公共资源的活动。贪心算法提供了一列争用某一公共资源的活动。贪心算法提供了一 个简单、漂亮的方法使得尽可能多的活动能兼容个简单、漂亮的方法使得尽可能多的活动能兼容 地使用公共资源地使用公共资源。 5.5 5.5 图的着色问题图的着色问

26、题 设有设有n n个活动的集合个活动的集合E=1,2,E=1,2,n,n，其中每个，其中每个 活动都要求使用同一资源，如演讲会场等，而在活动都要求使用同一资源，如演讲会场等，而在 同一时间内只有一个活动能使用这一资源。同一时间内只有一个活动能使用这一资源。 每个活动每个活动i i都有一个要求使用该资源的时间都有一个要求使用该资源的时间si, fi) ： （起始时间（起始时间s si，结束时间，结束时间f fi, ,且且s si f fi ）。）。 若区间若区间ssi, f, fi) )与区间与区间ssj, f, fj) )不相交，则称活动不相交，则称活动i i 与活动与活动j j是是相容的相容

27、的。也就是说，当。也就是说，当s siffj或或s sjffi时，时， 活动活动i i与活动与活动j j相容。相容。 例：例：设待安排的设待安排的1111个活动的开始时间和结束个活动的开始时间和结束 时间按结束时间的非减序排列如下：时间按结束时间的非减序排列如下： i12345678910 11 Si 130535688212 fi45678910 11 12 13 14 由于输入的活动以其完成时间的由于输入的活动以其完成时间的非减序非减序排列，排列， 所以算法所以算法greedySelectorgreedySelector每次总是选择每次总是选择具有最早完具有最早完 成时间成时间的相容活动加

28、入集合的相容活动加入集合A A中。中。直观上，按这种直观上，按这种 方法选择相容活动为未安排活动留下尽可能多的时方法选择相容活动为未安排活动留下尽可能多的时 间。间。也就是说，该算法的贪心选择的意义是也就是说，该算法的贪心选择的意义是使剩余使剩余 的可安排时间段极大化的可安排时间段极大化，以便安排尽可能多的相容，以便安排尽可能多的相容 活动。活动。 算法算法greedySelectorgreedySelector的效率极高。当输入的活的效率极高。当输入的活 动已按结束时间的非减序排列，算法只需动已按结束时间的非减序排列，算法只需O(n)O(n)的时的时 间安排间安排n n个活动，使最多的活动能

29、相容地使用公共个活动，使最多的活动能相容地使用公共 资源。如果所给出的活动未按非减序排列，可以用资源。如果所给出的活动未按非减序排列，可以用 O(nlogn)O(nlogn)的时间重排。的时间重排。 若被检查的活动若被检查的活动i i的开始时间的开始时间S Si i小于最近选择的小于最近选择的 活动活动j j的结束时间的结束时间f fi i，则不选择活动，则不选择活动i i，否则选择，否则选择 活动活动i i加入集合加入集合A A中。中。 贪心算法并不总能求得问题的贪心算法并不总能求得问题的整体最优解整体最优解。 但对于活动安排问题，贪心算法但对于活动安排问题，贪心算法greedySelect

30、orgreedySelector 却总能求得的整体最优解，即它最终所确定的相却总能求得的整体最优解，即它最终所确定的相 容活动集合容活动集合A A的规模最大。这个结论可以用数学归的规模最大。这个结论可以用数学归 纳法证明。纳法证明。 void GreedySelector(int n, Type s, Type f, int A) A1=1; int j=1; for (int i=2;i=fj) Ai=1; j=i; else Ai=0; 下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector : 各活动的起始时间和结各活动的起始时间和结 束时间存储于数组束

31、时间存储于数组s s和和f f 中且按结束时间的非减中且按结束时间的非减 序排列序排列 2 2、多机调度问题、多机调度问题 多机调度问题多机调度问题要求给出一种作业调度方案，使 所给的n个作业在尽可能短的时间内由m台机器加 工处理完成。 这个问题到目前为止还没有有效的解法。对于 这一类问题,用贪心选择策略贪心选择策略有时可以设计出较好 的近似算法。 约定，每个作业均可在任何一台机器上加工处约定，每个作业均可在任何一台机器上加工处 理，但未完工前不允许中断处理。作业不能拆分成理，但未完工前不允许中断处理。作业不能拆分成 更小的子作业。更小的子作业。 采用采用最长处理时间作业优先最长处理时间作业优

32、先的贪心选择策略的贪心选择策略 可以设计出解多机调度问题的较好的近似算法。可以设计出解多机调度问题的较好的近似算法。 按此策略，当按此策略，当 时，只要将机器时，只要将机器i的的0, ti时时 间区间分配给作业间区间分配给作业i即可，算法只需要即可，算法只需要O(1)时间。时间。 当当 时，首先将时，首先将n个作业依其所需的处理个作业依其所需的处理 时间时间从大到小从大到小排序。然后排序。然后依此顺序将作业分配给依此顺序将作业分配给 空闲的处理机空闲的处理机。算法所需的计算时间为。算法所需的计算时间为O(nlogn)。 mn mn 例例: :设设7 7个独立作业个独立作业1,2,3,4,5,6

33、,71,2,3,4,5,6,7由由3 3台机器台机器M1M1，M2M2和和M3M3 加工处理。各作业所需的处理时间分别为加工处理。各作业所需的处理时间分别为 2,14,4,16,6,5,32,14,4,16,6,5,3。按算法。按算法greedygreedy产生的作业调度如下产生的作业调度如下 图所示，所需的加工时间为图所示，所需的加工时间为1717。 排序后：排序后： 4(16), 2(14), 5(6), 6(5), 3(4), 7(3),1(2), 4(16), 2(14), 5(6), 6(5), 3(4), 7(3),1(2), 3 3、地图的着色（、地图的着色（4 4色）色） 定理

34、定理：任何平面地图可以使用：任何平面地图可以使用4 4种颜色给每个不同种颜色给每个不同 的城市着色，而保证相邻的城市着不同的颜色的城市着色，而保证相邻的城市着不同的颜色 思路思路：把地图上的每个城市抽象为一个点，并给：把地图上的每个城市抽象为一个点，并给 每个城市编号，相邻的城市之间用直线连接。每个城市编号，相邻的城市之间用直线连接。 据此做出邻接矩阵，若第据此做出邻接矩阵，若第i i个城市与第个城市与第j j个城市相个城市相 邻，则邻，则metroij=1,metroij=1,否则否则metroij=0metroij=0。 算法算法：按照编号从小到大的顺序检查每个城市，：按照编号从小到大的顺

35、序检查每个城市， 对每个城市从对每个城市从1 1到到4 4使用使用4 4种颜色着色，若当前颜色种颜色着色，若当前颜色 可用（即不与相邻城市颜色相同），则着色；否可用（即不与相邻城市颜色相同），则着色；否 则测试下一种颜色则测试下一种颜色。 void color(int metroNN,int r_colorN,int sum) int i,j,k; for(i=1;i=sum;i+)/*检查所有城市检查所有城市*/ for(j=1;j=4;j+)/*对每个城市尝试对每个城市尝试4种颜色的着色方案种颜色的着色方案 */ r_colori=j;/*尝试着色尝试着色*/ for(k=1;ki;k+)/*检查是否与相邻城市颜色相同检查是否与相邻城市颜色相同*/ if(metroik=1/*相同则跳出，此时有相同则跳出，此时有k=i)/*若不相同，则使用当前颜色，并检查下一个若不相同，则使用当前颜色，并检查下一个 城市城市*