乡村邮差问题哈林图.docx

封面组合优化课程论文报告题 目： Halin图上求解乡村邮差问题 院 系： 信息科学与技术学院计算机系 专 业： 计算机科学与技术 学生姓名： 庞宇明 学 号： 14212949 二一五年 六 月目录封面iHalin图上求解乡村邮差问题3想法：3一、若H是一个轮51.1、H不存在内边在E中61.2、H有且只有一条内边在E中71.3、H有且只有两条内边在E中81.4、H中存在三条或以上内边在E中8二、若H不是一个轮102.1、扇F中不存在内边在E中102.1.1、E中所有边均在扇F中102.1.2、E中只有部分或没有边在扇F中122.2、扇F中有且只有一条内边在E中132.2.1、若ru0,ui和rui,ur均无定义132.2.2、若ru0,ui有定义，而rui,ur无定义142.2.3、若ru0,ui无定义，而rui,ur有定义162.2.4、若ru0,ui和rui,ur均有定义162.3、扇F中有且只有两条内边在E中192.3.1、若rui,uj无定义192.3.2、若rui,uj有定义，ru0,ui或ruj,ur无定义202.3.3、若rui,uj，ru0,ui，ruj,ur均有定义212.4、扇F中有三条或以上内边在E中22三、O（N2）复杂度降为O(N)复杂度23Halin图上求解乡村邮差问题实例：图G=(V,E),每条边长度为l(e)为正整数，子集E含于E，界B为给定正整数。问：G中是否有一个圈包含E中的每一条边，并且总长度不超过B?题目：设计一个多项式时间（O(n)时间）的算法，在赋权Halin图上求解乡村邮差问题。想法：分情况讨论，首先是最简单轮的情况，分别是不存在内边在E中；有且只有一条内边在E中；有且只有两条内边在E中；有三条或以上内边在E中。然后是非轮的情况，即存在扇的情况。分别是扇不存在内边在E中；有且只有一条内边在E中；有且只有两条内边在E中；有三条或以上内边在E中。求出的最小圈（若存在）的长度如果比B小则存在。主体是参照在halin图上求解TSP问题的算法的思想，不过乡村邮差问题复杂很多，但并不是很难，公式也不复杂。主要还是把情况分得更细，把问题想得更全面。重点是收缩扇的处理，收缩后边权值的变化和E的变化，权值的变化很好地借鉴了在halin图上求解TSP问题的算法的思想。整个过程是递归的过程，递归的终止状态就是轮，把问题递归回去求解。中间有个过程是O（N2）,就是寻找扇或者圈经过内点的最短路径，但通过处理就变成了O（N）时间复杂度，整个算法是O(N)时间复杂度的。以下对赋权Halin图上的乡村邮差问题在多项式时间内进行的求解。设H=（V,E）是一个赋权Halin图，伴随圈为C。一、若H是一个轮如图1.1所示，其中，设H的伴随圈为C。u3u4u2u1u0ur-1urur+1ur+2un-1unv图1.1令wC= i=0n-1w(ui,ui+1)+w(u0,un)令ruj,uk表示在伴随圈C上从uj到uk不经过E中边的最长路径，若该路径不存在，则 ruj,uk无定义。假设jk，则ruj,uk的求解如下(对kj同理)：若路径ujuj+1uk-1uk中不包含E中的边，路径ukuk+1un-1unu0uj-1uj中包含E中的边，则ruj,uk= i=jk-1w(ui,ui+1)；若路径ujuj+1uk-1uk中包含E中的边，路径ukuk+1un-1unu0uj-1uj中不包含E中的边，则ruj,uk= i=kn-1w(ui,ui+1)+ i=0j-1w(ui,ui+1)+w(u0,un)；若路径ujuj+1uk-1uk中不包含E中的边，路径ukuk+1un-1unu0uj-1uj中也不包含E中的边，则ruj,uk= maxi=kn-1w(ui,ui+1)+ i=0j-1w(ui,ui+1)+w(u0,un), i=jk-1w(ui,ui+1)；若路径ujuj+1uk-1uk中包含E中的边，路径ukuk+1un-1unu0uj-1uj中也包含E中的边，则ruj,uk无定义。1.1、H不存在内边在E中如图1.2所示，虚线为E中的边，以下相同。此时可以有两种走法，一种是只经过H的伴随圈C，一种是经过中心点v。求得最小圈C=wC+min0,min0ijn且rui,uj有定义wui,v+wuj,v-rui,uju3u4u2u1u0ur-1urur+1ur+2un-1unv图1.21.2、H有且只有一条内边在E中如图1.3所示。u3u4u2u1u0ur-1urur+1ur+2un-1unv图1.3此时必经过中心点v，假设这条内边为uiv。求得最小圈C=wC+wui,v+min0jn且ji且rui,uj有定义wuj,v-rui,uj若是不存在j使得0jn且ji且rui,uj有定义，则最小圈不存在。1.3、H有且只有两条内边在E中如图1.4所示。u3u4u2u1u0ur-1urur+1ur+2un-1unv图1.4此时必经过中心点v，假设这两条内边为uiv和ujv,若是rui,uj无定义，则无解。否则，最小圈C=wC+wui,v+ wuj,v-rui,uj1.4、H中存在三条或以上内边在E中如图1.5u3u4u2u1u0ur-1urur+1ur+2un-1unv图1.5二、若H不是一个轮则H中含有一个扇F，如图2.1所示。图2.1u0u1ur-1urjklwF令wCF=i=0r-1w(ui,ui+1)，令rui,uj(0ijr)表示路径uiui+1uj-1uj的长度，若路径uiui+1uj-1uj包含E中的边，则rui,uj无定义。2.1、扇F中不存在内边在E中则Cjk=wCF+min0ir且rui,ur有定义wui,w-rui,urCkl=wCF+min0ir且ru0,ui有定义wui,w-ru0,uiCjl=wCF+min0ijr且rui,uj有定义wui,w+wuj,w-rui,uj2.1.1、E中所有边均在扇F中如图2.2所示。图2.2u0u1ur-1urjklwF此时最小圈有两种可能的存在情况，或者在扇F的内部，或者需要经过H除扇F中的边外其它的边。在扇F内部求出一个最小圈C1= wCF+min0ijr且ru0,ui和ruj,ur有定义wui,w+wuj,w-ruo,ui-ruj,ur将扇F收缩，得到新的Halin图H，则H中各边的权重重新计算如下：le=le,若eEHj,k,llj+12Cjk+Cjl-Ckl,e=jlk+12Cjk+Ckl-Cjl,e=kll+12Cjl+Ckl-Cjk,e=l之后分别令E=j,k,j,l,k,l，对应递归求解出在H上的最小圈C2，C3，C4。则原图H上的最小圈C=minC1,C2,C3,C4。2.1.2、E中只有部分或没有边在扇F中如图2.3所示。图2.3u0u1ur-1urjklwF此时最小圈不可能在F内部，因此直接收缩扇F，得到新的Halin图H，则H中各边的权重重新计算如下：le=le,若eEHj,k,llj+12Cjk+Cjl-Ckl,e=jlk+12Cjk+Ckl-Cjl,e=kll+12Cjl+Ckl-Cjk,e=l之后分别令E=Ej,k,Ej,l,Ek,l，递归对应求解出在H上的最小圈C1，C2，C3。则原图H上的最小圈C=minC1,C2,C3。2.2、扇F中有且只有一条内边在E中设该内边为uiw2.2.1、若ru0,ui和rui,ur均无定义如图2.4所示。图2.4u0u1ur-1urjklwF此时最小圈必须经过扇外其它边才可能存在，且不可能经过边k。令minji=min0ji且ruj,ui有定义wuj,w-ruj,ui令minij=minijr且rui,uj有定义wuj,w-rui,uj若minji和minij均无定义，则无解。否则，令Cjl=wCF+wui,w+minminji,minij收缩扇F，得到新的Halin图H，此时H中各边权重重新计算如下：le=le,若eEHj,llj+12Cjl,e=jll+12Cjl,e=l然后令E=Ej,l，在H上递归求得的最小圈即为在原图H上的最小圈。2.2.2、若ru0,ui有定义，而rui,ur无定义如图2.5所示。图2.5u0u1ur-1urjklwF令minji=min0jiwuj,w-ruj,ui令minij=minijr且rui,uj有定义wuj,w-rui,uj令Cjl=wCF+wui,w+minminji,minij令Ckl=wCF+wui,w-ru0,uiA. 若E中所有边均在扇F中如图2.6所示。图2.6u0u1ur-1urjklwF此时最小圈的求解有两种可能，一种是最小圈在扇F内部，一种是最小圈需要经过扇F外部的边。在扇F内求出一个最小圈C1= wCF+wui,w+minijr且ruj,ur有定义wuj,w-ruj,ur收缩扇F，得到新的Halin图H,各边权重重新计算如下:le=le,若eEHj,k,llj+12Cjl-Ckl,e=jlk+12Ckl-Cjl,e=kll+12Cjl+Ckl,e=l分别令E=j,l,k,l,在H上递归求得最小圈为C2和C3。则原Halin图H的最小圈为C=minC1,C2, C3。B. 若E只有部分边在扇F中如图2.5所示。此时最小圈必须经过扇F外部的边。收缩扇F，得到新的Halin图H,各边权重重新计算如下：le=le,若eEHj,k,llj+12Cjl-Ckl,e=jlk+12Ckl-Cjl,e=kll+12Cjl+Ckl,e=l分别令E=j,l,k,l,在H上递归求得最小圈为C1和C2。则原Halin图H的最小圈为C=minC1,C2。2.2.3、若ru0,ui无定义，而rui,ur有定义类似2.2.2可求得最小圈。2.2.4、若ru0,ui和rui,ur均有定义如图2.7所示。图2.7u0u1ur-1urjklwF令minji=min0jiwuj,w-ruj,ui令minij=minijrwuj,w-rui,uj令Cjk=wCF+wui,w-rui,ur令Cjl=wCF+wui,w+minminji,minij令Ckl=wCF+wui,w-ru0,ui收缩扇F，得到新的Halin图H，各边权重重新计算如下：le=le,若eEHj,k,llj+12Cjk+Cjl-Ckl,e=jlk+12Cjk+Ckl-Cjl,e=kll+12Cjl+Ckl-Cjk,e=l分别令E=Ej,k,Ej,l,Ek,l，递归对应求解出在H上的最小圈C1，C2，C3。A. 若E中所有边均在扇F中如图2.8所示。图2.8u0u1ur-1urjklwF则原图H的最小圈有两种可能情况，一种是最小圈在扇F内部，一种是最小圈需要经过扇F外部。在扇F内部求解最小圈为C4=wCF+wui,w+min0ji或ijrwuj,w-ru0,uminj,i-r(umaxj,i,ur)则原图H的最小圈为C=minC1,C2,C3,C4。B. 若E只有部分边在扇F中如图2.7所示。则原图H的最小圈为C=minC1,C2,C3。2.3、扇F中有且只有两条内边在E中设该内边为uiw和ujw,不妨设ij。2.3.1、若rui,uj无定义如图2.9所示。图2.9u0u1ur-1urjklwF此时若是ru0,ui或ruj,ur无定义或者E有部分边在扇F外，如图2.10所示，则显然问题无解。否则，原图H的最小圈在扇F内部，最小圈C=wCF+wui,w+wuj,w-ru0,ui-r(uj,ur)图2.10u0u1ur-1urjklwF2.3.2、若rui,uj有定义，ru0,ui或ruj,ur无定义如图2.11所示。图2.11u0u1ur-1urjklwF此时Halin图H在E上的最小圈必须经过扇F外部。令Cjl=wCF+wui,w+wuj,w-r(ui,uj)收缩扇F，得到新的Halin图H,则各边权重重新定义如下：le=le,若eEHj,llj+12Cjl,e=jll+12Cjl,e=l令E=Ej,l,在H上递归求得的最小圈即为原图H的最小圈。2.3.3、若rui,uj，ru0,ui，ruj,ur均有定义如图2.12所示。图2.12u0u1ur-1urjklwF令Cjl=wCF+wui,w+wuj,w-rui,uj收缩扇F，得到新的Halin图H,则各边权重重新定义如下：le=le,若eEHj,llj+12Cjl,e=jll+12Cjl,e=l令E=Ej,l,在H上递归求得最小圈C1。A. 若E的所有边均在扇F中则H的最小圈有两种存在的可能情况，一种是最小圈在扇F内部，一种是最小圈需要经过扇F外部。在扇F内部求得最小圈C2=wCF+wui,w+wuj,w-ru0,ui-ruj,ur则图H的最小圈C=minC1,C2。B. 若E有部分边在扇F外部则H的最小圈必须经过扇F的外部。则图H的最小圈C=C1。2.4、扇F中有三条或以上内边在E中问题无解。三、O（N2）复杂度降为O(N)复杂度可以看出O（N2）的式子有：C=wC+min0,min0ijn且rui,uj有定义wui,v+wuj,v-rui,uj （1）Cjl=wCF+min0ijr且rui,uj有定义wui,w+wuj,w-rui,uj （2）C1= wC