Bishop:找到从 A 到 B 的最短路径

Bishop: find shortest path from A to B

我目前正在尝试为以下问题找到解决方案:给定一个 8x8 的棋盘和一个主教和障碍物的数量,需要找到从当前主教位置到其他特定位置的最短路径。

更新

感谢所有响应者,我已经实施了一个解决方案。这是:

https://jsfiddle.net/heximal/teya2pcc/

  /**************************************
    Chess board logic functions
  ***************************************/
  function p(x, y) {
    return {
      x: x,
      y: y
    };
  }

  function pos_equals(p1, p2) {
    if (p1 == null || p2 == null) return false;
    return p1.x == p2.x && p1.y == p2.y;
  }

  function human_pos(pos) {
    return pos2alpha(pos.x, pos.y);
  }

  function pos2alpha(x, y) {
    return alpha[x] + (y + 1);
  }

  function intpos2alpha(intpos) {
    y = Math.trunc(intpos / 10);
    x = intpos - (y * 10);
    return alpha[x] + (y + 1);
  }

  function pos2int(pos) {
    return pos.y * 10 + pos.x;
  }

  function int2pos(intpos) {
    var y = Math.trunc(intpos / 10);
    var x = pos_int - (y * 10);
    return p(x, y);
  }

  function pos2path(pos, delim) {
    if (pos == null) return "[]";
    var res = [];
    for (var i = 0; i < pos.length; i++) {
      var p1 = pos[i];
      var x = 0,
        y = 0;
      if (typeof p1 === 'object') {
        x = p1.x;
        y = p1.y;
      } else {
        y = Math.trunc(p1 / 10);
        x = p1 - (y * 10);
      }
      res.push(pos2alpha(x, y));
    }
    if (delim == null) delim = "->"
    return res.join(delim);
  }

  function cell_color(location) {
    var color = 1;
    if (location.x % 2 == 0 && location.y % 2 == 0)
      color = 1;
    if (location.x % 2 != 0 && location.y % 2 == 0)
      color = 0;
    if (location.x % 2 == 0 && location.y % 2 != 0)
      color = 0;
    if (location.x % 2 != 0 && location.y % 2 != 0)
      color = 1;
    return color;
  }

  function board_obj(pos) {
    var res = 0;
    if (pos.x < 0 || pos.x > 7 || pos.y < 0 || pos.y > 7)
      res = "o";
    else
      res = board[7 - pos.y][pos.x];
    return res;
  }


  /**************************************
    Major find path functions
  ***************************************/
  var iterations = 0;
  // let's prevent scanning with particular iterations count
  // to avoid very long execution
  var max_iterations_count = 10000;

  /*
      ----------------    
      | nw |    | ne |
      ----------------
      |    | Bs |    |
      ----------------
      | sw |    | se |
      ----------------
  */

  var nw_vector = p(-1, 1);
  var ne_vector = p(1, 1);
  var se_vector = p(1, -1);
  var sw_vector = p(-1, -1);

  function find_path() {
    if (target_pos == null || bishop_pos == null) {
      alert("bishop and target both must be set");
      return;
    }
    var path = [];
    var start = new Date().getTime();
    if (cell_color(bishop_pos) == cell_color(target_pos)) {
      path = search_bfs(bishop_pos);
    }
    var end = new Date().getTime();
    var dur = end - start;
    output_result(path, dur);
  }

  function vector_point(pos, vector, shift) {
    return p(pos.x + shift * vector.x, pos.y + shift * vector.y);
  }

  function possible_moves_from(pos) {
    var vectors = [{
      active: true,
      vector: se_vector
    }, {
      active: true,
      vector: sw_vector
    }, {
      active: true,
      vector: nw_vector
    }, {
      active: true,
      vector: ne_vector
    }];
    var shift = 1;
    var res = [];
    while (vectors[0].active || vectors[1].active || vectors[2].active || vectors[3].active) {
      for (var j = 0; j < vectors.length; j++) {
        if (vectors[j].active) {
          iterations++;
          var v_pos = vector_point(pos, vectors[j].vector, shift);
          var l_obj = board_obj(v_pos);
          if (l_obj == "o" || l_obj == "b") {
            vectors[j].active = false;
          } else {
            res.push(v_pos.y * 10 + v_pos.x);
          }
        }
      }
      shift++;
    }
    return res;
  }

  function search_bfs(original_pos) {
    // reset global iterations counter
    iterations = 0;
    var original_pos_int = pos2int(original_pos);

    // create undirected graphs with all possible bishop positions
    var vertices = {};

    var pos = p(0, 0);
    // if bishop cell color differs from color of left-bottom cell color (A1)
    // than start with cell (A2)
    if (cell_color(pos) != cell_color(original_pos)) {
      pos.x = 1;
    }

    // let's convert cell positions {x: n, y: m} to integer representation
    // int_pos = y+10 + x, e.g. B2 = 1 * 10 + 1 = 11
    var target_pos_int = pos2int(target_pos);
    for (var i = 0; i < 32; i++) {
      var intpos = pos2int(pos);
      var l_obj = board_obj(pos);
      // if pos doesn't contain obstacle
      // get a collection of all moves that bishop can make from pos
      if (l_obj != "o") {
        var possible_moves = possible_moves_from(pos);
        vertices[intpos] = possible_moves;
      }
      pos.x += 2;
      if (pos.x > 7) {
        pos.x = pos.x % 2 == 0 ? 1 : 0;
        pos.y++;
      }
    }

    // initialize BFS queue (enqueue bishop position)
    var queue = [original_pos_int];
    // initialize BFS explored nodes collection
    var explored = [original_pos_int];
    // initialize parent nodes map
    var parents = {};
    while (queue.length > 0) {
      iterations++;
      if (iterations >= max_iterations_count) {
        console.log("max iterations exceeded (" + max_iterations_count + "). stop searching");
        return [];
      }
      var pos_int = queue.pop();
      var y = Math.trunc(pos_int / 10);
      var x = pos_int - (y * 10);
      var pos = p(x, y);
      var possible_moves = vertices[pos_int];
      if (possible_moves == null) continue;
      for (var j = 0; j < possible_moves.length; j++) {
        var possible_move = possible_moves[j];
        if (explored.indexOf(possible_move) < 0) {
          parents[possible_move] = pos_int;
          explored.push(possible_move);
          if (target_pos_int == possible_move) {
            queue = [];
            break;
          } else {
            queue.splice(0, 0, possible_move);
          }
        }
      }
    }
    // start backward traverse from target to bishop position
    // and compose result path
    var path = [];
    var current = target_pos_int;
    while (current != null) {
      path.push(current);
      current = parents[current];
    }
    // if path contains only one element, then path is not found
    return path.length > 1 ? path : [];
  }

