3

今春の四半期試験に備えるために、私はグラフの問題を研究して実験しています。

「巡回セールスマン」のような典型的な問題にはすでに慣れていましたが、「中国人郵便配達問題」とそのバリエーションを詳しく調べてみると、問題の重要な側面が欠けているように感じました。容量が限られているという側面です。したがって、特定の数nの文字が正常に配信された後、(新しい文字を取得するために)オフィスステーションに戻る必要があります。では、最短経路を見つけるのはどうですか?

CPPは、その関連性と実生活への適用のしやすさから非常に興味をそそられましたが、この側面を追加することで、CPPをさらに実生活に適用できるようになると思います。

すべてのエッジを少なくとも1回訪問する無向グラフ(CPP)で最短経路を見つける方法についての助けに感謝します。特定の文字数の後に開始点(ポストステーション)に戻らなければならないという制約は次のとおりです。配信されます。


編集(元のCPPの説明):「中国の郵便配達問題またはルート検査問題は、(接続された)無向グラフのすべてのエッジを訪れる最短の閉じたパスまたは回路を見つけることです。グラフにオイラー回路がある場合(閉じた歩行すべてのエッジを1回カバーする)、その回路が最適なソリューションです。グラフがオイラーでない場合は、奇数次の頂点が含まれている必要があります。ハンドシェイクの補題により、これらの頂点が偶数個存在する必要があります。郵便配達問題を解決するには、まず最小のT結合を見つけます。T結合を2倍にすることで、グラフをオイラーにします。元のグラフの郵便配達問題の解は、新しいグラフのオイラー回路を見つけることによって得られます。」Src:wikipedia.org

4

1 に答える 1

2

あなたのバリアントは、たとえば、すべての値が厳密に B/4 と B/2 の間にある3 分割問題からの削減により、NP 困難です。キャパシテイテッド ビークル ルーティングと同じ方法をいくつか使用して「解決」できる可能性があります。ただし、CPP は実際の問題ではなく、T 結合を研究する口実であることを理解する必要があります。

于 2012-04-11T22:19:59.240 に答える