2

私はc＃で深さ優先探索を実装しようとしましたが、これを分散コンピューティングの方法で行う方法が正確にはわかりません。あなたたちがこれで私を助けることができれば私は本当に感謝するでしょう:)あなたは私のDFSコードを以下に見つけることができます

public class DFS
{ 
static List<string> traversedList = new List<string>();
static List<string> parentList = new List<string>();

public static void Main(string[] args)
{

    int N = 100;
    int M = N * 4;
    int P = N * 16;

    Stack newstack = new Stack();

    List<string> global_list=new List<string>();

    StreamReader file = new StreamReader("my input file");

    string text = file.ReadToEnd();

    string[] lines = text.Split('\n');

    string[][] array1 = new string[lines.Length][];

    for (int i = 0; i < lines.Length; i++)
    {
        lines[i] = lines[i].Trim();
        string[] words = lines[i].Split(' ');

        array1[i] = new string[words.Length];

        for (int j = 0; j < words.Length; j++)
        {
            array1[i][j] = words[j];
        }
    }

    StreamWriter sr = new StreamWriter(args[0]);

    for (int i = 0; i < array1.Length; i++)
    {
        for (int j = 0; j < array1[i].Length; j++)
        {
            if (j != 0 )
            {
                sr.Write(array1[i][0] + ":" + array1[i][j]);
                Console.WriteLine(array1[i][0] + ":" + array1[i][j]);
                sr.Write(sr.NewLine);
            }
        }

    }

    int start_no = Convert.ToInt32(args[args.Length-1]);

    traversedList.Add(start_no.ToString());
    parentList.Add("root");
    dfs(array1, start_no);

    for (int z = 0; z < traversedList.Count; z++)
    {
            Console.WriteLine(traversedList.ElementAt(z) + " "+parentList.ElementAt(z)+" "+(z+1));
     }
    Console.ReadLine();
}

private static void dfs(string[][] array, int point)
{
    for (int z = 1; z < array[point].Length; z++)
        {
            if ((!traversedList.Contains(array[point][z])))
            {
                traversedList.Add(array[point][z]);
                parentList.Add(point.ToString());
                dfs(array, int.Parse(array[point][z]));
            }
        }
        return;
}

}

4

1 に答える 1

1

コンピューター チェス (現在は世界チャンピオンのコンピューター化されたゲーム プレーヤーに進化) の世界の文献を読む必要があります。彼らは分散型の深さ優先探索を約 30 年間行っており、多くのアイデアを持っています。特定のブランチにどれだけの作業が含まれているかを知らずに、作業を均等に分散する必要があるため、うまくいくのは難しいです。

Monty Newbornや McGill University を調べてみてください。10 年前には、この問題の温床だったようです。

そしてもちろん、GIYF: 「分散型深さ優先検索」は、この論文への参照を作成しました: 深さ優先検索の分散アルゴリズム。コンピューターチェスの世界からのアイデアがたくさん含まれていると思います。

*共有メモリの問題" DFS は少し難しくありません。分散ヘルパーにメッセージを送信する必要はなく、単純にポインターを渡すことができます :-} 並列処理を提供し、爆発的な並列処理を管理する言語を持つことが役立ちますプログラムがすべての分岐でフォークした場合に発生する可能性のある成長. 私が設計した並列プログラミング言語で構築された4x4 N パズル ソルバーの例を提供します. (この例は、私の最も初期の SO 投稿の 1 つです!)

于 2012-06-02T02:28:20.200 に答える