深度优先的分布式搜索 [英] Depth first search in a distributed way

问题描述

我曾尝试在C#中实现深度优先搜索，但是我不确定如何以分布式计算方式进行深度搜索.如果你们能在这方面帮助我，我将不胜感激:)您可以在下面找到我的DFS代码

I have tried implementing depth first search in c# but I am not exactly sure how to do this the distributed computing way. If you guys can help me out in this i would be really grateful :) You can find my DFS code below

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;
}   

}

推荐答案

您应该阅读计算机国际象棋世界(现在已发展为世界冠军的计算机化游戏玩家)中的文献资料.他们从事分布式深度优先搜索已有30年了，并且有很多想法.正确做起来很棘手，因为您必须在不知道特定分支可能包含多少工作的情况下平均分配工作.

You should read the literature from the computer chess (now evolved into world-champion computerized game players) world. They've been doing distributed depth-first search for some 30 years, and have lots of ideas. It is tricky to get right, because you have to distribute the work evenly without knowing how much work a particular branch might contain.

查看蒙蒂新生儿或麦吉尔大学，这似乎是这方面的温床大约10年前.

Check out Monty Newborn or McGill University, which seemed to be quite a hotbed of this some 10 years ago.

当然，GIYF:分布式深度优先搜索"产生了对本文的引用:深度优先搜索的分布式算法.我想它包含了来自计算机国际象棋世界的许多想法.

And of course, GIYF: "distributed depth first search" produced a reference to this paper: Distributed Algorithms for Depth-First Search. I'd guess it contains lots of ideas from the computer chess world.

共享内存的问题" DFS的难度要轻一些；您不必将消息发送给分布式助手，您只需传递一个指针即可:-}它有助于使一种语言为您提供并行性和管理您的程序在每个分支上分支时可能发生的爆炸性并行增长.我提供了一个内置的示例4x4 N-puzzle求解器一种我设计的并行编程语言(此示例是我最早的SO帖子之一！).

The problems for *shared memory" DFS a bit less difficult; you don't have to send messages to your distributed helpers, you can simply pass a pointer :-} It helps to have a language which provides you with parallelism and manages explosive parallelism growth that can occur if your program forks on every branch. I offer an example 4x4 N-puzzle solver built in a parallel programming language I designed. (This example was one of my earliest SO posts!).

这篇关于深度优先的分布式搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！