https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_%28%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE%29
マッチング (平面上の) - 版の履歴
2026-04-16T20:29:51Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_(%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE)&diff=6999&oldid=prev
Orsjwiki: "マッチング (平面上の)" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T01:56:32Z
<p>"マッチング (平面上の)" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 01:56時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_(%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE)&diff=4998&oldid=prev
2007年7月16日 (月) 10:34に122.17.2.240による
2007-07-16T10:34:06Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月16日 (月) 10:34時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>【まっちんぐ (matching in the plane)】</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''</ins>【まっちんぐ (matching in the plane)】<ins class="diffchange diffchange-inline">'''</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>与えられた平面上の<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>の手間で解ける.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>与えられた平面上の<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>の手間で解ける.</div></td></tr>
</table>
122.17.2.240
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_(%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE)&diff=4737&oldid=prev
2007年7月14日 (土) 07:05に222.225.128.87による
2007-07-14T07:05:48Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月14日 (土) 07:05時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【まっちんぐ (matching in the plane)】</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【まっちんぐ (matching in the plane)】</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>与えられた平面上の<del class="diffchange diffchange-inline">$</del>n=2m<del class="diffchange diffchange-inline">$</del>個の点集合に対して, 2点ずつペアにして<del class="diffchange diffchange-inline">$</del>m<del class="diffchange diffchange-inline">$</del>個のペアの集合(完全マッチング)<del class="diffchange diffchange-inline">$</del>M<del class="diffchange diffchange-inline">$</del>を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング<del class="diffchange diffchange-inline">$</del>M<del class="diffchange diffchange-inline">$</del>の重みを<del class="diffchange diffchange-inline">$</del>M<del class="diffchange diffchange-inline">$</del>に含まれる<del class="diffchange diffchange-inline">$</del>m<del class="diffchange diffchange-inline">$</del>個のペアの重みの総和として, 重みを最小にする完全マッチング<del class="diffchange diffchange-inline">$</del>M^*<del class="diffchange diffchange-inline">$</del>を見つける問題を平面最小重み完全マッチングという. この問題は<del class="diffchange diffchange-inline">$</del>\mbox{O}(n^3)<del class="diffchange diffchange-inline">$</del>の手間で解けるが, バケット法に基づけば近似的に<del class="diffchange diffchange-inline">$</del>\mbox{O}(n)<del class="diffchange diffchange-inline">$</del>の手間で解ける.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>与えられた平面上の<ins class="diffchange diffchange-inline"><math></ins>n=2m<ins class="diffchange diffchange-inline">\,</math></ins>個の点集合に対して, 2点ずつペアにして<ins class="diffchange diffchange-inline"><math></ins>m<ins class="diffchange diffchange-inline">\,</math></ins>個のペアの集合(完全マッチング)<ins class="diffchange diffchange-inline"><math></ins>M<ins class="diffchange diffchange-inline">\,</math></ins>を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング<ins class="diffchange diffchange-inline"><math></ins>M<ins class="diffchange diffchange-inline">\,</math></ins>の重みを<ins class="diffchange diffchange-inline"><math></ins>M<ins class="diffchange diffchange-inline">\,</math></ins>に含まれる<ins class="diffchange diffchange-inline"><math></ins>m<ins class="diffchange diffchange-inline">\,</math></ins>個のペアの重みの総和として, 重みを最小にする完全マッチング<ins class="diffchange diffchange-inline"><math></ins>M^*<ins class="diffchange diffchange-inline">\,</math></ins>を見つける問題を平面最小重み完全マッチングという. この問題は<ins class="diffchange diffchange-inline"><math></ins>\mbox{O}(n^3)<ins class="diffchange diffchange-inline">\,</math></ins>の手間で解けるが, バケット法に基づけば近似的に<ins class="diffchange diffchange-inline"><math></ins>\mbox{O}(n)<ins class="diffchange diffchange-inline">\,</math></ins>の手間で解ける.</div></td></tr>
</table>
222.225.128.87
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_(%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE)&diff=4129&oldid=prev
122.17.2.240: 新しいページ: '【まっちんぐ (matching in the plane)】 与えられた平面上の$n=2m$個の点集合に対して, 2点ずつペアにして$m$個のペアの集合(完全マッチ...'
2007-07-13T03:05:21Z
<p>新しいページ: '【まっちんぐ (matching in the plane)】 与えられた平面上の$n=2m$個の点集合に対して, 2点ずつペアにして$m$個のペアの集合(完全マッチ...'</p>
<p><b>新規ページ</b></p><div>【まっちんぐ (matching in the plane)】<br />
<br />
与えられた平面上の$n=2m$個の点集合に対して, 2点ずつペアにして$m$個のペアの集合(完全マッチング)$M$を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング$M$の重みを$M$に含まれる$m$個のペアの重みの総和として, 重みを最小にする完全マッチング$M^*$を見つける問題を平面最小重み完全マッチングという. この問題は$\mbox{O}(n^3)$の手間で解けるが, バケット法に基づけば近似的に$\mbox{O}(n)$の手間で解ける.</div>
122.17.2.240