はV頂点とEエッジと、あなたは有向グラフGを有していると仮定する。 L特別なエッジにはメダルが含まれており、少なくともNのメダルを収集することが目的です。頂点とエッジ（特殊なエッジを除く）は、何度も何度も訪れることができます。開始頂点も与えられますが、終了頂点はありません。訪問N特別なエッジが
私は同様の問題、すなわち：find shortest path in a graph that compulsorily visits certain Edges while others are not compulsory to visitを見ました。残念ながら、Lは約600であり、Nは約100です。私はDijkstraのアルゴリズムのいくつかの修正版を検討しましたが、頂点を一度しか訪問することができません。妥当な時間内にこれを実行できる解決策がありますか？
mcdowellaの参考文献をトラッキングすると、this paperになります（PDFへの直接リンク、Wileyのオンライン登録が必要な場合があります）。説明されている問題は、農村郵便配達員問題であり、確かにNP困難です。 TSP（NP-hard）、中国ポストマン問題（polytime）、および農村郵便配達問題（NP-hard）について述べている。ハミルトンサーキットからRPPへの削減は、私がコメントで示唆したことです：すべてのノードを2つに分割し、エッジでそれらを接続し、適切な重みを割り当て、それらのエッジを訪問したいものにします。
CPP（すべてのエッジにアクセスする必要がある）とRPPの違いは、すべてのノードにまたがる最小ウェイトツリーを見つける必要があるMSTを見つけることと、Steiner treeここで、ノードのサブセットにまたがる最小ウェイトツリーを見つける必要があります。
ウィキペディアがhttps://en.wikipedia.org/wiki/Route_inspection_problemと呼ぶ中国の郵便配達員問題があります。これは、あなたがすべての端を訪問したい場合に適用されますが、Wikipediaアカウントの最後に「農村郵便配達員の問題を最小限にする」と表示されます。それはあなたに少なくとも参照とおそらく検索語を与えます。
旅行のセールスマンのような音。 –
@ G.Bachエッジをトラバースすることと頂点をトラバースすることの違いは大きいので（EularパスVSハミルトンパス）、実際にはTSPであるかどうかはわかりません – amit
@amit TSPからの削減は、すべてのノードを2つに分割し、エッジで、それらのエッジを訪問したいものにします。 –