Complexity and Routing Problems
-
Hello, I know that the Traveling Salesman Problem has a solution space of (n-1)! / 2 for n = nodes, when the symetrick TSP is considered. But, is there any mathematical way to show how big a solution space a Arc Routing Problem, like the Capacitated Arc Routing Problem have? Or any other way to show (describe) why ít is a complex problem? In all the literature it is only described as NP-hard, and thats it. Thanks
-
Hello, I know that the Traveling Salesman Problem has a solution space of (n-1)! / 2 for n = nodes, when the symetrick TSP is considered. But, is there any mathematical way to show how big a solution space a Arc Routing Problem, like the Capacitated Arc Routing Problem have? Or any other way to show (describe) why ít is a complex problem? In all the literature it is only described as NP-hard, and thats it. Thanks
The standard way to show a problem is NP is to show that it reduces to a known NP problem. In other words, you show transformations (which must run in P (polynomial) time) that transform any instance of the problem to an instance of a known NP problem.
-
The standard way to show a problem is NP is to show that it reduces to a known NP problem. In other words, you show transformations (which must run in P (polynomial) time) that transform any instance of the problem to an instance of a known NP problem.
If you are interested in image processing, you might want to take a look at this http://www.youtube.com/watch?v=euHMcUfqpVo[^] :)
“Everything is simple when you take your time to analyze it.”