当前位置： 文江博客 话题详情

迷宫算法的问题

发布于 2024-08-01 14:09:22 字数 894 浏览 10 评论 0 原文

我在设计用于解决迷宫问题的算法时遇到问题。

我使用了这里的算法。http://www.cs.bu.edu/ education/alg/maze/

FIND-PATH(x, y)

  1. if (x,y 在迷宫外) return false
  2. if (x,y 是目标) return true
  3. if (x,y not open) return false
  4. 标记 x ,y 作为解决方案路径的一部分
  5. if (FIND-PATH(x,y 的北边) == true) 返回 true
  6. if (FIND-PATH(x,y 的东边) == true) 返回 true
  7. if (FIND-PATH(South of x,y) == true) return true
  8. if (FIND-PATH(West of x,y) == true) return true
  9. 取消标记 x,y 作为解决方案路径的一部分
  10. 返回错误

这是一个递归解决方案，我对其进行了修改，使其即使在找到退出后仍会继续，以便它也可以找到其他解决方案。 它似乎有效，只是它似乎找到了我所知道的可能解决方案总数的一半。

  1. if (x,y is goal) return true 更改为 return false。

有人知道这种算法可能存在什么问题，导致可能的解决方案总数只有一半吗？ 我也遇到了查找死胡同路径总数的问题，对此有什么建议吗？

原文

I am having a problem with a algorithm that is designed to solve mazes.

I used an algorithm from here.http://www.cs.bu.edu/teaching/alg/maze/

FIND-PATH(x, y)

  1. if (x,y outside maze) return false
  2. if (x,y is goal) return true
  3. if (x,y not open) return false
  4. mark x,y as part of solution path
  5. if (FIND-PATH(North of x,y) == true) return true
  6. if (FIND-PATH(East of x,y) == true) return true
  7. if (FIND-PATH(South of x,y) == true) return true
  8. if (FIND-PATH(West of x,y) == true) return true
  9. unmark x,y as part of solution path
    1. return false

It is a recursive solution , i modified it such that it will continue even after finding exit so that it can find other solutions as well. It seems to work , just that it seems to find half the total number of solutions that i know are possible.

  1. if (x,y is goal) return true is changed to return false.

Anyone know what might be the problem with such an algorithm resulting in half the number of total possible solutions? I also have a problem into finding the total number of dead end paths, any suggestions on that?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（5）

痴骨ら 2024-08-08 14:09:22

这是一个示例迷宫

####################
#S #  #       #    #
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #   #  #   ###
# ### ### ## # #####
#  #      #       E#
####################

This is a sample maze

####################
#S #  #       #    #
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #   #  #   ###
# ### ### ## # #####
#  #      #       E#
####################
回复 原文
追星践月 2024-08-08 14:09:22

对于死胡同的数量，您需要这样的东西：

3.5 if (x,y 的北边不开放) 和 (x,y 的南边不开放) 和 (x,y 的西边不开放) 和 (x 的东边， y 未打开）死胡同++

For the number of dead ends, you need something like that:

3.5 if (North of x,y not open) and (South of x,y not open) and (West of x,y not open) and (East of x,y not open) deadends++

回复 原文
风吹雪碎 2024-08-08 14:09:22

我尝试用java简单地实现该算法。 我的结论是，您描述的算法有效，即使对于查找多条路径也是如此。 或者，您可能想出了一个比我更聪明的测试用例。 （请发布你的迷宫，以便我可以尝试我的算法）

我的死胡同计数器的实现可能不是最有效的，但它完成了工作。 对于每个当前访问的 OPEN 节点，它会检​​查 4 个周围节点：

  • 如果至少有一个邻居是 OPEN，则当前节点不是死胡同
  • 如果访问了多个邻居，则当前节点不是死胡同
  • 如果只有一个节点是已访问（我们在上一步中来自的那个）并且没有其他邻居打开，当前节点是死胡同

这是我编写的 java 代码（注意！相当长）。 如果您愿意，另一种方法是将路径存储在堆栈上，每次将节点设置为“VISITED”时压入一个节点，每次将其设置回“OPEN”时弹出一个节点。 每次达到目标时，应复制并保存保存当前路径的堆栈。

如果删除标记为“死胡同调查步骤”的 if 块，则此实现几乎与问题中描述的完全相同。

package test;

import java.util.HashSet;
import java.util.Set;

public class MazeSolver {

final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;

static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };

// This is what the field looks like:
//  
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0

static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions

// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();

public static void main(String[] arg) {
    System.out.println("Initial maze:");
    printField();

    findPath(xStart, yStart);

    System.out.println("Number of solutions: " + nrSolutions);
    System.out.println("Number of dead ends: " + deadEnds.size());
}

private static void findPath(int x, int y) {

    if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
        return;
    } else if (field[x][y] == GOAL) { // Step 2
        nrSolutions++;
        System.out.println("Solution nr " + nrSolutions + ":");
        printField();
        return;
    } else if (field[x][y] != OPEN) { // Step 3
        return;
    } else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
        int uniqueNodeId = x + y * width;
        deadEnds.add(uniqueNodeId); // Report as dead end
        return;
    }

    field[x][y] = VISITED; // Step 4

    findPath(x, y - 1); // Step 5, go north
    findPath(x + 1, y); // Step 6, go east
    findPath(x, y + 1); // Step 7, go south
    findPath(x - 1, y); // Step 8, go west

    field[x][y] = OPEN; // Step 9

    // Step 10 is not really needed, since the boolean is intended to
    // display only whether or not a solution was found. This implementation
    // uses an int to record the number of solutions instead.
    // The boolean return value would be (nrSolutions != 0)
}

