ダイクストラの最短経路アルゴリズムなどでは、エッジを調べてノードへのより良いパスを提供するかどうかを確認することを、エッジの緩和と呼びます。なぜリラックスと呼ばれるのですか？
9518 次
2 に答える
42
一般に、数学的には、緩和は制約を減らす変更を加えています。ダイクストラアルゴリズムがエッジを調べるとき、プールからエッジを削除し、それによって制約の数を減らします。
それはひどく有用な用語ではありませんが、それを言ってどれほどクールに聞こえるかを考えてください。
于 2012-05-24T23:58:51.293 に答える
2
この質問は、現在受け入れられている回答で話されている数学的概念に関連しているとは思いません。私の答えは、コーメン（CLRS）の本の第2版、特にリラクゼーションに関するセクションの第24章に基づいています。
コンテキスト：ノードと他のすべてのノード間の最短パスを検索しています。2つのノードuとvがあるとします。あなたはすでに彼らのための中間の道を持っています。
Relax（u、v）は、「 relax vusingu」と読み替える必要がある関数です。私はこの関数を「 uを使用してvの距離をsに短縮する」と理解することを好みます。あなたはそれをsuvに変換することを支持してあなたの現在のパスsvをあきらめるべきかどうかあなた自身に尋ねています。suの距離と矢印uvの追加コストが距離svよりも優れているかどうかを確認するために必要なことはすべてあります。写真は機能を例示しています
于 2018-06-06T03:27:40.270 に答える