経路問題 - 変更履歴

Moderator: /* Dijkstraの方法 */

2020-11-27T16:23:37Z

Dijkstraの方法

←前の版		2020年11月27日 (金) 16:23時点における版
181 行:		181 行:
	===Dijkstraの方法===		===Dijkstraの方法===

-	DPの原理を使った効率的な方法として,~~Dijkstraの方法が知られています。~~	+	DPの原理を使った効率的な方法として,Dijkstraの方法が知られている.
-	~~<Dijkstra>~~	+	[https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95 Dijkstraのアルゴリズム]
		+	(Wikipedia)

	'''準備'''		'''準備'''

Moderator: /* 無向グラフ */

2020-11-27T14:11:39Z

無向グラフ

←前の版		2020年11月27日 (金) 14:11時点における版
444 行:		444 行:

	(図5.7)		(図5.7)
-	[[ファイル:Fig5.7.gif]]	+	[[ファイル:Fig5.7.gif\|300px]]

2020年11月27日 (金) 14:10 における Moderator による編集

2020-11-27T14:10:46Z

←前の版		2020年11月27日 (金) 14:10時点における版
26 行:		26 行:
	順序対<math>(a,b)</math>は向きのついた枝,あるいは弧と呼ばれ,		順序対<math>(a,b)</math>は向きのついた枝,あるいは弧と呼ばれ,

-	(図5.1) [[ファイル:Fig5.1.gif]]	+	(図5.1) [[ファイル:Fig5.1.gif\|300px]]

	のように表すことができる。<math>a</math>は始点,<math>b</math>は終点と呼ばれる。		のように表すことができる。<math>a</math>は始点,<math>b</math>は終点と呼ばれる。
33 行:		33 行:


-	(図5.2) [[ファイル:Fig5.2.gif\|~~300px~~]]	+	(図5.2) [[ファイル:Fig5.2.gif\|400px]]


46 行:		46 行:
	<math>G</math>をラベル付き有向グラフといいます。		<math>G</math>をラベル付き有向グラフといいます。

-	(図5.3) [[ファイル:Fig5.3.gif]]	+	(図5.3) [[ファイル:Fig5.3.gif\|400px]]

	===路===		===路===
61 行:		61 行:
	<math>G</math>をラベル付き有向グラフとする。ただし,		<math>G</math>をラベル付き有向グラフとする。ただし,

-	(図5.4) [[ファイル:Fig5.4.gif]]	+	(図5.4) [[ファイル:Fig5.4.gif\|400px]]

	の<math>(b,e,f,d,b)</math>のように「閉じた路」は含まないものとする。		の<math>(b,e,f,d,b)</math>のように「閉じた路」は含まないものとする。
70 行:		70 行:
	表すものとしておく。		表すものとしておく。

-	(図5.5) [[ファイル:Fig5.5.gif]]	+	(図5.5) [[ファイル:Fig5.5.gif\|400px]]

	弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で		弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で
87 行:		87 行:


-	(図5.6) [[ファイル:Fig5.6.gif]]	+	(図5.6) [[ファイル:Fig5.6.gif\|400px]]

	節点<math>a</math>から節点<math>d</math>への最短路が与えられたとする。その路が途中に節点<math>b</math>を経由しているとすると,		節点<math>a</math>から節点<math>d</math>への最短路が与えられたとする。その路が途中に節点<math>b</math>を経由しているとすると,
156 行:		156 行:
	のうち,最短のものが<math>O(i,k)</math>であるという意味である.		のうち,最短のものが<math>O(i,k)</math>であるという意味である.

-	(図5.5) [[ファイル:Fig5.5.gif]]	+	(図5.5) [[ファイル:Fig5.5.gif\|400px]]


452 行:		452 行:
	(図5.8)		(図5.8)

-	[[ファイル:Fig5.8.gif]]	+	[[ファイル:Fig5.8.gif\|400px]]

	<math>		<math>
468 行:		468 行:
	(図5.9)		(図5.9)

-	[[ファイル:Fig5.9.gif]]	+	[[ファイル:Fig5.9.gif\|400px]]

	===路===		===路===
488 行:		488 行:

	(図5.10)		(図5.10)
-	[[ファイル:Fig5.10.gif]]	+	[[ファイル:Fig5.10.gif\|400px]]

	弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で		弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で

2020年11月27日 (金) 14:08 における Moderator による編集

2020-11-27T14:08:13Z

←前の版		2020年11月27日 (金) 14:08時点における版
33 行:		33 行:


-	(図5.2) [[ファイル:Fig5.2.gif]]	+	(図5.2) [[ファイル:Fig5.2.gif\|300px]]

2020年11月26日 (木) 16:44 における Moderator による編集

2020-11-26T16:44:39Z

←前の版		2020年11月26日 (木) 16:44時点における版
1 行:		1 行:
-
	==有向グラフ==		==有向グラフ==
-	有向グラフは,ここでは<math>G</math>~~で表しますが~~,コンピュータや,~~ネットワークにもよく使われ~~	+	有向グラフは,ここでは<math>G</math>で表すが,コンピュータや,ネットワークにもよく使われる。有向グラフ<math>G</math>は
-	~~ます。有向グラフ~~<math>G</math>は	+

2020年11月26日 (木) 16:31 における Moderator による編集

2020-11-26T16:31:10Z

←前の版		2020年11月26日 (木) 16:31時点における版
186 行:		186 行:
	<Dijkstra>		<Dijkstra>

-	~~====~~準備~~====~~	+	'''準備'''
	<math>		<math>
	K \leftarrow \phi \\		K \leftarrow \phi \\
198 行:		198 行:
	</math>		</math>

-	~~====~~手順1~~====~~	+	'''手順1'''
	<math>		<math>
	終了 (K = P)		終了 (K = P)
207 行:		207 行:
	</math>		</math>

-	~~====~~手順2~~====~~	+	'''手順2'''
	<math>		<math>
	K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKとする。）\\		K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKとする。）\\
220 行:		220 行:
	<math> O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m </math> そうでなければ何もしない.]		<math> O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m </math> そうでなければ何もしない.]

-	~~====~~手順1にもどる。~~====~~	+	'''手順1にもどる。'''


242 行:		242 行:
	</math>		</math>

-	~~====~~準備~~====~~	+	'''準備'''
	<math>		<math>
	K \leftarrow \phi \\		K \leftarrow \phi \\
257 行:		257 行:
	</math>		</math>

-	~~====~~手順１(1回目)~~====~~	+	'''手順１(1回目)'''
	<math>		<math>
	K \ne Pなので終了ではない		K \ne Pなので終了ではない
267 行:		267 行:
	となり、m=1を選ぶ｡		となり、m=1を選ぶ｡

-	~~====~~手順２(1回目)~~====~~	+	'''手順２(1回目)'''
	<math>		<math>
	K \leftarrow \{ 1\}		K \leftarrow \{ 1\}
291 行:		291 行:
	</math>		</math>

-	~~====~~手順１(2回目)~~====~~	+	'''手順１(2回目)'''
	<math>		<math>
	K=\{1 \}なのでK \ne Pとなり終了ではない \\		K=\{1 \}なのでK \ne Pとなり終了ではない \\
302 行:		302 行:
	となり、<math>m=2</math>を選ぶ｡		となり、<math>m=2</math>を選ぶ｡

-	~~====~~手順２(２回目)~~====~~	+	'''手順２(２回目)'''
	<math>		<math>
	K \leftarrow 　\{1\} \cup \{2\}=\{1,2\} \\		K \leftarrow 　\{1\} \cup \{2\}=\{1,2\} \\
326 行:		326 行:
	</math>		</math>

-	~~====~~手順１(３回目)~~====~~	+	'''手順１(３回目)'''
	<math>		<math>
	K=\{1,2\}なのでK \ne Pとなり終了ではない \\		K=\{1,2\}なのでK \ne Pとなり終了ではない \\
336 行:		336 行:
	</math>		</math>

-	~~====~~手順２(３回目)~~====~~	+	'''手順２(３回目)'''
	<math>		<math>
	K \leftarrow \{1,2,4\} \\		K \leftarrow \{1,2,4\} \\
