厳密解が求まる例

ウィキペディア小見出し辞書

厳密解（最適解）が求まる例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/05/18 13:51 UTC 版)

「貪欲法」の記事における「厳密解（最適解）が求まる例」の解説

いくつかのアルゴリズムは貪欲法を基本戦略としているものの、厳密解が求まることが証明されている。 ダイクストラ法 プリム法 クラスカル法 最適化問題で厳密解となるには、動的計画法同様、部分構造最適性（英: optimal substructure）、つまり、部分問題を解き、それを利用して最適化問題の厳密解が解けることが必要である。