私は周りを検索してきましたが、TSP、ハミルトニアン、オイラーなど、誰もが好む問題のケースが少し異なるようです。V (頂点) と E (エッジ) で表されるグラフがあり、各エッジは無向であり、通過するのに一定のコストがあります。最小限のコストで、繰り返し可能なすべてのエッジをトラバースしたいと考えています。
直観的には、この問題は NP 困難であると感じられます。これは、他の NP 困難問題と非常に関連しているためです。ただし、パスはエッジを繰り返すことができるため、潜在的に簡単であることに気付きました。
私が最初に考えたのは、エッジを頂点に、頂点をノードに変換し、ハミルトニアンのように分析しようとすることでした。ただし、これにはすべてのノードに一度しかアクセスできないという制限があり、ノードに複数回アクセスできるという問題の緩和に関する情報は見つかりません。
私が検索が苦手なだけで、これが実際に既知の問題であり、研究されていることを知っている人はいますか?