352 行:		352 行:
	</math>		</math>

-	~~====~~手順１(４回目)~~====~~	+	'''手順１(４回目)'''
	<math>		<math>
	K=\{1,2,4\}なのでK \ne Pとなり終了ではない		K=\{1,2,4\}なのでK \ne Pとなり終了ではない
363 行:		363 行:
	となり、<math>m=5</math>を選ぶ｡		となり、<math>m=5</math>を選ぶ｡

-	~~====~~手順２(４回目)~~====~~	+	'''手順２(４回目)'''
	<math>		<math>
	K \leftarrow \{1,2,4,5\} \\		K \leftarrow \{1,2,4,5\} \\
378 行:		378 行:
	</math>		</math>

-	~~====~~手順１(５回目)~~====~~	+	'''手順１(５回目)'''
	<math>		<math>
	K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\		K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\
387 行:		387 行:
	となり<math>m=3</math>を選ぶ｡		となり<math>m=3</math>を選ぶ｡

-	~~====~~手順２(５回目)~~====~~	+	'''手順２(５回目)'''
	<math>		<math>
	K \leftarrow \{1,2,3,4,5\} \\		K \leftarrow \{1,2,3,4,5\} \\
399 行:		399 行:
	</math>		</math>

-	~~====~~手順１(６回目)~~====~~	+	'''手順１(６回目)'''
	<math>		<math>
	K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\		K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\
410 行:		410 行:
	となり、<math>m=6</math>を選ぶ｡		となり、<math>m=6</math>を選ぶ｡

-	~~====~~手順２(６回目)~~====~~	+	'''手順２(６回目)'''
	<math>		<math>
	K \leftarrow \{1,2,3,4,5,6\} \\		K \leftarrow \{1,2,3,4,5,6\} \\
419 行:		419 行:
	</math>		</math>

-	~~====~~手順１(７回目)~~====~~	+	'''手順１(７回目)'''
	<math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了		<math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了

2020年11月26日 (木) 16:29 における Moderator による編集

2020-11-26T16:29:27Z

←前の版		2020年11月26日 (木) 16:29時点における版
1 行:		1 行:
-	~~=={最短経路問題}~~

-		+	==有向グラフ==
-	~~==ラベル付き有向グラフ==~~	+
-		+
-	===有向グラフ===	+
	有向グラフは,ここでは<math>G</math>で表しますが,コンピュータや,ネットワークにもよく使われ		有向グラフは,ここでは<math>G</math>で表しますが,コンピュータや,ネットワークにもよく使われ
	ます。有向グラフ<math>G</math>は		ます。有向グラフ<math>G</math>は
190 行:		186 行:
	<Dijkstra>		<Dijkstra>

-	===準備===	+	====準備====
	<math>		<math>
	K \leftarrow \phi \\		K \leftarrow \phi \\
202 行:		198 行:
	</math>		</math>

-	===手順1===	+	====手順1====
	<math>		<math>
	終了 (K = P)		終了 (K = P)
211 行:		207 行:
	</math>		</math>

-	===手順2===	+	====手順2====
	<math>		<math>
	K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKとする。）\\		K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKとする。）\\
224 行:		220 行:
	<math> O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m </math> そうでなければ何もしない.]		<math> O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m </math> そうでなければ何もしない.]

-	===手順1にもどる。===	+	====手順1にもどる。====


246 行:		242 行:
	</math>		</math>

-	===準備===	+	====準備====
	<math>		<math>
	K \leftarrow \phi \\		K \leftarrow \phi \\
261 行:		257 行:
	</math>		</math>

-	===手順１(1回目)===	+	====手順１(1回目)====
	<math>		<math>
	K \ne Pなので終了ではない		K \ne Pなので終了ではない
271 行:		267 行:
	となり、m=1を選ぶ｡		となり、m=1を選ぶ｡

-	===手順２(1回目)===	+	====手順２(1回目)====
	<math>		<math>
	K \leftarrow \{ 1\}		K \leftarrow \{ 1\}
295 行:		291 行:
	</math>		</math>

