《巡回セールスマン問題》 - 版の履歴

Imahori: 誤植の修正

2008-03-13T01:18:02Z

誤植の修正

2007年8月6日 (月) 17:04にKuwashimaによる

2007-08-06T17:04:44Z

Orsjwiki: "《巡回セールスマン問題》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:14:48Z

"《巡回セールスマン問題》" を保護しました。 [edit=sysop:move=sysop]

2007年7月6日 (金) 07:17に122.26.167.76による

2007-07-06T07:17:15Z

2007年7月6日 (金) 07:14に122.26.167.76による

2007-07-06T07:14:50Z

2007年7月6日 (金) 06:44に122.26.167.76による

2007-07-06T06:44:11Z

2007年7月4日 (水) 06:25に122.26.167.76による

2007-07-04T06:25:42Z

2007年7月4日 (水) 06:25に122.26.167.76による

2007-07-04T06:25:10Z

122.26.167.76: 新しいページ: ''''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】''' 　点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) ...'

2007-07-04T06:24:18Z

新しいページ: ''''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】''' 　点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) ...'

新規ページ

'''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】'''

　点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) \in E$ 上の距離 $d_{ij}$ が与えられたとき，点集合 $V$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]](traveling salesman problem) （行商人問題）とよぶ．

　特に，距離の対称性（$d_{ij}=d_{ji}$）を満たすものを対称巡回セールスマン問題，3角不等式（$d_{ij} \leq d_{ik} + d_{kj}$）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が $d$ 次元超立方体 $[0,1]^d$ 内に分布しており，$2$ 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．

　巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．

　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が一定値$\alpha (<\infty)$ で抑えられる多項式時間の近似解法さえ${\rm P} \neq {\rm NP}$ のもとでは存在しないことが示されている．

　3角不等式を満たす対称巡回セールスマン問題に対しては，近似比が $3/2$ 以下の保証をもつ多項式時間の近似解法が知られている．また，$d$ を定数としたときの $d$ 次元ユークリッド巡回セールスマン問題に対しては，固定された $\epsilon >0$ を与えたときに，近似比が $1+\epsilon$ 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．

