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「の要素」リレーションと、「帽子」を上に付け、添字 k を付けた C について書いてC_hat[k]います。これらはこの形式ではうまく表示されないためです。

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

この行の目的は、アルゴリズムの残りの部分で、 ～ の範囲内の任意の値を取り、 かどうかをテストできると仮定するvことです。がすでに定義されていない限り、これは意味がありません。上記の行により、その値を使用する前に、そのようなすべての値が明確に定義されていることが保証されます。0L-1If 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 に答える