a-star - すべてのTSPアルゴリズムは同じ最適ルートを提供しますか？

Question

TSPのすべてのアルゴリズムが同じ最適ルートを提供するかどうか疑問に思っていましたか？これが当てはまると思いましたが、分枝限定法とA *を実装しましたが、どちらも同じ入力に対して非常に異なる結果をもたらします。これは正常かどうか疑問に思っていました。

Answer 1

ルートは異なりますが、すべての最適なソリューションのコストは同じである必要があります。

A *ソリューションの方が高価な場合は、ヒューリスティックが間違っています。ウィキペディアA*アルゴリズムを見て、常に最適なソリューションが見つかることを証明してください。

Answer 2

いいえ。複数の最適なルートが存在する場合、異なるアルゴリズムが同じパスを見つける必要はありません。それは実装に依存し、グラフのラベル付け方法にも依存すると思います。そのため、ラベル付けが異なると、同じアルゴリズムで異なるルートが検出されます。