-	===手順１(2回目)===	+	====手順１(2回目)====
	<math>		<math>
	K=\{1 \}なのでK \ne Pとなり終了ではない \\		K=\{1 \}なのでK \ne Pとなり終了ではない \\
306 行:		302 行:
	となり、<math>m=2</math>を選ぶ｡		となり、<math>m=2</math>を選ぶ｡

-	===手順２(２回目)===	+	====手順２(２回目)====
	<math>		<math>
	K \leftarrow 　\{1\} \cup \{2\}=\{1,2\} \\		K \leftarrow 　\{1\} \cup \{2\}=\{1,2\} \\
330 行:		326 行:
	</math>		</math>

-	===手順１(３回目)===	+	====手順１(３回目)====
	<math>		<math>
	K=\{1,2\}なのでK \ne Pとなり終了ではない \\		K=\{1,2\}なのでK \ne Pとなり終了ではない \\
340 行:		336 行:
	</math>		</math>

-	===手順２(３回目)===	+	====手順２(３回目)====
	<math>		<math>
	K \leftarrow \{1,2,4\} \\		K \leftarrow \{1,2,4\} \\
356 行:		352 行:
	</math>		</math>

-	===手順１(４回目)===	+	====手順１(４回目)====
	<math>		<math>
	K=\{1,2,4\}なのでK \ne Pとなり終了ではない		K=\{1,2,4\}なのでK \ne Pとなり終了ではない
367 行:		363 行:
	となり、<math>m=5</math>を選ぶ｡		となり、<math>m=5</math>を選ぶ｡

-	===手順２(４回目)===	+	====手順２(４回目)====
	<math>		<math>
	K \leftarrow \{1,2,4,5\} \\		K \leftarrow \{1,2,4,5\} \\
382 行:		378 行:
	</math>		</math>

-	===手順１(５回目)===	+	====手順１(５回目)====
	<math>		<math>
	K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\		K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\
391 行:		387 行:
	となり<math>m=3</math>を選ぶ｡		となり<math>m=3</math>を選ぶ｡

-	===手順２(５回目)===	+	====手順２(５回目)====
	<math>		<math>
	K \leftarrow \{1,2,3,4,5\} \\		K \leftarrow \{1,2,3,4,5\} \\
403 行:		399 行:
	</math>		</math>

-	===手順１(６回目)===	+	====手順１(６回目)====
	<math>		<math>
	K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\		K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\
414 行:		410 行:
	となり、<math>m=6</math>を選ぶ｡		となり、<math>m=6</math>を選ぶ｡

-	===手順２(６回目)===	+	====手順２(６回目)====
	<math>		<math>
	K \leftarrow \{1,2,3,4,5,6\} \\		K \leftarrow \{1,2,3,4,5,6\} \\
423 行:		419 行:
	</math>		</math>

-	===手順１(７回目)===	+	====手順１(７回目)====
	<math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了		<math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了

Moderator: /* 分岐限定法 */

2020-11-26T16:23:51Z

分岐限定法

←前の版		2020年11月26日 (木) 16:23時点における版
593 行:		593 行:
	問題の難しさを表す場合によく出てくる「NP困難問題」の一つである.		問題の難しさを表す場合によく出てくる「NP困難問題」の一つである.
	種々な方法が考案されている。「分岐限定法」もその一つである.		種々な方法が考案されている。「分岐限定法」もその一つである.
