いくつかの幾何学的ルーティングアルゴリズムについて読んでいましたが、メインアルゴリズムのバージョンでヒューリスティックを採用すると、パフォーマンスが向上する可能性がありますが、漸近的な最適性が失われると書かれています。
なぜそうなのですか？パフォーマンスの向上よりも漸近的な最適化を優先する必要がありますか? 漸近的な最適性を優先すべき典型的なケースはありますか? 既知のベンチマークはありますか?
質問する
117 次
2 に答える
0
ヒューリスティックは高速に実行されますが、完全に最適なソリューションを達成できない可能性がある最適化の問題について質問していると思いますが、真に最適なソリューションを見つけるアルゴリズムは、常に完全に最適なソリューションを提供しますが、最悪の場合ははるかに遅くなる可能性があります。もしそうなら、ここにいくつかの情報があります。一般に、ヒューリスティック アルゴリズムを使用するかどうかの決定は、多くの場合、それが「実際に」最適なソリューションにどれだけ近似しているか、この典型的なソリューションの品質が十分に優れているかどうか、および特定の問題インスタンスが実際に遭遇する問題のカテゴリ。興味がある場合は、NP 完全問題の近似アルゴリズムを調べることができます。ヒューリスティックによって発見された解のスコアが、最適解のスコアの定数乗数 (1 + イプシロン) 内にあるいくつかの問題があり、イプシロンを選択できます。ただし、通常、イプシロンが減少すると、実行時間は増加します。
于 2013-07-15T00:47:46.097 に答える
0
私の推測では、彼らは近似アルゴリズムのための (許容できない) ヒューリスティックの使用について話していると思います。たとえば、巡回セールスマンの問題は NP 完全ですが、NP 完全問題の既知のアルゴリズムよりもはるかに高速であるが、最適値の数パーセント以内になることが保証されているヒューリスティックな近似法があります。
于 2013-07-15T00:47:49.610 に答える