Devise a hill climbing search based approach to solve N-city TSPs. You must defi

Question

Devise a hill climbing search based approach to solve N-city TSPs. You must define all required elements to be able to implement the hill climbing search as indicated in the pseudocode of this algorithm including the state description (representation of the problem), the initial state, the successor function and applicable actions, the goal test or the goal state, and the heuristic function h. Strive for an evaluation or heuristic function definition that facilitates optimal solutions. Describe the pseudocode for the hill climbing algorithm adapted for the TSP. There is no need to implement the search algorithm.

Explanation / Answer

Function HILL-CLIMBING(Problem) returns a solution state
Inputs: Problem, problem
Local variables: Current, a node
Next, a node
Current = MAKE-NODE(INITIAL-STATE[Problem])
Loop do
Next = a highest-valued successor of Current
If VALUE[Next] < VALUE[Current] then return Current
Current = Next
End

The Hill Climbing algorithm is great for finding local optima and works by changing a small part of the current state to get a better (in this case, shorter) path.

implement the small changes to find a better solution is up to us. Let's say we want to simply switch two nodes and only keep the result if it's better than your current solution.

Just swapping the second town with some other town gives us the following:

we would want to check the fitness of each of these possibilities and keep the best one. Then reiterate until none of the next possibilities are better than your current state. We'll want to continually use the same algorithm for each iteration.

we can switch the second city on the first iteration, the third on the second, the fourth on the third, etc. but make sure we loop back around and continue this style of swapping and don't stop when we reach the end.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.