gpt4 book ai didi

c++ - 并行化深度优先搜索 C++

转载 作者:行者123 更新时间:2023-11-30 03:59:57 24 4
gpt4 key购买 nike

我当时正在为 HiQ 编写程序,并且正在使用这个深度优先搜索循环。但是我想将它与 MPI 并行进行,但是我该怎么做才能使深度优先搜索并行进行呢?

bool FindSolution(ConfigType PuzzleConfig ) // Depth-First Search for sol to puzzle
{

if (PuzzleConfig == SolutionConfig) return true;

bool SolutionFound = false;

Mark(PuzzleConfig);

// For all configurations adjacent to current Puzzle Configuration (uses brute-force)
for (short from=1; !SolutionFound && from<=NUMHOLES; from++)
{
for (short to=1; !SolutionFound && to<=NUMHOLES; to++)
{
JumpType jump = {from,to};
if ( ValidJump(jump, PuzzleConfig) )
{
ConfigType NewConfig = FindNewConfig(jump, PuzzleConfig);
if ( !Marked(NewConfig) )
{
SolutionFound = FindSolution( NewConfig ); // Recursive call for Depth-First Search
if (SolutionFound)
JumpStack.push(jump);
}
}
}
}

return SolutionFound;
}

最佳答案

当您可以预先定义并行计算元素的具体拓扑结构时,MPI 很有用,并且可以在执行之前很大程度上跨计算元素划分工作。然后每个元素“知道”其他元素在哪里,以及它们大致在做什么,因此可以决定它应该向哪个元素发送消息以发出 MPI 发送。同样,接收元素必须“知道”它们将要接收消息,以便发出 MPI 接收。

深度优先搜索可以说是树状的,所以你知道抽象的拓扑结构......但你不知道树的实际形状,因此没有处理器事先知道它与哪些节点相关联。所以很难弄清楚哪些处理器应该发送,哪些应该接收。我不认为 MPI 是你的 friend 。

有一个工作列表风格的算法可能会更好,它包含要搜索的扩展树的节点。然后每个处理器可以转到工作列表,获取一个节点,将该节点扩展为子节点,并将子节点放回工作列表中。这将给出一个随机扩展的边界,而不是深度优先。

要深入优先,寻找工作的节点希望工作队列为它提供最深扩展节点,因此工作列表应该像优先级队列一样工作。通过这种方式,最深的节点首先由处理器扩展,具有深度优先的风格。

可能最容易实现这种效果的方法是让一个处理器扩展一个树节点,将扩展的集合推到工作列表的顶部作为集合;然后每个处理器从工作列表顶部的集合中获取工作。当处理器发现工作列表顶部的集合为空时,它可以弹出该集合并重试。

一个窃取 版本给你这种效果。第一个处理器生成一组工作;如果它在生成某个节点 P 的子节点时有很多工作,它会停止生成 P 的子节点,留下一些工作来生成 P 的其余子节点,并将注意力转移到 P 的已经生成的子节点上。这给出了深度优先的效果。其他节点有工作时执行相同;如果他们不这样做,他们就会从另一个节点窃取工作列表条目,这会导致他们开始向下搜索子树。

关于c++ - 并行化深度优先搜索 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26598926/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com