0

I am writing code to address the Nurse Restoring Problem

I have implemented Simulated Annealing and I am interested in comparing the results to Late Acceptance Hill Climbing

I have found some pseudo code for Late Acceptance but need a little help to write it in 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

I really don't get this bit: For all k in ( 0.. L-1 ) C_hat[k]=C(s)

The pseudo code is from http://www.yuribykov.com/LAHC/LAHC_wonders.pdf

4

1 回答 1

1

我正在in为关系的“元素”和C_hat[k]顶部带有“帽子”和下标 k 的 C 写作，因为这些东西在这种格式下显示效果不佳。

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出现时，最新的解决方案只需比之前尝试的 index 更好v，即使该提议的解决方案非常糟糕。这似乎不对。我想知道该行是否实际上应该是该then子句的一部分，只有在解决方案被接受时才执行。

于 2014-07-29T17:30:00.790 回答