《近似アルゴリズム（ヒューリスティックアルゴリズム）》 - 版の履歴

2007年8月15日 (水) 07:46にSakasegawaによる

2007-08-15T07:46:31Z

2007年8月15日 (水) 07:45にSakasegawaによる

2007-08-15T07:45:59Z

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

2007-08-06T17:25:38Z

Orsjwiki: "《近似アルゴリズム（ヒューリスティックアルゴリズム）》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:25:23Z

"《近似アルゴリズム（ヒューリスティックアルゴリズム）》" を保護しました。 [edit=sysop:move=sysop]

2007年7月7日 (土) 01:35に122.26.167.76による

2007-07-07T01:35:16Z

2007年7月7日 (土) 01:33に122.26.167.76による

2007-07-07T01:33:39Z

2007年7月3日 (火) 10:19にOrsjwikiによる

2007-07-03T10:19:24Z

Orsjwiki: 新しいページ: ''''【きんじあるごりずむ（ひゅーりすてぃっくあるごりずむ）(approximation algorithm (heuristic algorithm))】''' 　組合せ最適化問題の中に...'

2007-07-03T10:11:10Z

新しいページ: ''''【きんじあるごりずむ（ひゅーりすてぃっくあるごりずむ）(approximation algorithm (heuristic algorithm))】''' 　組合せ最適化問題の中に...'

新規ページ

'''【きんじあるごりずむ（ひゅーりすてぃっくあるごりずむ）(approximation algorithm (heuristic algorithm))】'''

　組合せ最適化問題の中には, 最適解を求めることが現実的に困難な問題が数多く存在する. どのようなアルゴリズムを用いても莫大な計算時間, 計算量が必要になるような問題で, 計算機の性能に依存するというような次元の話ではなく, 問題の構造そのものに依存するという意味である. NP完全, NP困難なクラスに属する問題はそのような問題の代表例である. [[ナップサック問題]] (knapsack problem), [[最大カット問題]] (maximum cut problem), [[集合カバー問題]] (set covering problem)等の整数計画問題の多くはこれらのクラスに分類される. これらの問題を解くアルゴリズムには, その計算時間が問題の規模$n$の多項式として表されるものが一般的には存在しないと考えられている. しかし, 問題中のパラメータを含めると多項式時間で最適解を求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び, 動的計画法, 分枝限定法等の手法が用いられる.

　NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率$\varepsilon$に従って, $\varepsilon$-近似アルゴリズム}($\varepsilon$-approximation algorithm)という性能表現がなされ, 最近ではPTAS}{PTAS}(polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.

　近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, 遺伝的アルゴリズム等が挙げられるが, 基本的にこれらの手法は近似解を局所探索法}{局所探索法}(local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.

----
'''参考文献'''

[1] C. R. Reeves, ''Modern Heuristic Techniques for Combinatorial Problems'', Blackwell Scientific Publications, 1993. 横山隆一, 奈良宏一, 佐藤晴夫, 鈴木昭男, 荻本和彦, 陳洛南訳,『モダンヒューリスティックス』, 日刊工業新聞社, 1997.

[2] R. Sedgewick, ''Algorithms'', 2nd ed., Addison Wesley, 1988. 野下浩平, 星守, 佐藤創, 田口東訳,『アルゴリズム第3巻』, 近代科学社, 1992.

[3] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, ''Combinatorial Optimization'', John Wiley & Sons, 1998.

[4] T. C. Hu, ''Combinatorial Algorithms'', Addison Wesley, 1982.

[5] A. V. Aho, J. E. Hopcroft and J. D. Ullman, ''Data Structures and Algorithms'', Addison Wesley, 1983.

← 古い版		2007年8月15日 (水) 07:46時点における版
5行目:		5行目:
	NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[ε-近似アルゴリズム]] (<math>\varepsilon</math>-approximation algorithm)という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.		NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[ε-近似アルゴリズム]] (<math>\varepsilon</math>-approximation algorithm)という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.

−	近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, [[遺伝的アルゴリズム~~\|遺伝アルゴリズム~~]]等が挙げられるが, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.	+	近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, [[遺伝アルゴリズム\|遺伝的アルゴリズム]]等が挙げられるが, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.

← 古い版		2007年8月15日 (水) 07:45時点における版
5行目:		5行目:
	NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[ε-近似アルゴリズム]] (<math>\varepsilon</math>-approximation algorithm)という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.		NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[ε-近似アルゴリズム]] (<math>\varepsilon</math>-approximation algorithm)という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.