-
-	~~かなり作為的であるが,以下の例を考えます。~~
-	~~\vspace{5cm}~~
-	~~\par~~
-
-	~~(図5.11)~~
-
-	~~都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すれば,~~
-	~~<math>~~
-	~~(1,2,3,4,1),~~
-	~~(1,2,4,3,1),~~
-	~~(1,3,2,4,1),~~
-	~~(1,3,4,2,1),~~
-	~~(1,4,2,3,1),~~
-	~~(1,4,3,2,1)~~
-	~~</math>~~
-
-	~~である.これらの路は1番目,2番目,3番目に訪れる都市によって分類できる。~~
-	~~例えば,1番目に訪れる都市に注目して~~
-
-	~~(?)1番目の都市が2のもの~~
-	~~<math>(1,2,3,4,1),(1,2,4,3,1)</math>>~~
-
-	~~(?)1番目の都市が3のもの~~
-	~~<math>(1,3,2,4,1),(1,3,4,2,1)</math>>~~
-
-	~~（?）1番目の都市が4のもの~~
-	~~<math>　(1,4,2,3,1),(1,4,3,2,1)</math>>~~
-
-	~~である.?,?,?の中でそれぞれ,最少費用の路を探す問題は部分問題と呼ばれる。~~
-	~~さらに?,?,?の分類を2番目,3番目によって,細かく分類ができる。解の候補の「分岐」がでてくるわけである.~~
-
-	~~ここで,解の候補として路の<math>(1,3,4,2,1)</math>を選んだとする。この路の費用は130である.~~
-	~~部分問題?,すなわち,?の分類の中で費用最少を調べ見ると：~~
-	~~路（弧)</math>(1,4)</math>だけで,既に費用が130であり,費用がマイナスの弧はないのであるから,~~
-	~~この?の分類のものの最少費用は130より大である.従って,これ以上細かく調べる必要はない。~~
-	~~すると,解は,路の<math>(1,3,4,2,1)</math>を含む,（?）か（?）から探せばよい事になります。~~
-	~~このようにして,探すべき解の候補の「枝」のうち,無駄なものを削除する事ができる。~~
-
-	~~さらに,路<math>(1,2,3),(1,3,2)</math>も費用が130であるから,これらの後の節点がなんであろうと,費用は~~
-	~~130より大きくなります。この例では,以後の分岐はないので,これが判っても効用はあり~~
-	~~ませんが,もしさらに分岐があるなら,無駄な「枝」を削除できることになります。~~
-
-	~~この様にして,結局,~~
-	~~<math>　(1,3,4,2,1),　(1,2,4,3,1) </math>~~
-	~~にたどりつく。~~
-
-	~~無論,問題のよって,また,部分問題にの作製（分類）の仕方によって,最悪,全ての路を調べる事に~~
-	~~なる場合もあります。以上のような解法を一般的に表すと,~~
-
-	~~最小化問題<math>P</math>が与えられたとして：~~
-
-
-	~~===(1)===　<math>P</math>から,部分問題の集合<math>L=\{P_0,P_1,P_2,\cdots,P_n\}</math>を作り,~~
-	~~初期解を適当に選択してその値<math>C_0</math>を求める。~~
-	~~以下の手続きを<math>L</math>の元<math>P_i</math>の全てについて行う~~
-	~~===(2)===最小問題<math>P_i</math>の解の下限値<math>inf P_i</math>を求め,~~
-	~~<math>inf P_i >　C_0</math>なら　<math>L \leftarrow L \setminus \{P_i\}</math>~~
-	~~<math>(LからP_iを削除)</math>~~
-	~~===(3)=== 最小問題<math>P_i</math>の解<math>min P_i<m/ath>を求め~~
-	~~<math>min P_i　<　C_0</math>なら　<math>C_0 \leftarrow min P_i</math>~~
-	~~とする~~
-
-
-	~~図5.10の問題について,「分岐限定法」を適用すると例えば以下のようになります。~~
-	~~これは、本大学院の社会人学生久保さんにやっていただいたものである.上の例より~~
-	~~スマートな解法である.~~
-
-	~~都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すると,~~
-
-	~~<math>(1,2,3,4,1),(1,2,4,3,1),(1,3,2,4,1),(1,3,4,2,1),(1,4,2,3,1),(1,4,3,2,1)</math>>~~
-
-	~~である．これらの路は費用最小の<math>\{1,3\},\{3,4\}</math>の両方を通るものと，~~
-	~~通らないものに分類できる．~~
-
-
-	~~<math>\{1,3\},\{3,4\}</math>の両方を通るもの~~
-
-	~~<math>(1,2,4,3,1),(1,3,4,2,1)</math>>~~
-
-	~~\item{(?)}\{1,3\},\{3,4\}の両方は通らないもの~~
-
-	~~<math>(1,2,3,4,1),(1,3,2,4,1),(1,4,2,3,1),(1,4,3,2,1)</math>>~~
-
-
-	~~である．~~
-
-	~~ここで,解の候補として(?)から路<math>(1,2,4,3,1)</math>を選んだとする．~~
-	~~この路の費用は130である．~~
-
-	~~部分問題(?)で費用を調べて見ると,費用20の路が1つしか通れないことから，~~
-	~~各路の費用は <math>20,30,40,50,60</math> で，この中から4つを選ぶことから下限値は140となる．~~
-	~~140>130なので，は削除できる．~~
-
-	~~残った（）から探せばよい事になるが，路(1,3,4,2,1)の費用も130となり，~~
-	~~<math>(1,3,4,2,1),(1,2,4,3,1)</math>>~~
-	~~にたどりつく．~~
-
-	~~図5.11の問題について,「D.P.」を適用すると：~~
-
-
-	~~<math>~~
-	~~min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\}~~
-	~~,Cost(\{2,3,4\},4)+L\{4,1\} \}~~
-	~~=min\{ 80+50,110+20 ,140+130 \}~~
-	~~=130 (1,3,4,2,1)または (1,2,4,3,1)~~
-	~~Cost(\{2,3,4\},2)~~
-	~~=min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}~~
-	~~=min\{150+80,40+40\}=80 路は(1,3,4,2)~~
-	~~Cost(\{3,4\},3)=L\{1,4\}+L\{4,3\}=130+20=150~~
-	~~Cost(\{3,4\},4)=L\{1,3\}+L\{3,4\}=20+20=40~~
-	~~Cost(\{2,3,4\},3)~~
-	~~=min\{Cost(\{2,4\},2)+L\{2,3\},Cost(\{2,4\},4)+L\{4,3\}\}~~
-	~~=min\{170+80,90+20\}=110 路は(1,2,4,3)~~
-	~~Cost(\{2,4\},2)=L\{1,4\}+L\{4,2\}=130+40=170~~
-	~~Cost(\{2,4\},4)=L\{1,2\}+L\{2,4\}=50+40=90~~
-	~~Cost(\{2,3,4\},4)~~
-	~~=min\{Cost(\{2,3\},2)+L\{2,4\},Cost(\{2,3\},3)+L\{3,4\}\}~~
-	~~=min\{100+40,130+20\}=140 路は (1,3,2,4)~~
-	~~Cost(\{2,3\},2)=L\{1,3\}+L\{3,2\}=20+80=100~~
-	~~Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+80=130~~
-	~~</math>~~

