C++ Neural Networks and Fuzzy Logic: Preface

C++ Neural Networks and Fuzzy Logic

by Valluru B. Rao

MTBooks, IDG Books Worldwide, Inc.

ISBN: 1558515526   Pub Date: 06/01/95

Previous Table of Contents Next

Traveling Salesperson Problem

The traveling salesperson problem is well−known in optimization. Its mathematical formulation is simple, and

one can state a simple solution strategy also. Such a strategy is often impractical, and as yet, there is no

efficient algorithm for this problem that consistently works in all instances. The traveling salesperson problem

is one among the so− called NP−complete problems, about which you will read more in what follows. That

means that any algorithm for this problem is going to be impractical with certain examples. The neural

network approach tends to give solutions with less computing time than other available algorithms for use on

a digital computer. The problem is defined as follows. A traveling salesperson has a number of cities to visit.

The sequence in which the salesperson visits different cities is called a tour. A tour should be such that every

city on the list is visited once and only once, except that he returns to the city from which he starts. The goal is

to find a tour that minimizes the total distance the salesperson travels, among all the tours that satisfy this

criterion.

A simple strategy for this problem is to enumerate all feasible tours—a tour is feasible if it satisfies the

criterion that every city is visited but once—to calculate the total distance for each tour, and to pick the tour

with the smallest total distance. This simple strategy becomes impractical if the number of cities is large. For

example, if there are 10 cities for the traveling salesperson to visit (not counting home), there are 10! =

3,628,800 possible tours, where 10! denotes the factorial of 10—the product of all the integers from 1 to

10—and is the number of distinct permutations of the 10 cities. This number grows to over 6.2 billion with

only 13 cities in the tour, and to over a trillion with 15 cities.