「マッチング (平面上の)」の版間の差分
ナビゲーションに移動
検索に移動
| 1行目: | 1行目: | ||
| − | 【まっちんぐ (matching in the plane)】 | + | '''【まっちんぐ (matching in the plane)】''' |
与えられた平面上の<math>n=2m\,</math>個の点集合に対して, 2点ずつペアにして<math>m\,</math>個のペアの集合(完全マッチング)<math>M\,</math>を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング<math>M\,</math>の重みを<math>M\,</math>に含まれる<math>m\,</math>個のペアの重みの総和として, 重みを最小にする完全マッチング<math>M^*\,</math>を見つける問題を平面最小重み完全マッチングという. この問題は<math>\mbox{O}(n^3)\,</math>の手間で解けるが, バケット法に基づけば近似的に<math>\mbox{O}(n)\,</math>の手間で解ける. | 与えられた平面上の<math>n=2m\,</math>個の点集合に対して, 2点ずつペアにして<math>m\,</math>個のペアの集合(完全マッチング)<math>M\,</math>を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング<math>M\,</math>の重みを<math>M\,</math>に含まれる<math>m\,</math>個のペアの重みの総和として, 重みを最小にする完全マッチング<math>M^*\,</math>を見つける問題を平面最小重み完全マッチングという. この問題は<math>\mbox{O}(n^3)\,</math>の手間で解けるが, バケット法に基づけば近似的に<math>\mbox{O}(n)\,</math>の手間で解ける. | ||
2007年7月16日 (月) 19:34時点における版
【まっちんぐ (matching in the plane)】
与えられた平面上の個の点集合に対して, 2点ずつペアにして個のペアの集合(完全マッチング)を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチングの重みをに含まれる個のペアの重みの総和として, 重みを最小にする完全マッチングを見つける問題を平面最小重み完全マッチングという. この問題はの手間で解けるが, バケット法に基づけば近似的にの手間で解ける.
