Constraint Satisfaction

JCW2
JCW2 used Ask the Experts™
on
I'm a student and don't expect an immediate answer. I'm primarily looking at part C. Can you clarify how this works?
Problem1.PNG
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Commented:
It's the famous so called "Traveling Salesman Problem":
http://www.trinidadstate.edu/mathsci/csc/csc238/graphs/g.html

Under the above link you can find explanations and demos of algorithms...

ozo
Most Valuable Expert 2014
Top Expert 2015
Commented:
Hamiltonian Tour is not quote the same as Traveling Salesman.
Traveling Salesman requires finding the shortest Hamiltonian Path,
whereas Hamiltonian Tour only needs to find one such path.

However, any general algorithm for solving one can be polynomially transformed into an algorithm for solving the other.

Author

Commented:
Could you explain how to connect Hamiltonian tours to constraint satisfaction and/or clarify constraint satisfaction?

Author

Commented:
Thank you for your help.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial