tailieunhanh - Thuật toán Algorithms (Phần 54)

Tham khảo tài liệu 'thuật toán algorithms (phần 54)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | EXHAUSTIVE SEARCH 523 process node x visit x then visit each son of x applying this visiting procedure recursively and returning to node x after each son has been visited ending up at node x. This tour traverses every edge in the spanning tree twice so its cost is twice the cost of the tree. It is not a simple tour since a node may be visited many times but it can be converted to a simple tour simply by deleting all but the first occurrence of each node. Deleting an occurrence of a node corresponds to taking a shortcut past that node certainly it can t increase the cost of the tour. Thus we have a simple tour which has a cost less than twice that of the minimum spanning tree. For example the following diagram shows a minimum spanning tree for our set of sample points computed as described in Chapter along with a corresponding simple tour. This tour is clearly not the optimum because it self-intersects. For a large random point set it seems likely that the tour produced in this way will be close to the optimum though no analysis has been done to support this conclusion. Another approach that has been tried is to develop techniques to improve an existing tour in the hope that a short tour can be found by applying such improvements repeatedly. For example if we have as above a Euclidean traveling salesman problem where graph distances are distances 524 CHAPTER 39 between points in the plane then a self-intersecting tour can be improved by removing each intersection as follows. If the line AB intersects the line CD the situation can be diagramed as at left below without loss of generality. But it follows immediately that a shorter tour can be formed by deleting AB and CD and adding AD and CB as diagramed at right Applying this procedure successively will given any tour produce a tour that is no longer and which is not self-intersecting. For example the procedure applied to the tour produced from the minimum spanning tree in the example above gives the shorter tour .