問題タブ [chinese-postman]

私は多くのサイクルでグラフを指示しましたが、おそらく強く接続されており、そこから最小のサイクルを取得する必要があります。つまり、グラフで最も短いサイクルであるサイクルを取得する必要があり、すべてのエッジが少なくとも1回はカバーされます。

私はいくつかのアルゴリズムまたはいくつかの理論的背景を探していましたが、私が見つけたのは中国の郵便配達アルゴリズムだけです。ただし、このソリューションは有向グラフ用ではありません。

誰か助けてもらえますか？ありがとう

編集>>そのグラフのすべてのエッジのコストは同じです-たとえば1

私は、中国語の郵便配達員の問題を解決するクラスのプログラムに取り組んでいます。私たちの課題では、ハードコードされたグラフを解決するためのプログラムを作成するだけで済みますが、一般的なケースで自分で解決しようとしています。

問題を引き起こしているのは、奇妙な頂点のペアリングのパーティションを生成することです。

たとえば、グラフに次のラベル付きの奇数頂点があるとします。

これらの頂点で作成できる可能なペアリング/パーティションをすべて見つける必要があります。

与えられたパーティションがあることがiわかりました：

i = 15したがって、上記の 6 つの奇妙な頂点が与えられると、パーティションを生成する必要があることがわかります。

15 のパーティションは次のようになります。

次に、パーティションごとに、各ペアを取得し、それらの間の最短距離を見つけて、そのパーティションの合計を計算します。ペア間の合計距離が最小のパーティションが選択され、奇数頂点間の最短パス間のすべてのエッジが 2 倍になります (選択されたパーティションで見つかります)。

これらは、郵便配達員が 2 回歩かなければならないエッジを表します。

最初は、これらのパーティションを生成するための適切なアルゴリズムを考え出したと思いました。

1. 昇順でソートされたすべての奇数の頂点から始めます

   12 34 56

2. 現在最大の頂点を持つペアの後ろのペアを選択します

   12 [34] 56

3. このペアの 2 桁目を 1 増やします。選択したペアの左側のすべてを同じままにし、選択したペアの右側のすべてをセット内の残りの数字にし、昇順で並べ替えます。

   12 35 46

4. 繰り返す

ただし、これには欠陥があります。たとえば、最後に到達したときに選択ペアが一番左の位置にあることに気付きました (つまり):

[16] .. ..

私が考案したアルゴリズムはこの場合停止し、[16] で始まる残りのペアを生成しません。これは、その左側に変更するペアがないためです。

それで、それは製図板に戻ります。

この問題を以前に研究したことがある人は、これらのパーティションを生成するための正しい方向に私を導くのに役立つヒントを持っていますか?

巡回セールスマン問題（TSP）と中国人郵便配達問題（CPP）の違いは何ですか？

私にとっては、どちらも目的地に行き、そして戻って行きたいと思っています。

双向グラフで中国の郵便配達回路を見つけるアルゴリズムを探しています。ここでの双向グラフは対称有向グラフではなく、1970年にEdmonds＆Johnsonによって導入されたグラフです。

ハロルド・N・ガボウがi983で発表した論文に基づいて、同様の問題を解決した論文はほとんど見つかりませんでしたが、正式なアルゴリズムはありませんでした。彼らは、問題を減らすことができる/完全なbマッチング、双方向ネットワークフローなどに関連する可能性があると述べましたが、これまでは理解できませんでした。

そのための概念とアルゴリズムを知っている人がいたら、アドバイスをください。

訪問する必要のあるエッジとオプションのエッジを含むグラフがあります。エッジの重みはさまざまで、どちらの方向にも必要な回数だけ移動できます。総重量を最小にするルートを決めようとしています。

私が理解しているように、中国人郵便配達問題は、グラフのすべての端を少なくとも1回は訪問する必要があるグラフを扱います。上記のバリアントに「名前」があるかどうか、またはこのタイプのグラフの解決を処理する可能性のあるアルゴリズムの方向に私を向けるかどうかを誰かに教えてもらえますか？

私はPythonでソリューションをプログラムしようとしているので、それを使用するソリューションはどれも素晴らしいでしょう。そうでなければ、ソリューションを実行できると確信しています。

さて、今手元にある小さな作品で問題に直面しています...

主な目標は、与えられたグラフ (重みなしで有向) を持ち、すべてのエッジをカバーする最小の合計長でパスのグループ (可能であれば 1 つのパスのみですが、それ以上でもかまいません) を発見することです。その他の「制約」は、グラフが DFA であるため、パスは初期状態で開始し、受け入れ状態で終了する必要がある (マークされている) ことです。

