Maze solving with constraints
I know solving mazes is a frequently discussed topic here on Stack Overflow. Here is a problem that might interest you all.
A maze in the form of an*n matrix will be given as input. Each element would lie between 0-9. A sequence of numbers, each between 0-9 again would also be given. The dimension of the matrix and the sequence array is also known. The question is to find all possible paths in the matrix from (0,0) to (n-1,n-1) that satisfies the given sequence. The path can move down,right or down+right only. Has to be done using threads.
The input and output format are illustrated in the examples given below-
Examples: Example1 http://gowthams.in/etc/1.PNG Example2 http://gowthams.in/etc/2.PNG Example3 http://gowthams.in/etc/3.PNG
Each thread can either print its position (i,j) or update in some sort of data structure to be processed later.
What is the best way to approach this problem?
This is a homework problem and I am allowed to ask for help. I am not looking for code of any sort. I just want a few pointers in the right direction.
Thanks!
Thank you for the exact statement.
1) This sentence seems pretty disturbing:
You are expected to create threads for each entry in the matrix to ensure parallel scanning.
Because that means that for matrix NxN you surely need to create N2 threads, which for me is rather too much.
However your solution is even more dangerous: you want to start checking the routes and for each check create a new thread. This will create exponential number of new threads that will be needed in order to solve the task. You for sure will need some sort of optimization: this is called dynamic optimization: you store in the shared memory whether cell (i,j) can be used to finish the sequence taken from idx th index to the target cell. That way you will never have to solve the same subtask more than once. I suggest you create conditional locks for each such task [i,j,idx] and use it in order to tell the threads dependent on it when the child thread finishes.
2)multiple paths are not issue for you: if I read the assignment correctly you are just interested in whether such path exists, but not to find all solutions.
I am not giving exact solution, just directions, as requested. This is also exactly the way I tend to help homeworkers.
链接地址: http://www.djcxy.com/p/79618.html上一篇: 在python中使用递归解决迷宫问题
下一篇: 迷宫解决约束