作业选答：

习题一

习题四

1.某邮递员的投递范围如下图所示，A点表示邮局所在地。试设计一条最短投递路线，并求其长度。

                                      图8.6

 解：利用口诀：

(1)奇点：B,C,E,F,G,H,J,K

(2)奇点对对连，得到图8.7：

                                        图8.7

(3)检查上图中每一个圈，重复边的长度均不超过半圈长。

   再利用弗莱里算法求得的欧拉环游即最优环游为：ABCDHGHLKGCBFEIJKJFEA.

返回

4.某车站货场的货位及货运办公室A布置如图，试为货运员设计一个巡视图，以保证对每个货位的货物四周   都能进行检查，并要求行走的路程最短。

                                     图8.8

解：依据题意，即求图8.9从A点出发的最优环游：

                                     图8.9

   利用口诀：

(1)奇点：B,C,E,H,I,L,N,O;

(2)奇点对对连，得到图8.10：     

                                    图8.10

 (3)检查上图中每一个圈，重复边的长度均不超过半圈长。

    注意：有人在做题中添重复边如下图：

                                 图8.11

   这样添重复边不是最优的，奇偶点做图法要求图中每一个圈其重复边的长度和不超过半圈长。在上图中有一个圈不满足，就是最大的的那个圈ADPMA，其重复边的长度和为60m，该圈的总长为90，，因而这样添重复边的方法是错误的。

最后利用弗莱里算法，我们可以设计这样一个巡视图： ABCDHLHGFEIJKLPOKGCBFJNONMIEA.

返回

【关闭】