递归函数(迷宫求解器）-can'找不到漏洞;(）

Recursive function (maze solver) - can't find a bug;(((

本文关键字：找不到 漏洞 -can 递归函数 迷宫      更新时间：2023-09-26

我正在学习javascript，除了递归函数之类的东西之外，一切都很容易。我确实理解它们的工作方式，但在处理一个示例时，我意识到我无法捕获阻止它运行的错误。。。

我在下面有一个数组（map）（0是一个封闭的单元格，1表示路径是开放的），我正试图使用递归函数从左上角的单元格到右下角的单元格来"找到"走出这个"迷宫"的路径。。基本上只需要让函数"找到"这条1的路径。但它失败了；（

var map = [
        [1,1,0,0],
        [0,1,1,0],
        [0,0,1,0],
        [0,0,1,1]
    ]
function findpath(x,y) {
    if (x<0 || x>3 || y<0 || y>3) return false; //if it is outside of map
    if (x==3 && y==3) return true; // if it is the goal (exit point)
    if (map[y][x]==0) return false; //it is not open
    map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"
    if (findpath(x,y-1) == true) return true;
    if (findpath(x+1,y) == true) return true;
    if (findpath(x,y+1) == true) return true;
    if (findpath(x-1,y) == true) return true;
    map[y][x]=8; //unmark x,y as part of solution path outlined by "8"
    return false;
    };
findpath(0,0);

对"它失败了"的描述很少是有用的错误报告。

为了让别人帮助你，他们需要更多的细节。

在本例中，导入详细信息来自JavaScript错误控制台。您应该始终在问题中包含任何错误消息。

然而，由于你的代码很短，我可以将其剪切并粘贴到我的控制台中，在那里我得到了消息：

RangeError: Maximum call stack size exceeded

这意味着您的函数递归过深。你要么

  • 如果你的谜题逻辑不好，你就会一次又一次地重复使用相同的值
  • 这个谜题太复杂了，你不能像那样递归地解决它

您需要添加console.log语句，观察代码在做什么，并了解为什么它会深入到这个层次。

如果是逻辑错误，请修复该逻辑错误。（提示：我很确定——你永远不会在地图上标记你去过的地方，所以它会在同一地点来回自由地移动）。

如果不是，那么您需要使用一些更高级的技巧来处理递归，例如使用生成器函数并将您所做的更改单独存储在映射中。

快速答案：

它锁定在一个循环中是因为检查的顺序。

从0:0开始，然后尝试0:1。然后从0:1-"；嗯。。。0:0看起来很有希望。我们去那儿吧；。所以回到0:0…所以它锁定了。。。尝试离开回溯最后：

if(findpath(x+1,y)) return true;    
if(findpath(x,y+1)) return true;    
if(findpath(x,y-1)) return true;
if(findpath(x-1,y)) return true;

这只需交换问题就可以让你摆脱困境。如果你从3:3开始尝试到达0:0，你将再次被锁定。缺少的是一种标记到访广场的方式。

我认为你正在尝试实现一个a*算法

更新：

这是你的想法。刚刚添加了您几乎实现的回溯检查。

<html>
    <head>
    </head>
    <body>
        <script>
            var map = [
            [1,1,0,0],
            [0,1,1,0],
            [1,1,1,0],
            [1,0,1,1]
        ]
        
    var goalx = 0;
    var goaly = 3;
    
    console.log();
    
    function findpath(x,y) {
        
        
        // illegal move check
        if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map
        if (map[y][x]==0) return false; //it is not open
        
        // end move check
        if (x== goalx && y== goaly){
            console.log('Reached goal at: ' + x + ':' + y);
            return true; // if it is the goal (exit point)
        }
        
        if(map[y][x] == 9 || map[y][x] == 8)
            return false;
        
        console.log('Im here at: ' + x + ':' + y);
        
        map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"
        
        if(findpath(x+1,y)) 
            return true;    
        if(findpath(x,y+1)) 
            return true;    
        if(findpath(x,y-1))
            return true;
        if(findpath(x-1,y)) 
            return true;                    
        
        map[y][x]=8; //unmark x,y as part of solution path outlined by "8"
        
        return false;
    };
    
    findpath(3, 3);
        </script>
    </body>
</html>
相关文章：