近似アルゴリズム
(近似解法 から転送)
出典: フリー百科事典『ウィキペディア(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 近似アルゴリズムの概要
- 近似解法のページへのリンク