3

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

将给出一个 *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) 或更新某种数据结构以供稍后处理。

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

这是一个家庭作业问题，我可以寻求帮助。我不是在寻找任何类型的代码。我只想要一些正确方向的指示。

谢谢！

4

1 回答 1

3

谢谢你的确切陈述。

1）这句话似乎很令人不安：

您应该为矩阵中的每个条目创建线程以确保并行扫描。

因为这意味着对于矩阵 NxN，您肯定需要创建 N 2 个线程，这对我来说太多了。

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

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

我没有按照要求给出确切的解决方案，只是给出了指示。这也正是我倾向于帮助家庭工人的方式。

于 2012-11-04T12:41:37.123 回答