2

有向グラフの強連結成分を見つける必要があります。Tarjanのアルゴリズムを使用することにしました。ここまでは順調ですね。ただし、プログラムを操作するために必要なデータセットは巨大であり、stackoverflow例外が発生します。スタックサイズを増やすことができないので、別の解決策を見つける必要があります。

再帰的アルゴリズムを反復に変更することはできますが、「よりクリーンなソリューション」があるかどうか疑問に思いました。

そうではないと思いますが、反復バージョンの実装を開始する前に確認したいと思います。

提案をありがとう！

4

2 に答える 2

1

SCCを見つけるための既知のアルゴリズムはすべて、本質的に再帰的なDFSに基づいているため、基本的に次のオプションがあります。

  • 再帰とともに生きる。実際にはオプションではありません。すべてのノードの再帰により、スタックがすぐにいっぱいになります。
  • 反復を使用して再帰を書き換え、DFS用に独自のスタックを提供します。それほど難しいことではありませんが、これをお勧めします
  • 非再帰的アルゴリズムを発明します。その場合は頑張ってください
于 2012-04-10T12:10:41.150 に答える
0

私もこの問題を抱えていましたが、この問題を解決する最善の方法は、すべてのコードを新しいスレッドに転送することであることがわかりました。

public class Class implements Runnable {
    @Override
    public void run() {
        ...
    }
}

メインクラスでこれを行います：

public class Main {
    public static void main(String[] args) {
        Thread th = new Thread(null, new Class(), "solution", 32 << 20);
        th.start();
    }
} 

Thread(ThreadGroup group, Runnable target, String name, long stackSize)

最初のパラメータはnull、2番目のパラメータはこのスレッドで実行したいクラス、3番目のパラメータはあまり重要ではない名前、最後のパラメータはこのスレッドに割り当てたいスタックサイズです。例のスタック サイズは 2^32 バイトです (よくわかりません!)

ThreadJavaの詳細については、 https ://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html を参照してください。

これらの例は Java です。他のオブジェクト指向言語でも同じことができます。

于 2017-01-03T16:40:01.780 に答える