《用遗传算法求解TSP问题(共22页).doc》由会员分享，可在线阅读，更多相关《用遗传算法求解TSP问题(共22页).doc（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上用遗传算法求解TSP问题遗传算法（Genetic AlgorithmGA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的。J.Holland教授和它的研究小组围绕遗传算法进行研究的宗旨有两个：抽取和解释自然系统的自适应过程以及设计具有自然系统机理的人工系统。遗传算法的大致过程是这样的：将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，即给出一个适应度值。开始时，总是随机的产生一些个体，根据这些个体的适应度，利用遗传
2、算子选择（Selection）、交叉（Crossover）、变异（Mutation）对它们重新组合，得到一群新的个体。这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化。遗传算法主要的特点在于：简单、通用、鲁棒性强。经过二十多年的发展，遗传算法已经在旅行商问题、生产调度、函数优化、机器学习等领域得到成功的应用。 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染
3、色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3、 遗传算法使用多个点的搜索信息，具有隐含并行性。4、 遗传算法使用概率搜索技术，而非确定性规则。遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法步骤：1、创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样；在那里，问题的初始状态已经给定了。2、评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近
4、求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。3、繁殖(包括子代突变)带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。4、下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代地演化下去，直到达到期望的解为止。5、并行计算非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同
5、的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。6、术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，以下是我们将会涉及到的一些术语： 染色体(Chromosome)染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。 基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S01234，则其中
6、的1，0，2，3这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 基因地点(Locus)基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S12043 中，0的基因位置是3。 基因特征值(Gene Feature)在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。不过本程序的基因无特征值； 适应度(Fitness)各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能
7、力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。遗传算法中，针对三种遗传算子可进行如下的遗传操作。 一、选择算子 从群体中选择优胜的个体，淘汰劣质个体的操作叫做选择。选择算子又叫再生算子（Reproduction Operator）。选择的目的是把优化的解直接遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有： 1适应度比例方法（Fitness proportional model） 适应度比例方法是目前遗传算法中最基本最常用的选择方法。它也叫赌轮（roulet
8、te wheele）或蒙特卡罗（Monte Carlo）选择。 设群体大小为,其中个体的适应度值为,则被选择的概率为:可见反映了个体的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，被选择的概率就越高。2最佳个体保存方法（Elitist model） 此方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。采用这种选择方法的优点是：进化过程中某一代的最优解可以不被交叉和变异操作所破坏。但是，这是这样可能隐含了一种危机导致早熟，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解。也就是说，该方法的全局搜索能力不强，它更加适合于单峰性质的搜索空间搜索。一般将
9、这种方法与其它一些选择操作配合起来使用，才能有良好的效果。 另外，最佳个体保存方法还可加以推广，即在每一代的进化过程中保留多个最优个体不参加交叉、变异等遗传操作，而直接将它们复制到下一代群体中。这种选择方法也称为稳态复制。 3排序选择方法（Rank-based）排序选择方法是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按顺序分配给个体，作为各自的选择概率。这种方法的不足之处在于选择概率和序号的关系必须事先确定。此外，它和适应度比例方法一样都是一种基于概率的选择，所以仍然有统计误差。 此外还有一些比较常用的选择方法如期望值方法（Expected val
10、ue model）、联赛选择方法（Tournament selection model）等。二、 交叉算子 1交叉算子的设计 实现个体结构重组的交叉算子设计一般与所求解的具体问题有关，一般包括以下一些要点： 任何交叉算子需要满足交叉算子的评估准则，就是说交叉算子需要保证前一代中优秀个体的性状能在后一代的新个体中尽可能得到遗传和继承。 交叉设计和编码设计是相互联系的。也就是说，交叉算子设计和编码设计需协调操作。这也就是所谓的编码交叉设计。 2基本的交叉算子 一点交叉（One point crossover） 一点交叉又叫做简单交叉。具体的操作是：在个体串中随机设定一个交叉点，实行交叉的时候，该点
11、前或后的两个个体的部分结构进行互换，并生成两个新的个体。如下图所示：图2.1一点交叉 二点交叉（Two point crossover） 二点交叉与一点交叉类似，只是设值2个交叉点（随机设定），如下图所示：图2.2 二点交叉 一致交叉（Uniform crossover） 一致交叉是指通过设定屏蔽字（mask）来决定新个体的基因继承两个旧个体中哪个个体的对应基因。如下图所示：图2.3 一致交叉 算术交叉（Arithmetic Crossover） 算术交叉是指由两个个体的线性组合而产生出两个新的个体。为了能够进行线性组合运算，算术交叉的操作对象一般是由浮点数编码所表示的个体。假设在两个个体，之
12、间进行算术交叉，则交叉运算后所产生出的两个新个体是：其中，是一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术交叉。3交叉算子与遗传算法的收敛型 遗传算法的收敛性不仅取决于编码，初始化群体，适应度函数，选择算子的设计，而且还取决于交叉算子和下面要提到的变异算子。但是，遗传算法的收敛性主要决定于作为其核心操作的交叉算子。交叉算子收敛性是遗传算法研究中最重要的课题之一。需要指出的是，交叉算子并未提供收敛性保证。 三、变异算子 变异操作的基本内容是对群体中的个体串的某些基因座上的基因值作变动。例如，基于字符集0，1的
13、二值码串，变异操作就是把1变成0或者把0变成1。变异操作的步骤为：在群体中所有个体的码串范围内随机的确定基因座，然后以事先设定的变异概率对这些基因座的基因值进行变异。如下图所示：图2.4 简单位变异遗传算法引入变异的目的有两个：一个是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解临近值时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。这种情况下变异概率应取较小值，否则已经接近最优解的值会因为变异而遭到破坏。二是使遗传算法可以维持群体多样性，以防止出现早熟现象。 遗传算法中，交叉算子因为其全局搜索能力作为主要算子，变异算子因其局部搜索能力作为辅助算子。遗传算法通过
14、交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。遗传算法在组合优化中有着许多重要而且成功的应用实例，这里只涉及到了最典型的旅行商问题(TSP问题)。旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中的著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 。即寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X= 1,2,n的一个排列，使得取最小值。其中表示城市i到的距离。TSP问题
15、是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。遗传算法求解可以得到问题的最优解，且算法简单，对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。我将用遗传算法来求解一个简单的TSP问题，其中基因是n个城市的排列顺序,适应度应该是城市之间的距离总和，将距离作为权值。算法求解的问题就是对总距离最小的访问城市的路径排序。得到最短访问路径适应函数的最优排序。本例中，首先以十进制方式对遍历29个城市的次序排列进行编码，例如码串表示从城市1开始，依次经过城市2，3，4，5，
16、6，7，8，最后返回城市1的遍历路径，这是一种针对TSP问题的最自然的编码方式。其边权值如下所示：/* 0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167 107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 374 171 259 509 317
17、217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175 307 57 220 121 97 8
18、0 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435 76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 344 289 177 216 141
19、346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111 157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 365 159 0 404 176 106
20、 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297 234 391 107 322 33
21、1 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 118 62 92 277 55 155
22、275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 66 178 112 0 128 167
23、 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 412 193 103 428 230 4
24、4 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 221 251 424 137 307 3
25、01 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 149 290 80 41 147 265
26、 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0*/对此29个城市的访问，要求每个城市都只能访问一次，并且最后要回到原来出发的城市。将以上29个城市之间的代号和距离权值用一个的数组matri
27、xmaxstringmaxstring进行存储和初始化。接着在此基础上定义适应度函数。适应度函数通常取路径长度的倒数，即。如果结合TSP的约束条件（比如每个城市经过且只经过一次），则适应度函数可表示成为。其中是对TSP路径不合法的度量（比如取为未遍历的城市的个数），为惩罚系数，可以是距离的倍数。然后进行遗传算子的设计：以n个城市的遍历次序作为遗传算法的编码，因为在各种遗传操作中都隐含了TSP问题的合法性约束条件（例如，每个城市经过且经过一次），所以适应度函数取哈密而顿长度的倒数。 采用赌轮选择机制。一开始用随机方法产生初始群体。随着遗传算法的执行，则保留M个教优的个体作为群体。在每一代运算过程
28、中，个体被选中的概率与其在群体中的相对适应度成正比。 交叉方法采用改进的OX方法，这种方法的好处是，在两个父代串相同的情况下仍能产生一定程度的变异效果，这对维持群体内一定的多样化特性有一定的作用。变异方法采用“逆转”与下山方法相结合的操作，称为“进化逆转”，主要目的是改善遗传算法的局部搜索能力。在基本遗传算法操作中，交叉操作在可行解空间中动作范围较宽，步伐较大，导致变异操作受“选择”压力的作用，难以发挥局部搜索的功效。因此，在遗传算法框架中加入适当的、基于邻域的局部搜索机制，构成一种全局搜索和局部搜索相结合的优化搜索算法。下山方法就是一种很好的局部搜索方法。这里，定义一次“逆转”为进入一个解的
29、邻居，则进化逆转就是一个单方向的（朝着改进方向的深度下山）和连续的“逆转”操作。若“逆转”使可行解的适应度提高，则继续执行逆转，如此反复直到适应度不再提高（这就是典型的下山过程）。这一操作可以得到较好的效果。 将此算法编程实现，可得到如下的算法描述和流程框图：TSPSTART数据初始化与内存空间分配；gen = 0；初始化路径群体；适应度统计；显示初始路径；dogen = gen + 1；选择操作；交叉操作；变异操作；适应度统计；显示中间结果；while(不满足停止条件)将计算结果写入文件；内存空间释放；END实验分析此问题即一个TSP问题,其中事件间相当于一个偏序集,解方法可以用递归和回溯法
30、,时间复杂度比较复杂.用遗传算法求解时，问题是要得到基因的一个序列与前面的不同，所以要在基因进行交叉和变异之后要进行基因序列的休整，使得整个基因序列保持完整，休整方法就是对重复基因进行更换。用遗传算法求解问题时,很容易将问题限于局部忧化。本程序代码在C-Free 3.5下编译通过，谢谢老师审阅！附录：代码/*/*TSP write by LJ */*/#include #include #include #include #include #define maxpop 100#define maxstring 29struct individual unsigned int chrommaxs
31、tring;float x,fitness;int parent2;int xsite;struct individual *oldpop; /* 当前代种群 */struct individual *newpop; /* 新一代种群 */struct individual *temp,*p1; unsigned int co_min,jrand;unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;float sumfitness,avg,max,min,seed,maxold,oldrandmaxstring;unsigned cha
32、r xmaxstring,ymaxstring;float *dd,ff,maxdd,refpd,fm201;/以下为29个城市的边权值/* 0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167 107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 3
33、74 171 259 509 317 217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175
34、307 57 220 121 97 80 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435 76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 3
35、44 289 177 216 141 346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111 157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 36
36、5 159 0 404 176 106 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297
37、 234 391 107 322 331 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 11
38、8 62 92 277 55 155 275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 6
39、6 178 112 0 128 167 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 41
40、2 193 103 428 230 44 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 22
41、1 251 424 137 307 301 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 14
42、9 290 80 41 147 265 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0*/static int matrixmaxstringmaxstring=0,107,241,190,
43、124,80,316,76,152,157,283,133,113,297,228,129,348,276,188,150,65,341,184,67,221,169,108,45,167,107,0,148,137,88,127,336,183,134,95,254,180,101,234,175,176,265,199,182,67,42,278,271,146,251,105,191,139,79,241,148,0,374,171,259,509,317,217,232,491,312,280,391,412,349,422,356,355,204,182,435,417,292,42
44、4,116,337,273,77,190,137,374,0,202,234,222,192,248,42,117,287,79,107,38,121,152,86,68,70,137,151,239,135,137,242,165,228,205,124,88,171,202,0,61,392,202,46,160,319,112,163,322,240,232,314,287,238,155,65,366,300,175,307,57,220,121,97,80,127,259,234,61,0,386,141,72,167,351,55,157,331,272,226,362,296,2
45、32,164,85,375,249,147,301,118,188,60,185,316,336,509,222,392,386,0,233,438,254,202,439,235,254,210,187,313,266,154,282,321,298,168,249,95,437,190,314,435,76,183,317,192,202,141,233,0,213,188,272,193,131,302,233,98,344,289,177,216,141,346,108,57,190,245,43,81,243,152,134,217,248,46,72,438,213,0,206,3
46、65,89,209,368,286,278,360,333,284,201,111,412,321,221,353,72,266,132,111,157,95,232,42,160,167,254,188,206,0,159,220,57,149,80,132,193,127,100,28,95,193,241,131,169,200,161,189,163,283,254,491,117,319,351,202,272,365,159,0,404,176,106,79,161,165,141,95,187,254,103,279,215,117,359,216,308,322,133,180,312,287,112,55,439,193,89,220,404,0,210,384,325,279,415,349,285,217,