0

私は昨夜今日までネット全体を広範囲に検索してきましたが、特にバックトラッキングアルゴリズムを使用して最短経路問題を解決する方法を説明しているリソースを見つけることができないようです。このアルゴで解いてみましたが、意味がわかりません。それがn-クイーンの問題であれば、それほど複雑ではありません。

それで、誰かが私にいくつかのリソースを指すいくつかのインターネットリンクを与えることができますか?とても感謝しています。

*更新:興味深いことに、バックトラッキングアルゴリズムは本当に最短経路問題を解決できますか?

4

2 に答える 2

1

バックトラッキングアルゴリズムを使用するように指定されています。実際、ダイクストラ SPFA またはベルマンフォードアルゴリズムは問題を解決するのに最適です。バックトラックを使用しなければならない場合は、残念ながら、時間計算量が悪くなってしまう可能性があります。次の道路セグメントを試してみてください。選択したセグメントの合計の長さが「現在の最短経路」を超えたら、バックトラックを開始してください。

于 2012-01-14T06:50:38.627 に答える