Hill Climbing Search Algorithm Applies to Traveling Salesmen
Let's say we are given 7 cities A, B, C, D, E, F, G and we have an initial state ABCDEFGA with some value "x", I don't understand what the children of this node would be It would be interesting how the second one will continue an iteration of the mountaineering algorithm?
Will node ABCDEFGA, which is the initial state, have 6 children? As in the case
second iteration should be ACBDEFGA, ADCBEFGA , AECDBFGA, AFCDEBGA, AGCDEFBA?
The third iteration: . Suppose ADCBEFGA is selected in the second iteration, and then will the third iteration exchange city "C" with all other cities, etc.?
I just would like to know if I understand the algorithm correctly.
source to share
Hill Climbing 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.
How you implement small changes to find the best solution is up to you. Let's say you just want to switch two nodes and only keep the result if it's better than your current solution.
Simply switching a second city to another city gives you the following:
# first iteration
start: ABCDEFGA
next: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA
# second iteration
start: ADCBEFGA
next: ACDBEFGA, ABCDEFGA, AECBDFGA, AFCBEDGA, AGCBEFDA
You would like to test the suitability of each of these possibilities and keep the best. Then repeat until none of the following is better than your current condition. You want to constantly use the same algorithm for each iteration.
You can switch the second city to the first iteration, the third to the second, the fourth to the third, and so on, but make sure you go back and continue with this swap style and don't stop when you reach the end. I suggest sticking to one place and changing place elsewhere, but you end up with different suboptimal responses no matter how you deal with it.
source to share