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

Please reply to the newsgroup.
You can find my real e-mail on my home page above.



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  
 
 [ 3 post ] 

 Relevant Pages 

1. TSP (Travelling Salesman Problem)

2. Travelling Salesman Problem

3. TRAVELLING SALESMAN PROBLEM & VEHICLE ROUTING

4. Travelling Salesman Problem

5. Travelling Salesman problem

6. solving travelling salesman using FPGA

7. Travelling Salesman algorithm.

8. Travelling Salesman

9. Traveling salesman problem

10. Trvaelleing Salesman Problem

11. Blind Traveling Salesman Problem in StarLogo

12. Traveling Salesman problem

 

 
Powered by phpBB® Forum Software