　実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[k-opt法 (巡回セールスマン問題の)|k-opt法]] {{$k$}-opt法}($k$-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．

----

'''参考文献'''

[1] 山本芳嗣, 久保幹雄, 『巡回セールスマン問題への招待』, 朝倉書店，1997.

@@ 3行目: / 3行目: @@
 　点集合 <math>V\, </math>，枝集合 <math>E\, </math> から構成されるグラフ <math>G=(V,E)\, </math>, 枝 <math>(i,j) \in E\, </math> 上の距離 <math>d_{ij}\, </math> が与えられたとき，点集合 <math>V\, </math> のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．
-　特に，距離の対称性（<math>d_{ij}=d_{ji}\, </math>）を満たすものを対称巡回セールスマン問題，3角不等式（<math>d_{ij} \leq d_{ik} + d_{kj}\, </math>）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が <math>d\, </math> 次元超立方体 <math>[0,1]^d\, </math> 内に分布しており，<math>2\, </math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
+　特に，距離の対称性（<math>d_{ij}=d_{ji}\, </math>）を満たすものを対称巡回セールスマン問題，三角不等式（<math>d_{ij} \leq d_{ik} + d_{kj}\, </math>）を満たすものを三角不等式を満たす巡回セールスマン問題，点集合が <math>d\, </math> 次元超立方体 <math>[0,1]^d\, </math> 内に分布しており，<math>2\, </math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
 　巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．
@@ 9行目: / 9行目: @@
 　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値<math>\alpha (<\infty)\, </math> で抑えられる多項式時間の近似解法さえ<math>{\rm P} \neq {\rm NP}\, </math> のもとでは存在しないことが示されている．
-角不等式を満たす対称巡回セールスマン問題に対しては，近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている．また，<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては，固定された <math>\epsilon >0\, </math> を与えたときに，近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
+　三角不等式を満たす対称巡回セールスマン問題に対しては，近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている．また，<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては，固定された <math>\epsilon >0\, </math> を与えたときに，近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
 　実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[k-opt法 (巡回セールスマン問題の)|k-opt法]] (<math>k\, </math>-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．

← 古い版		2007年8月6日 (月) 17:04時点における版
18行目:		18行目:

	[1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店，1997.		[1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店，1997.
		+
		+
		+	[[Category:グラフ･ネットワーク\|じゅんかいせーるすまんもんだい]]

← 古い版		2007年7月6日 (金) 07:17時点における版
11行目:		11行目:
	3角不等式を満たす対称巡回セールスマン問題に対しては，近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている．また，<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては，固定された <math>\epsilon >0\, </math> を与えたときに，近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．		3角不等式を満たす対称巡回セールスマン問題に対しては，近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている．また，<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては，固定された <math>\epsilon >0\, </math> を与えたときに，近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．

−	実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[~~<math>~~k~~\, </math>~~-opt法 (巡回セールスマン問題の)\|]] (<math>k\, </math>-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．	+	実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[k-opt法 (巡回セールスマン問題の)\|k-opt法]] (<math>k\, </math>-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．

@@ 1行目: / 1行目: @@
 '''【じゅんかいせーるすまんもんだい (traveling salesman problem) 】'''
-　点集合 $<math>V</math>$，枝集合 $<math>E</math>$ から構成されるグラフ $<math>G=(V,E)</math>$, 枝 $<math>(i,j) \in E</math>$ 上の距離 $<math>d_{ij}</math>$ が与えられたとき，点集合 <math>$V</math>$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．
+　点集合 <math>V\, </math>，枝集合 <math>E\, </math> から構成されるグラフ <math>G=(V,E)\, </math>, 枝 <math>(i,j) \in E\, </math> 上の距離 <math>d_{ij}\, </math> が与えられたとき，点集合 <math>V\, </math> のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．
-　特に，距離の対称性（$<math>d_{ij}=d_{ji}</math>$）を満たすものを対称巡回セールスマン問題，3角不等式（$<math>d_{ij} \leq d_{ik} + d_{kj}</math>$）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が $<math>d</math>$ 次元超立方体 $<math>[0,1]^d</math>$ 内に分布しており，$<math>2$</math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
+　特に，距離の対称性（<math>d_{ij}=d_{ji}\, </math>）を満たすものを対称巡回セールスマン問題，3角不等式（<math>d_{ij} \leq d_{ik} + d_{kj}\, </math>）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が <math>d\, </math> 次元超立方体 <math>[0,1]^d\, </math> 内に分布しており，<math>2\, </math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
 　巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．
-　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値$<math>\alpha (<\infty)</math>$ で抑えられる多項式時間の近似解法さえ$<math>{\rm P} \neq {\rm NP}</math>$ のもとでは存在しないことが示されている．
+　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値<math>\alpha (<\infty)\, </math> で抑えられる多項式時間の近似解法さえ<math>{\rm P} \neq {\rm NP}\, </math> のもとでは存在しないことが示されている．
-角不等式を満たす対称巡回セールスマン問題に対しては，近似比が $<math>3/2</math>$ 以下の保証をもつ多項式時間の近似解法が知られている．また，$<math>d</math>$ を定数としたときの $<math>d</math>$ 次元ユークリッド巡回セールスマン問題に対しては，固定された $<math>\epsilon >0$</math> を与えたときに，近似比が $<math>1+\epsilon</math>$ 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
+角不等式を満たす対称巡回セールスマン問題に対しては，近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている．また，<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては，固定された <math>\epsilon >0\, </math> を与えたときに，近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
-　実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[k-opt法 (巡回セールスマン問題の)|k-opt法]] {{$<math>k</math>$}-opt法}($<math>k</math>$-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．
+　実用的な近似解法としては，[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[<math>k\, </math>-opt法 (巡回セールスマン問題の)|]] (<math>k\, </math>-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（[[TSP多面体]](TSP polytope)）を利用した[[分枝カット法]] (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．

@@ 1行目: / 1行目: @@
 '''【じゅんかいせーるすまんもんだい (traveling salesman problem) 】'''
-　点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) \in E$ 上の距離 $d_{ij}$ が与えられたとき，点集合 $V$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．
+　点集合 $<math>V</math>$，枝集合 $<math>E</math>$ から構成されるグラフ $<math>G=(V,E)</math>$, 枝 $<math>(i,j) \in E</math>$ 上の距離 $<math>d_{ij}</math>$ が与えられたとき，点集合 <math>$V</math>$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．
-　特に，距離の対称性（$d_{ij}=d_{ji}$）を満たすものを対称巡回セールスマン問題，3角不等式（$d_{ij} \leq d_{ik} + d_{kj}$）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が $d$ 次元超立方体 $[0,1]^d$ 内に分布しており，$2$ 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
+　特に，距離の対称性（$<math>d_{ij}=d_{ji}</math>$）を満たすものを対称巡回セールスマン問題，3角不等式（$<math>d_{ij} \leq d_{ik} + d_{kj}</math>$）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が $<math>d</math>$ 次元超立方体 $<math>[0,1]^d</math>$ 内に分布しており，$<math>2$</math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ．
 　巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．
-　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値$\alpha (<\infty)$ で抑えられる多項式時間の近似解法さえ${\rm P} \neq {\rm NP}$ のもとでは存在しないことが示されている．
+　巡回セールスマン問題は，[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値$<math>\alpha (<\infty)</math>$ で抑えられる多項式時間の近似解法さえ$<math>{\rm P} \neq {\rm NP}</math>$ のもとでは存在しないことが示されている．
-角不等式を満たす対称巡回セールスマン問題に対しては，近似比が $3/2$ 以下の保証をもつ多項式時間の近似解法が知られている．また，$d$ を定数としたときの $d$ 次元ユークリッド巡回セールスマン問題に対しては，固定された $\epsilon >0$ を与えたときに，近似比が $1+\epsilon$ 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
+角不等式を満たす対称巡回セールスマン問題に対しては，近似比が $<math>3/2</math>$ 以下の保証をもつ多項式時間の近似解法が知られている．また，$<math>d</math>$ を定数としたときの $<math>d</math>$ 次元ユークリッド巡回セールスマン問題に対しては，固定された $<math>\epsilon >0$</math> を与えたときに，近似比が $<math>1+\epsilon</math>$ 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
 ----
 '''参考文献'''
 [1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店，1997.

← 古い版	2007年7月19日 (木) 13:14時点における版
(相違点なし)

← 古い版		2007年7月4日 (水) 06:25時点における版
1行目:		1行目:
−	'''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】'''	+	'''【じゅんかいせーるすまんもんだい (traveling salesman problem) 】'''

	点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) \in E$ 上の距離 $d_{ij}$ が与えられたとき，点集合 $V$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．		点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) \in E$ 上の距離 $d_{ij}$ が与えられたとき，点集合 $V$ のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) （行商人問題）とよぶ．

《巡回セールスマン問題》 - 版の履歴

Imahori: 誤植の修正

2007年8月6日 (月) 17:04にKuwashimaによる

Orsjwiki: "《巡回セールスマン問題》" を保護しました。 [edit=sysop:move=sysop]

2007年7月6日 (金) 07:17に122.26.167.76による

2007年7月6日 (金) 07:14に122.26.167.76による

2007年7月6日 (金) 06:44に122.26.167.76による

2007年7月4日 (水) 06:25に122.26.167.76による

2007年7月4日 (水) 06:25に122.26.167.76による

122.26.167.76: 新しいページ: ''''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】''' 点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) ...'

122.26.167.76: 新しいページ: ''''【じゅんかいせーるすまんもんだい (traveling salesman problem}) 】''' 　点集合 $V$，枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) ...'