Алгоритм альпинизма на поздней стадии принятия

Question

Я пишу код для решения проблемы восстановления медсестры

Я внедрил имитацию отжига и мне интересно сравнить результаты с Late Acceptance Hill Climbing

Я нашел псевдокод для позднего принятия, но мне нужна небольшая помощь, чтобы написать его на Java:

Produce an initial solution s
Calculate initial cost function C(s)
Set the initial number of steps I=0
For all k in ( 0.. L-1 ) C_hat[k]=C(s)
Do until a stopping condition
 Construct a candidate solution s*
 Calculate its cost function C(s*)
 v = I mod L
 If C(s*) <= C_hat[v]
 Then accept s*
 Insert cost value into the list C_hat[v] = C(s)
 Increment a number of steps I=I+1
End do

Я действительно не понимаю это немного: For all k in ( 0.. L-1 ) C_hat[k]=C(s)

Псевдокод взят с http://www.yuribykov.com/LAHC/LAHC_wonders.pdf

Answer 1

Я пишу in для отношения "элемент" и C_hat[k] для C с "шляпкой" сверху и индексом k, так как эти вещи не очень хорошо отображаются в этом формате.

For all k in ( 0.. L-1 ) C_hat[k]=C(s)

Цель этой строки в том, что в остальной части алгоритма вы предполагаете, что можете принять любое значение v В диапазоне 0 в L-1 и проверить, If C(s*) <= C_hat[v], Это не имеет смысла, если C_hat[v] уже определено. приведенная выше строка гарантирует, что каждый такой C_hat[v] имеет четко определенное значение, прежде чем пытаться использовать это значение.

Это также означает, что вы никогда не примете решение, худшее, чем первое, которое вы попробовали.

---

Кстати, я с подозрением отношусь к тому, как в исходном документе написана следующая строка:

Insert cost value into the list C_hat[v] = C(s)

Основываясь на форматировании алгоритма в исходном документе, я бы пришел к выводу, что эта операция должна выполняться на каждой итерации цикла, независимо от того, принято новое решение или нет. В следующий раз индекс v самое новое решение должно быть только лучше, чем ранее пробованное для индекса vдаже если это предложенное решение было ужасно плохим. Это не кажется правильным. Интересно, должна ли эта линия быть частью then пункт, подлежащий исполнению только в том случае, если решение принято.