- #1
steve22
- 4
- 0
Hi Guys
I like to know how can a problem like the travling salesman be tackled. I have made some notes below about tackling TSP problems but can someone confirm to me have I said the right things and is there any other way u can tackle the TSP
The traveling salesman can be tackled using Greedy Algorithm, Constraint Satisfaction Algorithms. A Greedy Algorithm works in stages. At each stage. You take the best at that particular state without regard to the future. The hope is that by choosing the best local decision it will lead to the best global solution.
Another way to tackle the traveling salesman is using the Constraint Satisfaction problem(CSP) Sometimes there may be many solutions that satisfy all the constraints but each solution has a different cost associated with it. In that case a solution is required that not only satisfies all the constraints but also minimizes the cost of the solution this is how CSP is used . A Constraint Satisfaction Problem is characterized by a set of variables {x1, x2, .., xn}. for each variable xi a domain Di with the possible values for that variable. Here are some simple examples of constraint satisfaction problems. CSP can be solved by a variety of search algorithms.
Standard Backtracking is used to generate solutions by checking that the constraints are satisfied as we assign the values. If a situation is reached when no valid assignment can be made to a variable then the algorithm “backtracks” to the previous node in the search tree and tries a different assignment.
Backtracking with Forward Checking works by checking each variable not already assigned to see if it has at least one value that satisfies the constraints. This is called a choice point. Once a value is assigned it reduces the domain of values that can be validly assigned to other variables.
Generalised Forward Checking involves assigning variables out of turn in the situation where the domain of the variable has been reduced to only one possible value. In this situation the variable is assigned and the domains of other unassigned variables are further reduced.
I like to know how can a problem like the travling salesman be tackled. I have made some notes below about tackling TSP problems but can someone confirm to me have I said the right things and is there any other way u can tackle the TSP
The traveling salesman can be tackled using Greedy Algorithm, Constraint Satisfaction Algorithms. A Greedy Algorithm works in stages. At each stage. You take the best at that particular state without regard to the future. The hope is that by choosing the best local decision it will lead to the best global solution.
Another way to tackle the traveling salesman is using the Constraint Satisfaction problem(CSP) Sometimes there may be many solutions that satisfy all the constraints but each solution has a different cost associated with it. In that case a solution is required that not only satisfies all the constraints but also minimizes the cost of the solution this is how CSP is used . A Constraint Satisfaction Problem is characterized by a set of variables {x1, x2, .., xn}. for each variable xi a domain Di with the possible values for that variable. Here are some simple examples of constraint satisfaction problems. CSP can be solved by a variety of search algorithms.
Standard Backtracking is used to generate solutions by checking that the constraints are satisfied as we assign the values. If a situation is reached when no valid assignment can be made to a variable then the algorithm “backtracks” to the previous node in the search tree and tries a different assignment.
Backtracking with Forward Checking works by checking each variable not already assigned to see if it has at least one value that satisfies the constraints. This is called a choice point. Once a value is assigned it reduces the domain of values that can be validly assigned to other variables.
Generalised Forward Checking involves assigning variables out of turn in the situation where the domain of the variable has been reduced to only one possible value. In this situation the variable is assigned and the domains of other unassigned variables are further reduced.