最初は、これが中国の郵便配達員問題に似ていることに気づきました。実際、そうです。しかし、私の場合、グラフは方向付けられており (これは少し変わっていると思います)、結果のパスが最短のままであるため、エッジを複数回処理しても問題はありません。

オイラー パスと T-Joins についていくつか読んだことがありますが、これがおそらく私の問題の解決策です。私がそれを正しく理解していれば、私がすべきことは、グラフでオイラー パスを見つけて、存在しない場合は存在させたり、T-Joins を複製したり、そのようなことをすることです...私は多くの問題を抱えていましたこれを理解しても、これが私の問題に対する答えであるかどうかさえわかりません... (ここで見つけた最も短くてわかりやすいテキスト: http://en.wikipedia.org/wiki/Route_inspection_problem )

このグラフを考えると、短い例を残すだけです (1 は初期で、5 は承認です)。

1 -> 2; 2 -> 3; 2 -> 4; 4 -> 5;

私の問題に対する答えは、1 -> 2 -> 4 -> 5 および 1 -> 2 -> 3 となるはずです (この場合、3 は受け入れ状態ではないという事実も処理する必要がありますが、しかし、エッジのないすべての状態を他のノードに受け入れ状態としてフラグを立てることで、簡単にそれを乗り越えることができます)。

すべてを十分に説明したことを願っています。

前もって感謝します！

私の質問はプログラミングよりもグラフに関するものであることは知っていますが、ここのコミュニティは非常に活発で、グラフを扱っている可能性があります。

ここで、有向グラフのオイラー閉路の集合に複数のグラフを含めることができるかどうか疑問に思っています。

ありがとう

だから、私はグラフを楽しみたいと思っていましたが、今では夢中になっています。

まず、指定された数のエッジを持つ連結グラフを生成します。これは私の呪いになった簡単な部分です。基本的には意図したとおりに動作しますが、得られた結果はかなり奇妙です (まあ、そうではないかもしれませんが、ここでの問題です)。グラフを生成するアルゴリズムは非常に単純です。

02 つの配列があり、そのうちの 1 つは からまでの数値で満たされ、もう 1 つn - 1は空です。

最初に、最初の要素をシャッフルして、最後の要素を空の要素に移動します。

次に、ループで、最初の配列の最後の要素と2番目の配列のランダムな要素の間にエッジを作成し、その後、最後の要素を最初の配列から別の配列に移動します。

その部分が完了したら、必要な数が得られるまで、頂点間にランダムなエッジを作成する必要があります。これも非常に簡単です。0からまでの範囲の 2 つの数値をランダムに選択しn - 1、これらの頂点間にエッジがない場合は、1 つ作成します。

これはコードです：

さて、これを印刷すると立派なグラフです。次に、ハミルトニアン サイクルを見つけたいと思います。この部分は機能します。次に、私の悩みの種であるオイラーサイクルに行き着きます。どうしたの？

まず、すべての頂点が偶数かどうかを確認します。そして、そうではありません。いつも。完全なグラフを生成することを選択しない限り、毎回。

私は今、自分のコードによって破壊されていると感じています。何か間違えている？それともこうあるべきなのか？オイラー回路がまれであることはわかっていましたが、それほどまれではありませんでした。助けてください。

私はグラフ理論の初心者です。5 日以来、Python を使用して Hierholzer のアルゴリズムをコードに実装しようとしています。グラフ理論に関する私の経験も、これまでに 5 日間です。私のコードは以下の通りです：

D2 グラフは接続されており、各ノードは次数が偶数です。ran_k が開始ノードとして 6 を選択し、オイラー回路が [6, 5, 4, 2, 1, 0, 3, 2, 6, 8, 7, 9, 6] の場合、私のコード (サイクル関数) は正常に動作します。D2グラフが強く接続され、すべてのノードが偶数の次数を持つため、開始ノードはオイラー回路を持ちます。

ran_k が開始ノードとして 0 を選択すると、サイクル関数は次のように返します: 残りのグラフ: {2: [6], 4: [2], 5: [4], 6: [5, 8], 7: [9], 8: [7], 9: [6]} として一時スタック: [0, 3, 2, 1, 0]. これも問題ありません。なぜなら、cycle2 を実行し、cycle 関数のこれらの出力に対して関数をスタックする必要があることがわかっているからです。私は自分の論文でこれを解決できますが、D2 の長さがゼロまたは tmp_stk 0 の長さをチェックする while ループを使用してこれらの関数を使用する方法がわかりません。