4

7つの都市A、B、C、D、E、F、Gが与えられ、開始状態がABCDEFGAで、コストが「x」であるとしましょう。このノードの子がどうなるかわかりません。山登りアルゴリズムの2回目の反復は続行されますか？

開始状態であるノードABCDEFGAには6つの子がありますか？のように

2番目の反復はACBDEFGA、ADCBEFGA、AECDBFGA、AFCDEBGA、AGCDEFBAですか？

3回目の反復： 2回目の反復でADCBEFGAが選択されたとすると、3回目の反復では、都市「C」を他のすべての都市と交換することになりますか？

アルゴリズムの理解が正しいかどうかを知りたいだけです。

4

1 に答える 1

6

Hill Climbing アルゴリズムは、局所的な最適値を見つけるのに優れており、現在の状態の小さな部分を変更してより良い (この場合はより短い) パスを取得することで機能します。

より良い解決策を見つけるために小さな変更をどのように実装するかは、あなた次第です。単純に 2 つのノードを切り替えて、現在のソリューションよりも優れている場合にのみ結果を保持するとします。

2 番目の町を他の町と交換するだけで、次のようになります。

# first iteration
start: ABCDEFGA
next: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA

# second iteration
start: ADCBEFGA
next: ACDBEFGA, ABCDEFGA, AECBDFGA, AFCBEDGA, AGCBEFDA

これらの可能性のそれぞれの適合性をチェックし、最良のものを保持する必要があります。次に、次の可能性がどれも現在の状態より良くなるまで繰り返します。反復ごとに同じアルゴリズムを継続的に使用する必要があります。

最初の繰り返しで 2 番目の都市、2 番目の反復で 3 番目の都市、3 番目の反復で 4 番目の都市を切り替えることができます。1 つのスポットに固執し、別のスポットと交換することをお勧めしますが、最終的には、これにどのように取り組んでも、さまざまな次善の答えが得られることになります。

于 2013-02-20T02:29:00.833 に答える