−	近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, ~~遺伝的アルゴリズム等が挙げられるが~~, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.	+	近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, [[遺伝的アルゴリズム\|遺伝アルゴリズム]]等が挙げられるが, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.

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

	[5] A. V. Aho, J. E. Hopcroft and J. D. Ullman, ''Data Structures and Algorithms'', Addison Wesley, 1983.		[5] A. V. Aho, J. E. Hopcroft and J. D. Ullman, ''Data Structures and Algorithms'', Addison Wesley, 1983.
		+
		+	[[category:近似・知能・感覚的手法\|きんじあるごりずむ（ひゅーりすてぃっくあるごりずむ）]]

@@ 3行目: / 3行目: @@
 　組合せ最適化問題の中には, 最適解を求めることが現実的に困難な問題が数多く存在する. どのようなアルゴリズムを用いても莫大な計算時間, 計算量が必要になるような問題で, 計算機の性能に依存するというような次元の話ではなく, 問題の構造そのものに依存するという意味である. NP完全, NP困難なクラスに属する問題はそのような問題の代表例である. [[ナップサック問題]] (knapsack problem), [[最大カット問題]] (maximum cut problem), [[集合カバー問題]] (set covering problem)等の整数計画問題の多くはこれらのクラスに分類される. これらの問題を解くアルゴリズムには, その計算時間が問題の規模<math>n\, </math>の多項式として表されるものが一般的には存在しないと考えられている. しかし, 問題中のパラメータを含めると多項式時間で最適解を求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び, 動的計画法, 分枝限定法等の手法が用いられる.
-　NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[&epsilon;-近似アルゴリズム]] ([<math>\varepsilon</math>-approximation algorithm]])という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.
+　NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[&epsilon;-近似アルゴリズム]] (<math>\varepsilon</math>-approximation algorithm)という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.
 　近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, 遺伝的アルゴリズム等が挙げられるが, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.

@@ 1行目: / 1行目: @@
 '''【きんじあるごりずむ（ひゅーりすてぃっくあるごりずむ）(approximation algorithm (heuristic algorithm))】'''
-　組合せ最適化問題の中には, 最適解を求めることが現実的に困難な問題が数多く存在する. どのようなアルゴリズムを用いても莫大な計算時間, 計算量が必要になるような問題で, 計算機の性能に依存するというような次元の話ではなく, 問題の構造そのものに依存するという意味である. NP完全, NP困難なクラスに属する問題はそのような問題の代表例である. [[ナップサック問題]] (knapsack problem), [[最大カット問題]] (maximum cut problem), [[集合カバー問題]] (set covering problem)等の整数計画問題の多くはこれらのクラスに分類される. これらの問題を解くアルゴリズムには, その計算時間が問題の規模$n$の多項式として表されるものが一般的には存在しないと考えられている. しかし, 問題中のパラメータを含めると多項式時間で最適解を求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び, 動的計画法, 分枝限定法等の手法が用いられる.
+　組合せ最適化問題の中には, 最適解を求めることが現実的に困難な問題が数多く存在する. どのようなアルゴリズムを用いても莫大な計算時間, 計算量が必要になるような問題で, 計算機の性能に依存するというような次元の話ではなく, 問題の構造そのものに依存するという意味である. NP完全, NP困難なクラスに属する問題はそのような問題の代表例である. [[ナップサック問題]] (knapsack problem), [[最大カット問題]] (maximum cut problem), [[集合カバー問題]] (set covering problem)等の整数計画問題の多くはこれらのクラスに分類される. これらの問題を解くアルゴリズムには, その計算時間が問題の規模<math>n\, </math>の多項式として表されるものが一般的には存在しないと考えられている. しかし, 問題中のパラメータを含めると多項式時間で最適解を求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び, 動的計画法, 分枝限定法等の手法が用いられる.
-　NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率$\varepsilon$に従って, [[$\varepsilon$-近似アルゴリズム]] ([[$\varepsilon$-approximation algorithm]])という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.
+　NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを[[近似アルゴリズム]] (approximation algorithm)と呼ぶ. [[欲張り法]](greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率<math>\varepsilon\, </math>に従って, [[&epsilon;-近似アルゴリズム]] ([<math>\varepsilon</math>-approximation algorithm]])という性能表現がなされ, 最近では[[PTAS]] (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.
 　近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, 遺伝的アルゴリズム等が挙げられるが, 基本的にこれらの手法は近似解を[[局所探索法]] (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.

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