private static boolean isDeadEnd(int x, int y) {
    int nrVisitedNeighbours = 0;

    if (y > 0) { // If northern neighbour exists
        if (field[x][y - 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y - 1] != WALL) {
            return false;
        }
    }
    if (x < width - 1) { // If eastern neighbour exists
        if (field[x + 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x + 1][y] != WALL) {
            return false;
        }
    }
    if (y < height - 1) { // If southern neighbour exists
        if (field[x][y + 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y + 1] != WALL) {
            return false;
        }
    }
    if (x > 0) { // If western neighbour exists
        if (field[x - 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x - 1][y] != WALL) {
            return false;
        }
    }

    if (nrVisitedNeighbours > 1) { // Circular path scenario
        return false;
    }

    return true; // The exhaustive result of this check: this is a dead
    // end
}

private static void printField() {
    for (int yy = 0; yy < field[0].length; yy++) {
        for (int xx = 0; xx < field.length; xx++) {

            System.out.print(field[xx][yy] + " ");
        }
        System.out.println();
    }
    System.out.println();
}
}

上面的算法报告了示例迷宫的四个不同的解决方案路径和两个死胡同，该迷宫被硬编码到代码中。

<编辑>
您获得的解决方案路径太少的原因可能是对解决方案路径的误解吗？ 例如，考虑这个迷宫：

######
##   #
## # #
#S   #
##E###
######

这个迷宫只有一条有效的解决方案路径。 这是因为您只能访问每个节点一次，因此绕圆形路径不是有效的解决方案路径，因为这将访问 S 以东和 E 以北的节点两次。 您使用的算法隐含了解决方案路径的定义。

如果允许多次访问同一个节点，就会有无限多个解决方案，因为您可以绕圈 1、2、3 ... 无限多次。

正如您所说，每次将节点设置为“VISITED”时，我都会增加路径长度，并在每次设置时减少路径长度将已访问的节点恢复为打开状态。

为了记录最短路径长度，我还有一个 ShortestPath int 值，我将其初始化为 Integer.MAX_VALUE。 然后，每次达到目标时，我都会这样做：

if(pathLength < shortestPath){
    shortestPath = pathLength;
}

至于死胡同……我尝试用手数它们，我认为 9 似乎是正确的。 这是 Sareen 发布的迷宫，但标记了死胡同（由手）与 D：

####################
#S # D#      D#D  D#
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #D  #D #   ###
# ### ### ## # #####
# D#D     #D      E#
####################

你还能找到更多吗？
还是我误解了你所说的死胡同的意思？
我认为死胡同意味着：一个只能从一个方向到达的节点。

示例 1：

######
## ###
## ### 
## ### 
#S  E#
######

上面的迷宫有一个死胡同。

例2：

######
##  ##
##  ## 
##  ## 
#S  E#
######

上面的迷宫没有死胡同。 即使您位于最北边的可访问节点之一，仍然有两个相邻的非 WALL 方块。

您对死胡同还有其他定义吗？

I tried making a simple-minded implementation of the algorithm in java. My conlusion was that the algorithm you described works, even for finding multiple paths. Or, possibly, you managed to think of a more clever test case than me. (Please post your maze so I can try my algorithm on it)