Moderator: /* D.P.の適用 */

2020-11-26T16:22:16Z

D.P.の適用

←前の版		2020年11月26日 (木) 16:22時点における版
566 行:		566 行:
	<math>		<math>
	min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\},Cost(\{2,3,4\},4)+L\{4,1\} \}		min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\},Cost(\{2,3,4\},4)+L\{4,1\} \}
-	=min\{ 80+50,110+20 ,120+30 \} \\	+	=min\{ 80+50,110+20 ,120+30 \} =130 \\
-	~~=130~~ (1,3,4,2,1)または (1,2,4,3,1) \\	+	(1,3,4,2,1)または (1,2,4,3,1) \\
	Cost(\{2,3,4\},2)		Cost(\{2,3,4\},2)
	=min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}		=min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}

Moderator: /* D.P.の適用 */

2020-11-26T16:21:16Z

D.P.の適用

←前の版		2020年11月26日 (木) 16:21時点における版
565 行:		565 行:

	<math>		<math>
-	min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\}	+	min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\},Cost(\{2,3,4\},4)+L\{4,1\} \}
-	,Cost(\{2,3,4\},4)+L\{4,1\} \}	+	=min\{ 80+50,110+20 ,120+30 \} \\
-	=min\{ 80+50,110+20 ,120+30 \}	+
	=130 (1,3,4,2,1)または (1,2,4,3,1) \\		=130 (1,3,4,2,1)または (1,2,4,3,1) \\
	Cost(\{2,3,4\},2)		Cost(\{2,3,4\},2)