一件重要的事情你在使用 BFS 时必须牢记:当你将元素入队时,你必须将它放在队列的开头而不是队列的结尾。

这就是我之前没能得到想要的结果的原因。

要弄清楚最短路径指的是最少的移动次数还是最少走过的田地数。无论哪种情况,都可以使用修改后的 depth-first search; 来解决问题。一个人必须存储当前的最短路径,这使得迭代实现成为可取的,因为它可能无法从调用堆栈中显式读取信息。

  1. 创建一个无向图,其中节点数为 32 减去障碍物数。每个节点代表一个黑色方块(对于黑色象)或白色方块(对于白色象)。每条边代表两个方块之间可能的移动。

  2. 在可以直接移动的任意两个节点之间添加一条边。如果您正在寻找最少的移动次数 - 该图可能未加权。如果您正在寻找最小移动距离 - 根据移动长度设置边缘权重。

  3. 您现在要做的就是找到两个所需节点之间的最短路径。如果图形未加权,则使用 BFS 或 modified-DFS。如果图表是加权的 - Dijkstra 会做。

使用BFS寻找最短路径:

给定无向无权图G,节点uv之间的最短路径可以查到如下:

// --- BFS(u, v)-----------------------------
      for each vertex w
      do  flag[w] := false;
          pred[w]  := -1  ;  // predecessor of w
      Q := empty queue;
      flag[u] := true;       // already visited
      enqueue(Q, u)
      while Q not empty
      do    w:= dequeue(Q);
            for each x adjacent to w
                     if flag[x] = false
                        flag[x] := true;
                        pred[x] := w   ;
                        if x = v
                           empty Q;
                           break;
                        else
                           enqueue(Q, x);

// --- ReportShortestPath(u, v)---------------
// backward path - v to u:
      current := v;
      do    output current;
            current := pred[currrent];
      while current != -1