My implementation of the dead end counter is probably not the most efficient one, but it gets the job done. For each current OPEN node that is visited, it checks the 4 surrounding nodes:

  • If at least one neighbour is OPEN, current node is not a dead end
  • If more than one neighbour is VISITED current node is not a dead end
  • If only one node is VISITED (the one we came from in the previous step) and no other neighbour is OPEN, current node is a dead end

This is the java code I wrote (beware! pretty long). An alternative would be, if you wish, to store the path on a stack, pushing a node each time it is set to VISITED and popping a node each time it is set back to OPEN. Each time the GOAL is reached, the stack holding the current path should be copied and saved.

If the if block marked with a comment as "dead-end-investigation-step" is removed, this implementation is almost exactly equal to the one described in the question.

package test;

import java.util.HashSet;
import java.util.Set;

public class MazeSolver {

final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;

static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };

// This is what the field looks like:
//  
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0

static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions

// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();

public static void main(String[] arg) {
    System.out.println("Initial maze:");
    printField();

    findPath(xStart, yStart);

    System.out.println("Number of solutions: " + nrSolutions);
    System.out.println("Number of dead ends: " + deadEnds.size());
}

private static void findPath(int x, int y) {

    if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
        return;
    } else if (field[x][y] == GOAL) { // Step 2
        nrSolutions++;
        System.out.println("Solution nr " + nrSolutions + ":");
        printField();
        return;
    } else if (field[x][y] != OPEN) { // Step 3
        return;
    } else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
        int uniqueNodeId = x + y * width;
        deadEnds.add(uniqueNodeId); // Report as dead end
        return;
    }

    field[x][y] = VISITED; // Step 4

    findPath(x, y - 1); // Step 5, go north
    findPath(x + 1, y); // Step 6, go east
    findPath(x, y + 1); // Step 7, go south
    findPath(x - 1, y); // Step 8, go west

    field[x][y] = OPEN; // Step 9

    // Step 10 is not really needed, since the boolean is intended to
    // display only whether or not a solution was found. This implementation
    // uses an int to record the number of solutions instead.
    // The boolean return value would be (nrSolutions != 0)
}

private static boolean isDeadEnd(int x, int y) {
    int nrVisitedNeighbours = 0;

    if (y > 0) { // If northern neighbour exists
        if (field[x][y - 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y - 1] != WALL) {
            return false;
        }
    }
    if (x < width - 1) { // If eastern neighbour exists
        if (field[x + 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x + 1][y] != WALL) {
            return false;
        }
    }
    if (y < height - 1) { // If southern neighbour exists
        if (field[x][y + 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y + 1] != WALL) {
            return false;
        }
    }
    if (x > 0) { // If western neighbour exists
        if (field[x - 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x - 1][y] != WALL) {
            return false;
        }
    }

    if (nrVisitedNeighbours > 1) { // Circular path scenario
        return false;
    }

    return true; // The exhaustive result of this check: this is a dead
    // end
}

private static void printField() {
    for (int yy = 0; yy < field[0].length; yy++) {
        for (int xx = 0; xx < field.length; xx++) {

            System.out.print(field[xx][yy] + " ");
        }
        System.out.println();
    }
    System.out.println();
}
}

The algorithm above reports four different solution paths and two dead ends to the example maze which is hardcoded into the code.

<EDIT>
Might the reason for why you get too few solution paths be a misinterpretation of what is a solution path? For example, consider this maze:

######
##   #
## # #
#S   #
##E###
######

This maze has only one valid solution path. This is because you are only allowed to visit each node once, so going around the circular path is not a valid solution path since that would visit the node east of S and north of E twice. This definition of a solution path is implied by the algorithm that you use.

If one were to allow visiting the same node multiple times, there would be infinitely many solutions, as you could go around the circle 1, 2, 3 ... to infinitely many times.
</EDIT>

<EDIT2>

Exactly as you say, I increase the pathLength each time I set a node to VISITED, and decrease the path length each time I set a VISITED node back to OPEN.

To record the shortest path length I also have a shortestPath int value which I initiate to Integer.MAX_VALUE. Then, each time I have reached the goal, I do this:

if(pathLength < shortestPath){
    shortestPath = pathLength;
}

As for the dead ends... I tried counting them by hand and I thought 9 seemed right. Here is the maze posted by Sareen, but with the dead ends marked (by hand) with a D:

####################
#S # D#      D#D  D#
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #D  #D #   ###
# ### ### ## # #####
# D#D     #D      E#
####################

Can you find any more?
Or did I misinterpret what you meant by dead end?
I thought dead end means: A node to which you can only come from one direction.

Example 1:

######
## ###
## ### 
## ### 
#S  E#
######

The maze above has one dead end.

Example 2:

######
##  ##
##  ## 
##  ## 
#S  E#
######

The above maze has no dead ends. Even if you are at one of the accessible nodes furthest to the north, there are still two adjacent non-WALL squares.

Do you have another definition of dead end?
</EDIT2>

回复 原文
提笔书几行 2024-08-08 14:09:22

您不需要尝试找到一种穿过迷宫的方法，而是需要找到（并因此绘制）多种穿过迷宫的方法。

为此，您需要标记您去过的位置（在特定路径上）。 如果您到达已经去过的地点，则需要将该路线标记为死胡同。

递归函数仍然是可行的方法，但请确保通过递归函数传递 (placesIhaveBeen) 结构。

当到达 N、S、E、W 都被阻塞的点时，递归循环需要中断。 （你以前来过那里，你不能朝那个方向走，它在迷宫外面）
当您达到目标时，递归循环也需要中断。

如果达到目标 - 将全局变量增加一。
如果你无处可去——将你的死胡同增加一个。

我无法为此编写 pcode（这会花费太长时间），但我相信秘密就在一个函数中，如果 N、S、E 和 W 都被阻止，该函数将返回 true。

补充我最初的答案

关于为什么我将我去过的区域视为“封锁”，以及为什么我将它们视为死胡同......

      ########
      #      #  
      # #### #
####### #  # #
        #  # #
####### #  # #
      # #### #
      #      #  
      ########

我将上述迷宫部分分类为死胡同，如果不将我去过的地方视为封锁区域，我不知道如何识别它。

我意识到这会导致以下内容也出现死胡同，但我看不到解决方法。

      #######
      #     #  
      # ### #
####### #G# #
        # # #
####### #   #
      # ### #
      #     #  
      #######

Rather than trying to find one way through the maze, you need to find (and therefore map) multiple ways through the maze.

In order to do this, you need to mark where you've been (on a particular path). If you reach a point you've already been to, you need to flag that route as a dead end.

A recursive function is still the way to go, but make sure that you pass the (placesIhaveBeen) structure through the recursive function.

The recursive loop needs to break when you get to a point where N,S,E,W are all blocked. (You've been there before, you can't go in that direction, it's outside the maze)
The recursive loop also needs to break when you reach your target.

If you get to your target - increase a Global Variable by one.
If you've nowhere to go - increase your dead-ends by one.

I can't write the pcode for this (it'll take too long), but I believe that the secret is in a function that returns true if N, S, E and W are all blocked.

Addition to my initial answer

With regard to why I treat areas I've been to as "blocked", and why I treat them as dead ends....

      ########
      #      #  
      # #### #
####### #  # #
        #  # #
####### #  # #
      # #### #
      #      #  
      ########

I would classify the above maze part as a dead end, and I can't see how I can identify it as such without treating places I've been to as blocked areas.

I realise that this would cause the following to also show dead ends, but I can't see a way around it. 

      #######
      #     #  
      # ### #
####### #G# #
        # # #
####### #   #
      # ### #
      #     #  
      #######
回复 原文
独享拥抱 2024-08-08 14:09:22

似乎缺少的是检查 X&Y 是否已被标记为解决方案的一部分，如果是，我们将中止。 （这应该是第 3.5 点上的某个地方）

如果不是一个可能存在循环的迷宫，那么某个地方会无限期地运行并炸毁堆栈

，从我读到的内容来看，该算法基于只有 1 个解决方案

R的迷宫

what seems to be missing is the check if X&Y has already been marked as part of the solution, and if so we abort. (this should be somewhere on point 3.5)

If not a maze with a possible loop somewhere would run indefinately and blow up the stack

by the way, from what I read the algorithm is based on a maze with only 1 solution

R

回复 原文
~没有更多了~

关于作者

看春风乍起

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

苍风燃霜

文章 0 评论 0

我的黑色迷你裙

文章 0 评论 0

悸初

文章 0 评论 0

撧情箌佬

文章 0 评论 0

森罗

文章 0 评论 0

lyn1245

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文