最短路問題 - 版の履歴

2008年11月9日 (日) 08:58にAlbeit-Kunによる

2008-11-09T08:58:46Z

2008年8月6日 (水) 07:48にImahoriによる

2008-08-06T07:48:37Z

2008年8月6日 (水) 07:47にImahoriによる

2008-08-06T07:47:30Z

2008年8月6日 (水) 03:10にImahoriによる

2008-08-06T03:10:09Z

2008年8月6日 (水) 02:59にImahoriによる

2008-08-06T02:59:02Z

Imahori: 基礎編と用語編のマージ

2008-03-13T14:05:19Z

基礎編と用語編のマージ

2007年8月8日 (水) 11:52にKanda.kによる

2007-08-08T11:52:03Z

Orsjwiki: "最短路問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:27:29Z

"最短路問題" を保護しました。 [edit=sysop:move=sysop]

122.17.2.240: 新しいページ: ''''【さいたんろもんだい (shortest path problem)】''' 有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有...'

2007-07-12T06:27:49Z

新しいページ: ''''【さいたんろもんだい (shortest path problem)】''' 有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有...'

新規ページ

'''【さいたんろもんだい (shortest path problem)】'''

有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.

← 古い版		2008年11月9日 (日) 08:58時点における版
38行目:		38行目:

	[[Category:グラフ･ネットワーク\|さいたんろもんだい]]		[[Category:グラフ･ネットワーク\|さいたんろもんだい]]
		+
		+	[[Category:組合せ最適化\|さいたんろもんだい]]

← 古い版		2008年8月6日 (水) 07:48時点における版
21行目:		21行目:


−		+	==参考文献==
−	~~----~~
−	~~'''~~参考文献~~'''~~

	[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, ''Network Flows: Theory, Algorithms, and Applications'', Prentice Hall, New Jersey, 1993.		[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, ''Network Flows: Theory, Algorithms, and Applications'', Prentice Hall, New Jersey, 1993.

@@ 1行目: / 1行目: @@
 '''【さいたんろもんだい (shortest path problem)】'''
-=== 概要 ===
+== 概要 ==
 有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.
-=== 詳説 ===
+== 詳説 ==
 　[[有向グラフ]]<math>G=(V,A)\, </math>の各[[枝]]<math>a\in A\, </math>に長さ<math>l(a)\in \mathbf{R}\, </math>が付与されている[[ネットワーク]]<math>N=(G=(V,A),l)\, </math>が与えられているとする. 有向グラフ<math>G\, </math>の任意の2点<math>s,t\in V\, </math>に対して, 点<math>s\, </math>を始点とし点<math>t\, </math>を終点とする有向道<math>P\, </math>の長さ<math>l(P)\, </math>は<math>P\, </math>上の枝の長さの総和, <math>\textstyle l(P)={\sum}_{a\in P}l(a)\, </math>, と定める. 始点<math>s\, </math>から終点<math>t\, </math>への有向道<math>P\, </math>のなかで, その長さを最小にするもの(が存在すれば, それ)を点<math>s\, </math>から点<math>t\, </math>への最短路(shortest path)といい, 最短路を求める問題を[[最短路問題]] (shortest path problem) という. 与えられたネットワークにおいて負の長さの有向閉路(負閉路と呼ぶ)が存在する場合には一般に最短路は存在しなくなる. ただし，負閉路を持つネットワーク上でも，初等的な（点を繰り返さない）道で最短なものを求める問題を考えることもあるが，一般的には解くことが難しい問題となる．

@@ 25行目: / 25行目: @@
 '''参考文献'''
-[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, ''Network Flows:Theory, Algorithms, and Applications'', Prentice Hall, New Jersey, 1993.
+[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, ''Network Flows: Theory, Algorithms, and Applications'', Prentice Hall, New Jersey, 1993.
 [2] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Applications of Network Optimization," in ''Network Models'', M. O, Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser, eds., North-Holland, 1995.

@@ 29行目: / 29行目: @@
 [2] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Applications of Network Optimization," in ''Network Models'', M. O, Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser, eds., North-Holland, 1995.
-[3] R. E. Bellman, "On a Routing Problem," ''Quarterly of Applied Mathematics'', '''16''' (1958), 87-90.
+[3] R. E. Bellman, "On a routing problem," ''Quarterly of Applied Mathematics'', '''16''' (1958), 87-90.
 [4] E. W. Dijkstra, "A note on two problems in connexion with graphs," ''Numerische Mathematik'', '''1''' (1959), 268-271.
@@ 37行目: / 37行目: @@
 [6] 久保，田村，松井 (編) 『応用数理計画ハンドブック』，朝倉書店，2002.
 [[Category:グラフ･ネットワーク|さいたんろもんだい]]

← 古い版		2007年8月8日 (水) 11:52時点における版
2行目:		2行目:

	有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.		有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.
		+
		+	詳しくは[[《最短路問題》\|基礎編：最短路問題]]を参照.

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