最長単純道
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/03/04 03:06 UTC 版)
最短経路とは逆の問題で、最長単純道問題もある。最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立しておらず、貪欲法などで解くことが出来ない。辺の重みなしであっても、NP完全問題である。
※この「最長単純道」の解説は、「最短経路問題」の解説の一部です。
「最長単純道」を含む「最短経路問題」の記事については、「最短経路問題」の概要を参照ください。
Weblioに収録されているすべての辞書から最長単純道を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から最長単純道を検索
- 最長単純道のページへのリンク