4

有向巡回グラフで可能なすべてのパスを見つけたいです。そのためのプログラムを作成しましたが、ノード数が 40 または 50 を超えると無限の時間がかかり始めることに気付きました。

理論的に言えば、 Nノードの有向巡回グラフで可能なパスの数。factorial( N ) のようなものですか? 次の 119 ノードの例の推測を教えてください。もちろん、ループは 1 回だけなので、循環パスは無視してかまいません。

グラフ画像

4

2 に答える 2

3

グラフに表示されるこの一般的なパターンを見てみましょう。

A ---> B
|     /|
|    / v
|   /  C
|  /   |
| /    |
vv    /
D <---

アスキーアートですみません。A -> Dしたがって、ここには 、A -> B -> D、およびの3 つのパスがありA -> B -> C -> Dます。

ここで、まったく同じ図がD別のノードから発せられているとしますG:

D ---> E
|     /|
|    / v
|   /  F
|  /   |
| /    |
vv    /
G <---

以前と同様に、 、 、および の 3 つのパスがD -> GありD -> E -> GますD -> E -> F -> G。

Aでは、 からへの道は何通りありますGか?

から に到達するAには、 からにG到達する必要があります。これは、3 つの方法のいずれかで行うことができます。次に、 から まで取得する必要があります。これは、3 つの方法のいずれかで行うことができます。これら 2 つの選択肢 ( toとto ) は、互いに独立しています。したがって、* =からへの可能なパスがあります。ADDGADDG339AG

3図を繰り返し続けると、繰り返しごとに可能なパスの数を掛けることになります。したがって、3 つの数字で 27 のパスがあります。4 つの図形、81 パス。等

それは指数関数的な成長です。別の言い方をすれば、効率的になりたい場合は、現在行っていることを別の方法で行う必要があります。

編集:大まかな見積もりを取得するには:これらの数字のみを数え、途中の複雑なごちゃまぜを見ずに、これらの単純なノードだけを介して3 * 3 * 3 * 3 * (2^8) * (4^8) * 3 * 3 * 2 * 3=可能なパスを取得します。73383542784

編集: コード分析を行っているようです。何をしたいのか正確にわからなくても、私が推奨するのは、到達する必要Aがあるノードに沿って収集している情報を統合することです (たとえば、図のノード、D、およびG)。次に、到達する必要がある次のノードに到達するまで検索を行い、そこでも情報を収集します。これにより、指数関数的な爆発が防止されます。

于 2012-08-30T16:08:12.487 に答える
0

次のことを試すことができます。

  • すべてのパスの一部であるグラフ内のノードを見つけます。これを行うには、グラフからノードを順番に削除します。削除するとパスを見つけることができなくなる各ノードは、そのようなノードです。グラフにはそれらがたくさんあるはずです。
  • これを証明することはできませんが、これらのノードがすべてのパスに現れる順序を見つけることはできるはずです。
  • グラフを、2 つの連続する強制ノードとそれらの間のすべてのノードで構成されるチャンクに分割します。
  • 各チャンクのパス数を計算する
  • すべてのパス カウントの積を計算して、フル カウントを取得します。数値のオーバーフローを避けるために、GMP などを使用することを忘れないでください
于 2012-08-30T18:03:52.483 に答える