olzsilk.blogg.se

More precisely, such an algorithm exists if and only if the two computational classes P and NP coincide, a very improbable hypothesis, according to the last years research developments. Hence, an efficient algorithm for TSP (that is, an algorithm computing, for any TSP instance with m nodes, the tour of least possible cost in polynomial time with respect to m) probably does not exist. Actually, TSP belongs to the NP-hard class. Among them, TSP is one of the most important, since it is very easy to describe, but very difficult to solve. TSP is a representative of a large class of problems known as combinatorial optimization problems.

More formally, a TSP instance is given by a complete graph G on a node set V=, for some integer m, and by a cost function assigning a cost cij to the arc (i,j), for any i, j in V. Thus, which is the tour of least possible cost the salesman can take? The Traveling Salesman Problem (for short, TSP) was born. He knows the cost of traveling from any city i to any other city j. A traveling salesman has to visit exactly once each one of a list of m cities and then return to the home city. In these years the Austrian mathematician Karl Menger invited the research community to consider from a mathematical point of view the following problem taken from the every day life. Actually, fundamental concepts, such as ‘algorithm’, or ‘computational problem’, has been formalized just some year before. Travelling Salesman Problem, Federico Greco Preface In the middle 1930s computer science was yet a not well defined academic discipline. 111225072 Travelling Salesman Problem, Edited by Federico Greco p. © 2008 In-teh Additional copies can be obtained from: First published September 2008 Printed in Croatia A catalogue record for this book is available from the University Library Rijeka under no. After this work has been published by the In-Teh, authors have the right to republish it, in whole or part, in any publication of which they are an author or editor, and the make other personal use of the work. Publisher assumes no responsibility liability for any damage or injury to persons or property arising out of the use of any materials, instructions, methods or ideas contained inside. No responsibility is accepted for the accuracy of information contained in the published articles. Statements and opinions expressed in the chapters are these of the individual contributors and not necessarily those of the editors or publisher.

Abstracting and non-profit use of the material is permitted with credit to the source. Travelling Salesman Problem Travelling Salesman Problem Edited by Federico Greco I-Tech IV Published by In-Teh In-Teh is Croatian branch of I-Tech Education and Publishing KG, Vienna, Austria.