2つの数値間の関係を示す順序付けられていないペアのリストが与えられた場合、連続したリストを形成するようにペアを結合するCまたはPythonの効率的なアルゴリズムは何ですか.
たとえば、次のようになります。
(0, 1)
(1, 2)
(3, 2)
(4, 3)
以下を生成します。[0, 1, 2, 3, 4]
明らかに、ペアにギャップやループがある場合、これはうまくいきません(0, 1) (3, 4)。
質問する
66 次
2 に答える
1
数値は、グラフの頂点としてモデル化できます。リスト内の各要素は、ノード間のエッジを表します。
あなたが探しているのは、このグラフの「オイラーパス」です。これには複数のアルゴリズムがあります。http://en.wikipedia.org/wiki/Eulerian_pathでよく知られているアルゴリズムを確認してください。
于 2013-03-11T02:53:39.423 に答える
0
あなたがやろうとしているのは、オイラーパス (各エッジを 1 回訪問する) ではなく、ハミルトニアンパス(各頂点を 1 回訪問する) です。これは、パスにループを持たせたくないためです。これは、ループの定義によってそうしないことを意味します任意の頂点に 2 回アクセスしたい。
この問題は、既知の効率的なアルゴリズムがないことを意味するNP 完全であることが知られています (「効率的」とは、多項式時間で意味する場合)。
この問題の効率的なアルゴリズムを見つけることができれば、P と NP が等しいことを示すことで、P とNP の問題も解決できます。ほとんどのコンピューター科学者は、P 対 NP の問題に対する答えは「いいえ、NP の問題に対する効率的なアルゴリズムは不可能です」であると考えています。これは、質問に対する効率的なアルゴリズムの可能性がないことを意味します (ただし、証明される必要があります)。
于 2013-03-11T07:58:08.063 に答える