解决迷宫问题的迷宫

我知道解决迷宫问题是Stack Overflow中经常讨论的话题。这是一个可能让你感兴趣的问题。解决迷宫问题的迷宫

以n * n矩阵形式的迷宫将作为输入给出。每个元素将介于0-9之间。也会给出一系列数字，每个数字在0-9之间。矩阵和序列阵列的维度也是已知的。问题是要找到满足给定序列的从（0,0）到（n-1，n-1）的矩阵中所有可能的路径。路径只能向下或向右移动。必须使用线程来完成。

输入和输出格式如下─

实例给出的实施例中示出： Example1 http://gowthams.in/etc/1.PNG Example2 http://gowthams.in/etc/2.PNG Example3 http://gowthams.in/etc/3.PNG

每个线程可以打印某种其位置（i，j）的更新或数据结构稍后将被处理。

解决此问题的最佳方法是什么？

这是一个家庭作业问题，我被允许寻求帮助。我不寻找任何形式的代码。我只想向正确的方向指出几点。

谢谢！

来源

2012-11-04 Gowtham

@MitchWheat我很惊讶处理等待线程返回。我在进程中做了一个类似的问题，我只是使用wait（NULL）来确保所有进程在程序继续之前返回。线程的本质是并行处理，所以我不知道如何做到这一点。一旦我清楚了解如何做到这一点，我确信我可以自己实现代码。 – Gowtham

那么这是一个算法问题还是一个线程问题？如果后者发布您将使用单个线程的算法可能会有所帮助。另外，你的所有例子看起来都一样。 – IVlad

我更正了所有指向同一文件的图像的链接。 – nico

谢谢你的确切声明。

1）这句话似乎很不安：

您预计在矩阵每个条目创建线程并行确保扫描。

因为这意味着，对于N×N的矩阵你一定需要创建n个线程，这对我来说是太过分。

但是，您的解决方案更加危险：您要开始检查路线，并为每个检查创建一个新线程。这将创建指数为解决任务将需要的新线程数量。您肯定需要某种优化：这称为动态优化：您将存储在共享内存中是否可以使用单元格(i,j)来完成从idx th索引到目标单元格的序列。这样你就不必再多次解决同一个子任务。我建议你为每个这样的任务[i,j,idx]创建条件锁，并使用它来告诉当子线程完成时依赖它的线程。

2）多个路径对您来说不是问题：如果我正确地读取了赋值，您只是对这样的路径是否存在感兴趣，而不是找到所有解决方案。

我没有给出确切的解决方案，只是方向，根据要求。这也正是我倾向于帮助家庭佣工的方式。

来源

2012-11-04 12:41:37

问题的语言有点模糊。尽管它表示必须为每个元素创建一个线程，但实际上并不需要那样。按照我的方式，我将为每个检查路径时立即返回的元素创建三个线程。所以，正如你所说，可能会创建指数线程。但实际上，在实践中很少会创建，因为最多只有2或3条路径。另外，我觉得我最大的问题是多重路径。在第二个例子中，你可以看到输出格式。我不知道如何解决这个问题。感谢您的帮助！ – Gowtham

@Gowtham：你怎么知道最多有2或3条路径？ –

我无法确定。我正在研究平均情况与最坏情况。你知道任何与这个问题有关的标准算法吗？ – Gowtham

解决迷宫问题的迷宫

回答

相关问题