割当問題 - 版の履歴

2008年11月14日 (金) 00:55にAlbeit-Kunによる

2008-11-14T00:55:28Z

2007年10月13日 (土) 15:50にSakasegawaによる

2007-10-13T15:50:51Z

Orsjwiki: "割当問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T00:49:18Z

"割当問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 04:27に122.17.2.240による

2007-07-17T04:27:34Z

2007年7月11日 (水) 08:33に211.9.146.139による

2007-07-11T08:33:44Z

2007年7月11日 (水) 08:32に211.9.146.139による

2007-07-11T08:32:38Z

2007年7月11日 (水) 08:29に211.9.146.139による

2007-07-11T08:29:33Z

122.17.2.240: 新しいページ: ''''【わりあてもんだい (assignment problem)】''' $|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与...'

2007-07-09T06:03:38Z

新しいページ: ''''【わりあてもんだい (assignment problem)】''' $|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与...'

新規ページ

'''【わりあてもんだい (assignment problem)】'''

$|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与えられたときに, 枝の重みの和 $\sum_{a \in M}w(a)$ を最大にする完全マッチング $M \subseteq A$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

← 古い版		2008年11月14日 (金) 00:55時点における版
2行目:		2行目:

	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.		<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.
		+
		+	[[Category:グラフ･ネットワーク\|わりあてもんだい]]

← 古い版		2007年10月13日 (土) 15:50時点における版
1行目:		1行目:
	'''【わりあてもんだい (assignment problem)】'''		'''【わりあてもんだい (assignment problem)】'''

−	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, ~~最小費用流問題の特殊ケースと見ることもできる~~. この問題に対し, 効率的な多項式時間解法が数多く提案されている.	+	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

← 古い版		2007年7月17日 (火) 04:27時点における版
1行目:		1行目:
	'''【わりあてもんだい (assignment problem)】'''		'''【わりあてもんだい (assignment problem)】'''

−	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.	+	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

← 古い版		2007年7月11日 (水) 08:33時点における版
1行目:		1行目:
	'''【わりあてもんだい (assignment problem)】'''		'''【わりあてもんだい (assignment problem)】'''

−	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \~~mathin~~ A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.	+	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

← 古い版		2007年7月11日 (水) 08:32時点における版
1行目:		1行目:
	'''【わりあてもんだい (assignment problem)】'''		'''【わりあてもんだい (assignment problem)】'''

−	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.	+	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \mathin A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

← 古い版	2007年7月20日 (金) 00:49時点における版
(相違点なし)

← 古い版		2007年7月11日 (水) 08:29時点における版
1行目:		1行目:
	'''【わりあてもんだい (assignment problem)】'''		'''【わりあてもんだい (assignment problem)】'''

−	$\|V^+\| = \|V^-\|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与えられたときに, 枝の重みの和 $\sum_{a \in M}w(a)$ を最大にする完全マッチング $M \subseteq A$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.	+	<math>\|V^+\| = \|V^-\|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.