当开始和结束节点相距太远时 BFS 算法失败

Question

我正在为广度优先搜索开发一个寻路可视化工具，该算法在“开始”和“结束”相距大约 15 个单位时有效，但之后它要么需要很长时间来计算，要么就是无法工作。我认为我的代码可能效率低下，但我对如何修复它感到困惑。非常感谢任何帮助。

这是我现在拥有的用于 BFS 的 JavaScript 代码，它使用 id 来定位 table 中的节点：

      var start = document.getElementsByClassName("start")[0];

      let q = new Queue();
      q.enqueue(start);
      
      while(!q.isEmpty()){
          var x = q.dequeue();
      
          var row = parseInt(x.id.split('-')[0]);
          var col = parseInt(x.id.split('-')[1]);
          //go up
          if((row-1)>=0){
              var u = document.getElementById((row-1)+"-"+col);
              if(u.className=="end"){
                  break;
              }else if(u.className!="start" || u.className!="visited"){
                  u.className="visited";
                  q.enqueue(u);
              }
          }
          //go down
          if((row+1)<=20){
              var d = document.getElementById((row+1)+"-"+col);
              if(d.className=="end"){
                  break;
              }else if(d.className!="start" || d.className!="visited"){
                  d.className="visited";
                  q.enqueue(d);
              }
          }
          //go right
          if((col+1)<=50){
              var r = document.getElementById(row+"-"+(col+1));
              if(r.className=="end"){
                  break;
              }else if(r.className!="start" || r.className!="visited"){
                  r.className="visited";
                  q.enqueue(r);
              }
          }
          //go left
          if((col-1)>=0){
              var l = document.getElementById(row+"-"+(col-1));
              if(l.className=="end"){
                  break;
              }else if(l.className!="start" ||       l.className!="visited"){
                  l.className="visited";
                  q.enqueue(l);
              }
          }

这是界面，绿色是开始节点，红色是结束节点，蓝色是bfs算法

Answer 1

避免混淆的一个好方法是像这样将呼吸优先搜索算法与其余代码分开。它将允许您单独测试每个部分。

function bfs () {

  let q = new Queue();
  q.enqueue(start);

  while (! q.isEmpty()) {
    let x = q.dequeue();

    if (! visited(x)) {
      process(x);
      if (exit()) break;
      q.enqueue( adjacent(x) );
    }
  } 
}

此外，如果您想为算法设置动画，则需要使用 setTimeout 并且每次 setTimeout 调用仅执行 1 圈循环。如果不这样做，由于浏览器事件循环的性质，您将只能在算法找到“结束”后看到结果。你看，当 javascript 是运行时，浏览器无法刷新屏幕。如果你想看到一些变化，你需要执行一些指令然后让浏览器刷新并继续执行更多的指令。冲洗并重复，你就有了一个动画。 setTimeout 是允许您重新开始执行的函数。

这是一个例子：

let start = "x16y2";
let end   = "x25y4";

function main () {
   init();

   step1();
   
   function step1 () {
     bfs(step2); 
   }
   function step2 () {
     dfs(step1); 
   }
}

// breath first search (bfs)

function bfs (cont) {
   clearVisited();
   
   let queue = new STACK_QUEUE("shift");

   queue.add(start);
   bfs_cont();
/*
   while (! queue.isEmpty()) {
     let x = queue.retrieve();
     if (! visited(x)) {
       process(x);
       if (exit()) break;
       queue.add( adjacent(x) );
     }
   }
*/   
  function bfs_cont () {

     if (queue.isEmpty()) return;

     let x = queue.retrieve();

     if (! visited(x)) {
       process(x);
       if (exit()) {setTimeout(cont, 2000); return;}
       queue.add( adjacent(x) );
     }

     setTimeout(bfs_cont, 10);
  }
}

// depth first search (dfs)

function dfs (cont) {
   clearVisited();

   let stack = new STACK_QUEUE("pop");

   stack.add(start);
   dfs_cont();
/*
   while (! stack.isEmpty()) {
     let x= stack.retrieve();
     if (! visited(x)) {
       process(x);
       if (exit()) break;
       stack.add( adjacent(x) );
     }
  }
*/
  function dfs_cont () {

     if (stack.isEmpty()) return;

     let x = stack.retrieve();

     if (! visited(x)) {
       process(x);
       if (exit()) {setTimeout(cont, 2000); return;}
       stack.add( adjacent(x) );
     }

     setTimeout(dfs_cont, 10);
  }
}



function exit () {
  return visited(end);
}

function visited (id) {
  let e = document.getElementById(id);
  return hasClass(e, "visited");
}

function process (id) {
  let e = document.getElementById(id);
  addClass(e, "visited");
}

function adjacent (id) {
   let pos_y = id.indexOf('y');
   let x = 1 * id.substring(1,pos_y);
   let y = 1 * id.substr(pos_y+1);
   let res = [];
   // up
   if (x > 0)    res.push("x"+(x-1)+"y"+y);
   // left 
   if (y > 0)    res.push("x"+x+"y"+(y-1));
   // down
   if (x < 32-1) res.push("x"+(x+1)+"y"+y);
   // right 
   if (y < 20-1) res.push("x"+x+"y"+(y+1));
   
   return radomizeIt(res);
}

function clearVisited () {
  var list;
  while (true) {
    list = document.getElementsByClassName("visited");
    if (list.length <= 0) break;
    for (let i = 0 ; i < list.length ; i += 1) {
      removeClass(list[i], "visited");
    }
  }
}

function init() {
  let c =  document.createElement("div");
  c.setAttribute("class", "container");
  c.setAttribute("id", "container");
  document.body.appendChild(c);

  let container = document.getElementById("container");
  for (let y = 0 ; y < 20 ; y += 1) {
    for (let x = 0 ; x < 32 ; x += 1) {
      let e = document.createElement("div");
      e.setAttribute("class", "cell");
      e.setAttribute("id", "x"+x+"y"+y);
      e.style.top = ""+(y*8)+"px";
      e.style.left = ""+(x*8)+"px";
      container.appendChild(e);
    }
  }

  addClass(document.getElementById(start), "start");
  addClass(document.getElementById(end),   "end");
}

function addClass(e, cssClass) {
  if (!e) return;
  let _class = e.getAttribute("class");
  if (! hasClass(e, cssClass)) {
    _class += " "+cssClass;
    e.setAttribute("class", _class);
  }
}

function removeClass(e, cssClass) {
  if (!e) return;
  let _class = e.getAttribute("class");
  if (hasClass(e, cssClass)) {
    _class = _class.replace(cssClass, "");
    _class = _class.replace("  ", " ");
    e.setAttribute("class", _class);
  }
}

function hasClass(e, cssClass) {
  if (!e) return false;
  let _class = e.getAttribute("class");
  if (_class === null) return false;
  return _class.indexOf(cssClass) >= 0;
}

function STACK_QUEUE (fn) {
  var self = this;
  self.arr = [];

  self.isEmpty = function () {
    return self.arr.length === 0;
  };

  self.add = function (e) {
    if (Array.isArray(e)) {
      self.arr = self.arr.concat(e);
    } else {
      self.arr.push(e);
    }
    return self;
  };

  self.retrieve = function () {
    return self.arr[fn]();
  };
}

function radomizeIt (arr) {
  let py0 = start.indexOf('y');
  let x0 = 1* start.substring(0,py0);
  let y0 = 1* start.substr(py0);

  let res = arr.slice();
  res.sort((a,b)=>(dist(b)-dist(a)));
/*  
  for (let i = 0 ; i < arr.length-1 ; i += 1) {
    let j = Math.floor(Math.random() * (arr.length - i));
    swap(i,j);
  }
*/
  return res;

  function swap (i,j) {

   if (i === j) return;
    var t = res[i];
    res[i] = res[j];
    res[j] = t;
  }
  function dist (id) {
    let py = id.indexOf('y');
    let x = 1* id.substring(0,py0);
    let y = 1* id.substr(py0);
    let dx = (x-x0);
    let dy = (y-y0);
    return dx*dx+dy*dy;
  }
} 

main();

.container {
  position: relative;
  width: 320px;
  height: 200px;
}

.cell {
  position: absolute;
  width: 5px;
  height: 5px;
  border: 1px solid black;
  backgound-color: white;
}

.visited {
  background-color: #39cccc;
}

.cell.start {
  background-color: #3c9970;
}

.end {
  background-color: #ff7066;
}

.visited.end {
  background-color: #ff0000;
}

当开始和结束节点相距太远时 BFS 算法失败

BFS algorithm fails when start and end nodes are too far apart

javascript

html

breadth-first-search

path-finding