近似度の下限
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 10:13 UTC 版)
「クリストフィードのアルゴリズム」の記事における「近似度の下限」の解説
クリストフィードのアルゴリズムの近似度を3/2まで限りなく近づけることができる頂点集合が存在する。そのような1つの入力はn個の頂点によって形成される道に対し、1つの頂点まで辺の重みを1とし、道において2辺分離れた頂点を結ぶ辺の重みを1 + εとし（但し、εは限りなく0に近い正の数とする）、残りの完全グラフの辺の重みは既に定義された部分グラフの最短経路の重みの和とする。このグラフで形成される最小全域木が重み1のn − 1本の辺を持ち、ただ2つの奇数次の頂点を持つ。そしてその奇数次の頂点の最適マッチングは重みおよそn/2の1本の辺によって構築される。最小全域木と最適マッチングの辺を統合した経路は単純閉路であるため、近道は存在せず、重みの和はおよそ3n/2となる。 しかし、最適解は重み1 + εのn-2本の辺と、道の端点の辺である重み1の2本の辺によって構成されるため、重みの和はn + (n − 2)εとなり、εが十分小さい場合nに近づく。したがって、近似度は3/2となる場合が存在する。
※この「近似度の下限」の解説は、「クリストフィードのアルゴリズム」の解説の一部です。
「近似度の下限」を含む「クリストフィードのアルゴリズム」の記事については、「クリストフィードのアルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「近似度の下限」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 近似度の下限のページへのリンク
