Travelling salesman problem
Author Message
Travelling salesman problem

Check out the topic "dynamic programming".  The TSP is an optimization
problem.  Doing an exhaustive search would be very "suboptimal" in terms
of computational efficiency.

Mon, 21 Jul 2008 03:53:37 GMT
Travelling salesman problem
| By the way, can anyone think of a compact method of checking all the N!
| possible routes (obviously for small N), where N = number of cities?
|
| The way I'm thinking of at the moment requires N nested do loops, which
| will be quite clumsy to write up.

There are several ways to emulate N nested to-loops without writing them
down explicitly. Here's one:

iCounter(1:nLoops) = 1
Outmost:     &
do while(.TRUE.)
IndLoop=2
do j=1,iEndLoop(1)
!Inmost code here
end do

!Increasing indices of outer loops:
do while(.TRUE.)

iCounter(IndLoop)=iCounter(IndLoop)+1

if(iCounter(IndLoop) .LE. iEndLoop(IndLoop)) then
!This one did not hit the limit
exit
else
!Limit is hit; Increase outer loop
iCounter(IndLoop)=1
IndLoop=IndLoop+1
if(IndLoop .GT. nLoops) exit Outmost !Terminal condition
end if
end do
end do Outmost

Obviously, iEndLoop contains loop trips, 1 denoting the inmost;
iCounter contains actual states of loop variables. If you're looping
through N! combinations, you should set iEndLoop to (/(k, k=1,n)/)
(I guess, lazy to really check out :-) ).

Recursion is another way to do it.

--
Jugoslav
___________
www.xeffort.com

Mon, 21 Jul 2008 16:14:57 GMT
Travelling salesman problem
Another way of several ways to emulate N do loops:
http://ftp.cac.psu.edu/pub/ger/fortran/hdk/loopnest.f90

Skip Knoble

-|| By the way, can anyone think of a compact method of checking all the N!
-|| possible routes (obviously for small N), where N = number of cities?
-||
-|| The way I'm thinking of at the moment requires N nested do loops, which
-|| will be quite clumsy to write up.
-|
-|There are several ways to emulate N nested to-loops without writing them
-|down explicitly. Here's one:
-|
-|      iCounter(1:nLoops) = 1
-|      Outmost:     &
-|      do while(.TRUE.)
-|        IndLoop=2
-|        do j=1,iEndLoop(1)
-|            !Inmost code here
-|        end do
-|
-|        !Increasing indices of outer loops:
-|        do while(.TRUE.)
-|
-|          iCounter(IndLoop)=iCounter(IndLoop)+1
-|
-|          if(iCounter(IndLoop) .LE. iEndLoop(IndLoop)) then
-|             !This one did not hit the limit
-|             exit
-|          else
-|             !Limit is hit; Increase outer loop
-|             iCounter(IndLoop)=1
-|             IndLoop=IndLoop+1
-|             if(IndLoop .GT. nLoops) exit Outmost !Terminal condition
-|          end if
-|        end do
-|      end do Outmost
-|
-|Obviously, iEndLoop contains loop trips, 1 denoting the inmost;
-|iCounter contains actual states of loop variables. If you're looping
-|through N! combinations, you should set iEndLoop to (/(k, k=1,n)/)
-|(I guess, lazy to really check out :-) ).
-|
-|Recursion is another way to do it.

Mon, 21 Jul 2008 21:46:20 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages