Solved

Travelling salesman problem- 1 city can be visited more than once

Posted on 2005-04-09
331 Views
Question-

How to solve the travelling salesman problem without the restriction of not visiting a city more then once-

Given a weighted graph, the starting node(sn), and a set of nodes(S) to visit. Find a route starting from and ending at (sn) and covering all nodes in S. One node can be visited more than once.

Plz let me know the algorithm(clearly) at the earliest......(it is easy but urgent)...
0
Question by:ManiBhushan Kumar
1 Comment

LVL 3

Accepted Solution

Some Links for ur reference for the Alogorithm

http://www.codeproject.com/cpp/tspapp.asp
http://www.pcug.org.au/~dakin/tspbb.htm
http://ai-depot.com/Articles/51/TSP.html

For Quick Reference:

The Metropolis algorithm ..., developed to simulate the behaviour of atoms in thermal equilibrium at a particular temperature, begins with an initial configuration with energy E0. Each subsequent iteration involves performing a small random perturbation to the current configuration i (with associated energy Ei), then the energy, Ej, of the resulting configuration j is calculated. If the change in energy E'' = Ej - Ei <= 0, the configuration j is accepted with probability 1 and becomes the current configuration of the next iteration. If E'' > 0, then configuration j is accepted with probability exp(- E''/kT), with the aim of obtaining a Boltzman distribution. If configuration j is rejected the current configuration i remains unchanged. After a large number of iterations the accepted configurations approximate a Boltzman distribution at a particular temperature, T.

0

Featured Post

Suggested Solutions

format the code in java 6 60
only14 challenge 19 57
factorial example challenge 10 44
changeXy challenge 13 40
RIA (Rich Internet Application) tools are interactive internet applications which have many of the characteristics of desktop applications. The RIA tools typically deliver output either by the way of a site-specific browser or via browser plug-in. T…
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!