近似アルゴリズム
(近似度 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 10:07 UTC 版)
近似アルゴリズム（きんじアルゴリズム、英: approximation algorithm）とは、組合せ最適化問題の近似解を得るためのアルゴリズムを言う[1]。近似解とは、実行可能解（かつ問題の何らかの制約を満たす解）ではあるが、正解（厳密解）ではないものを言う。これは組合せ最適化問題の正解（すなわち最適解）であることが（厳密には）保証されないところの解を得るものである。なお、問題を変形した近似問題に対する正解を得るアルゴリズムも、元の問題に対する近似アルゴリズムと言える。
| |||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||
- ^ David P. Williamson; David B. Shmoys (2011). The Design of Approximation Algorithms. ISBN 978-0521195270.
[続きの解説]
「近似アルゴリズム」の続きの解説一覧
- 1 近似アルゴリズムとは
- 2 近似アルゴリズムの概要
- 近似度のページへのリンク
