12

私は楽しみと練習のために倉庫番ソルバーを書いています。これは単純なアルゴリズム (BFS のようなものですが、少し違います) を使用します。

今、私はその実行時間を推定したいと思います（Oとオメガ）。ただし、ネットワーク内の頂点から別の頂点への非循環パスの数を計算する方法を知る必要があります。実際には、頂点の am*n マトリックスの 2 つの頂点間の有効なパスの数を計算する式が必要です。

有効なパス:

  • 各頂点を 0 回または 1 回訪問します。
  • 回路がない

たとえば、これは有効なパスです。

代替テキスト http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

しかし、これはそうではありません:

代替テキスト http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

必要なのは、2 つの頂点aとbの間のすべての非巡回パスの数を見つけるメソッドです。

解決方法やトリックに関するコメントを歓迎します。

4

5 に答える 5

4

解決策ではありませんが、このアイデアをもう少し考えてみてください。問題は、すべてのパスを取得するために、可能な限り長いパスも計算する必要があることです。最長パスの問題は、一般的なグラフのNP完全問題であるため、比較的小さなグラフ（8x8以上）でも非常に長い時間がかかります。

開始頂点がマトリックスの左上隅にあり、終了頂点がマトリックスの右下隅にあると想像してください。

  • 1x2マトリックスの場合、可能なパスは1つだけです。
  • 2x2マトリックス=>2***1**パス=>2
  • 3x2マトリックス=>2***2**パス=>4
  • 3x3マトリックス=>2*** 4 ** + 2*2パス=>12
  • 3x4マトリックス=>2*** 12 ** + 12+2パス=>38

毎回、現在のパス数について前回の計算結果を組み合わせました。そのような平面グラフの厳密な定式化が存在する可能性があります。おそらくそれについては多くの理論がありますが、私はそれに対して愚かすぎます...

次のJava（申し訳ありませんが、私はc ++の専門家ではありません：-/）スニペットを使用して、より大きな行列の可能なパスを計算できます。

public static void main(String[] args) {
    new Main(3, 2).start();
}
int xSize;
int ySize;
boolean visited[][];

public Main(int maxX, int maxY) {
    xSize = maxX;
    ySize = maxY;
    visited = new boolean[xSize][ySize];
}

public void start() {
    // path starts in the top left corner
    int paths = nextCell(0, 0);
    System.out.println(paths);
}

public int nextCell(int x, int y) {
    // path should end in the lower right corner
    if (x == xSize - 1 && y == ySize - 1)
        return 1;

    if (x < 0 || y < 0 || x >= xSize || y >= ySize || visited[x][y]) {
        return 0;
    }

    visited[x][y] = true;
    int c = 0;
    c += nextCell(x + 1, y);
    c += nextCell(x - 1, y);
    c += nextCell(x, y + 1);
    c += nextCell(x, y - 1);
    visited[x][y] = false;
    return c;
}

=>

  • 4x4 => 184
  • 5x5 => 8512
  • 6x6 => 1262816
  • 7x7（この単純なケースでもかなりの時間がかかります！）=> 575780564

これは、（理論的にのみ）MxMマトリックスの任意の位置から右下隅までのすべての可能なパスを計算し、このマトリックスを使用してパスの数をすばやく検索できることを意味します。動的計画法（以前の計算結果を使用）は、物事を少しスピードアップする可能性があります。

于 2010-03-28T11:02:15.337 に答える
4

グラフ内の単純なパスの数を数える一般的な問題は、#P 完全です。一部の #P 完全問題には、完全に多項式のランダム化された近似スキームがありますが、ないものもありますが、近似には関心がないと主張しています。トゥッテ多項式を計算する場合と同様に、グリッド構造を利用する方法があるかもしれませんが、これを行う方法についてのアイデアはありません。

于 2010-03-24T22:29:27.160 に答える
3

プロジェクト Euler にも同様の、あまり一般的ではない問題があります: http://projecteuler.net/index.php?section=problems&id=237

フォーラムで説明されているソリューションのいくつかは、一般的なケースを解決するために拡張できると思います。ただし、特に一般的なケースでは、かなり難しい問題です。

フォーラムにアクセスするには、まず問題を解決する必要があります。私はここに答えを投稿したり、答えをリストした特定のサイトへのリンクを張ったりしません.

于 2010-03-23T16:39:34.943 に答える
2

これは、ポリマー結合をモデル化するために使用することで、化学と物理学に直接適用される数学の未解決の問題です。これに関する最も初期の作業のいくつかは、マンハッタン計画 (第二次世界大戦の核爆弾) で行われました。

自己回避歩行問題として知られています。

私は夏の間、大学の数学科でピボット アルゴリズムと呼ばれるモンテカルロ アルゴリズムを研究して、特定の長さの自己回避歩行数の漸近適合のパラメーターを近似しましたn。

これまでにこの問題にアプローチするために使用されたさまざまなテクニックについては、Gordon Slade の「 The Self Avoiding Walk 」というタイトルの優れた本を参照してください。

これは非常に複雑な問題であり、あなたがそれを検討する動機は何なのだろうか. 自己回避ウォークはまったく単純ではないため、おそらく、あなたが望むもののためのより単純なモデルを見つけることができます.

于 2010-05-26T16:51:50.593 に答える
1

エッジを示すマトリックスは機能しますか? エッジがどこにあるかを示す行列を作成することを検討してください。つまり、[a,b]=1 <=> a->b はグラフのエッジ、それ以外の場合は 0 です。次に、この行列をさまざまなべき乗に上げて、n ステップを使用して頂点間を移動する方法がいくつ存在するかを示し、それらを合計して結果を取得します。これは、問題を解決する 1 つの方法のアイデアにすぎません。問題を組み立てる方法は他にもあるかもしれません。

別のアイデアとして、これはMathOverflowに属しているのだろうか

確かに、ゼロ行列を取得したら、あなたの場合のようにべき乗を停止できます.3の後に行く場所はあまりありませんが、1から3へのパスは直接パスであり、2を通過するパスになるため、すべてゼロの 1 が見つかる前に、いくつかの行列を足し合わせるだけです。

たとえば、n^(n+1) の範囲を計算する方法が必要だと思います。ここで、n はグラフ内の頂点の数であり、その時点までにすべての頂点が停止点であることを示します。一度訪れた。ただし、循環パスを問題から取り除く方法がわかりません。または、グラフに循環がないと仮定できますか?

于 2010-03-23T15:51:24.487 に答える