私の問題は次のとおりです。
無向グラフがあります。各エッジにはコスト（または重量）があります。ノードの1つにSというラベルが付いています。Sから始めて、すべてのノードに少なくとも1回はアクセスしたいと思います。ノードに複数回アクセスすることは許可されています。エッジに沿って複数回移動することは許可されていますが、ソリューションのコストが高くなります。3のコストでエッジを2回移動すると、パス全体のコストに6が追加されます。グラフにはいくつかの「行き止まり」ノードがあるため、エッジを複数回移動する必要がある場合があります。
これを行うための高速アルゴリズムとは何ですか？これはよく知られている問題ですか？
私が探しているもの：
適度に速い-ここで話しているグラフの相対的なサイズは、40〜50ノードのオーダーです。したがって、アルゴリズムが10〜15秒以上かかることはないでしょう。
合理的に最適-私は絶対的な最適性を探していません。解がほぼ最適になるように検索をガイドするための興味深いヒューリスティックは十分です。
私はこれをPythonで書きます。したがって、アルゴリズムのPython実装を知っている場合は、それが最適です。
助けてくれてありがとう。
