Jeff Edmonds によるテキスト「アルゴリズムについて考える方法」には、Network Flows and Linear Programming の章に Primal-Dual Hill Climbing を説明するセクションがあります。指数関数的な数の屋根と、なぜ「最も低く、したがって最適な屋根が最も高く、したがって最適な場所の上にある」のかを視覚化するのに苦労しています。
1 に答える
0
これが正しいかどうかは 100% 確信が持てませんが、これが私の見解でした。ナビゲートしている特定の丘陵地のトポロジーが与えられた場合、その鏡像が上空に浮かんでいると想像してください。最も高い丘の頂上が伸び、空から伸びている鏡の一番下の谷の底に接触します。逆に、一番下の谷に移動すると、ミラー イメージで真上にあるポイントとの距離が最大になります。本ではあまり説明されていませんが、この鏡像は本で言及されている「指数屋根」です。
とにかく、この鏡像は、あなたが世界最大値に達したことを証明するための基礎として使用されます. 直観的に証明が言っていることは、まず第一に、鏡像は元の問題の別の例であり、ちょうど逆になっているということです. ただし、上空の鏡像の存在により、ローカル最大値とグローバル最大値を区別できます。特定のピークに到達しても、空の「ミラー ピーク」に頭がぶつからない場合は、極大値に達しています。一方、ピークがその鏡像に対して突き出ているために立つ余地がない場合は、グローバルな最大値に達したことがわかります.
本の元の説明に戻ると、著者が「指数関数的屋根」と表現しているものは、ガゼボがたくさんある一連の丘のように聞こえたので、問題があると思いますが、それは正しくありません. より良い説明は、お互いを正確に反映する石筍と鍾乳石の洞窟です。
于 2013-05-22T23:46:23.750 に答える