用n球解决迷宫的通用算法

1 回答

• 9

  我会建议以下算法：

  • 为迷宫创建数据结构，对于每个空闲单元格（正方形），已知以下内容：

  一个 . 坐标（行，列）
  湾4个移动的目标细胞（北，东，南，西）
  C . b的反面：大理石可以来到这个细胞的细胞（如果有的话） .

  • 从目标单元格开始执行BFS，使用一个假想的大理石执行反向移动，分配给每个访问的单元格，从该单元格到达目标单元格所需的最少移动次数 . 请注意，某些单元格可能不会以这种方式访问，这意味着如果将大理石放置在那里，则无法通过执行合法移动将其移至目标单元格 . 这些细胞将获得归因于它们的无限距离（初始值） .

  • 创建一个评估函数，该函数将为特定的大理石配置分配成本 . 建议的评估函数将总结由至少一个大理石占据的每个单元的距离的平方 . 通过取正方形，较高的距离将带来相对较高的成本，因此该算法将有利于改善具有最差位置的大理石位置的移动 . 此功能不会计算由多个大理石占据的单元格的两倍 . 这样，大理石共享细胞的配置受到青睐 .

  • 从起始位置，以评估成本生成4个可能的移动 . 按成本递增排序，按顺序执行DFS，递归重复此步骤 . 当成本变为零时，找到解决方案，并且在立即回溯递归期间，返回移动的“路径” . 当成本为无限时，则停止搜索，尝试下一步，等等 .

  • 在搜索过程中，保留一份访问过的位置列表 . 当再次访问某个位置时，评估函数会给它一个无穷大的值，以便在发生这种情况时搜索将回溯 .

  以下是上述算法的JavaScript实现：

  "use strict";
  function createMaze(mazeStr) {
      var maze, lines, cell, row, ch, id, r, c, n, m;
      
      maze = {
          nodesRowCol: [],
          nodes: [],
          target: null,
          marbles: []
      };
      id = 0;
      lines = mazeStr.split("\n");
      for (r = 0; r < lines.length; r++) {
          maze.nodesRowCol[r] = row = [];
          for (c = 0; c < lines[r].length; c++) {
              ch = lines[r].charAt(c);
              if (ch !== '#') {
                  maze.nodes[id] = row[c] = cell = {
                      row: r,
                      col: c,
                      id: id++,
                      comeFrom: [],
                  };
                  // Keep track of target and marbles
                  if (ch === '*') maze.target = cell;
                  if (ch === '.') maze.marbles.push(cell);
              }
          }
      }
      // Add neighbours
      for (n = 0; n < maze.nodes.length; n++) {
          cell = maze.nodes[n];
          cell.neighbours = [
              maze.nodesRowCol[cell.row-1][cell.col], /* north */
              maze.nodesRowCol[cell.row][cell.col+1], /* east  */
              maze.nodesRowCol[cell.row+1][cell.col], /* south */
              maze.nodesRowCol[cell.row][cell.col-1]  /* west  */
          ];
      }
      // Add marble moves in two steps
      for (n = 0; n < maze.nodes.length; n++) {
          cell = maze.nodes[n];
          cell.moves = [ 
              cell.neighbours[0] ? cell.neighbours[0].moves[0] : cell, /* north */
              null,
              null,
              cell.neighbours[3] ? cell.neighbours[3].moves[3] : cell, /* west  */
          ];
      }
      for (n = maze.nodes.length - 1; n >= 0; n--) {
          cell = maze.nodes[n];
          cell.moves[1] = cell.neighbours[1] ? cell.neighbours[1].moves[1] : cell; /* west */
          cell.moves[2] = cell.neighbours[2] ? cell.neighbours[2].moves[2] : cell; /* south */
      }
      // add reverse-move ("marble can come from") data
      for (n = maze.nodes.length - 1; n >= 0; n--) {
          cell = maze.nodes[n];
          for (m = 0; m < 4; m++) {
              if (cell.moves[m] !== cell) cell.moves[m].comeFrom.push(cell);
          }
      }
      return maze;
  }
  
  function setDistances(maze) {
      var n, cell, distance, stack, newStack, i;
      // clear distance information
      for (n = 0; n < maze.nodes.length; n++) {
          maze.nodes[n].distance = Number.POSITIVE_INFINITY;
      }
      // set initial distance
      cell = maze.target;
      cell.distance = distance = 0;
      // BSF loop to set the distance for each cell that can be reached
      stack = cell.comeFrom.slice();
      while (stack.length) {
          distance++;
          newStack = [];
          for (i = 0; i < stack.length; i++) {
              cell = stack[i];
              if (distance < cell.distance) {
                  cell.distance = distance;
                  newStack = newStack.concat(cell.comeFrom);
              }
          }
          stack = newStack;
      }
  }
  
  function evaluatedPosition(position, visited) {
      // Assign heurstic cost to position
      var m, ids;
      
      position.cost = 0;
      ids = []; // keep track of marble positions
      for (m = 0; m < position.marbles.length; m++) {
          // If mulitple marbles are at same cell, only account for that cell once.
          // This will favour such positions: 
          if (ids[position.marbles[m].id] === undefined) { 
             // Make higher distances cost a lot, so that insentive
             // is to improve the position of the worst placed marble 
             position.cost += Math.pow(position.marbles[m].distance, 2);
             ids[position.marbles[m].id] = position.marbles[m].id;
          }
      }
      // Assign some unique string, identifying the marble configuration
      position.id = ids.join(','); 
      // If position was already visited before, give it the maximum cost
      if (visited[position.id]) position.cost = Number.POSITIVE_INFINITY;
      // Mark position as visited
      visited[position.id] = 1;
      return position;
  }
  
  function createMove(dir, marbles, visited) {
      var m, movedMarbles;
      
      movedMarbles = [];
      for (m = 0; m < marbles.length; m++) {
          movedMarbles[m] = marbles[m].moves[dir];
      }
      return evaluatedPosition({
          dir: dir,
          marbles: movedMarbles,
      }, visited);
  }
  
  function solve(maze) {
      var visited = {}; // nothing visited yet
      
      function recurse (position) {
          var ids, m, moves, i, path;
          if (position.cost == 0) return []; // marbles are all on target spot.
          if (!isFinite(position.cost)) return false; // no solution
          // get move list
          moves = [];
          for (i = 0; i < 4; i++) {
              moves[i] = createMove(i, position.marbles, visited);
          }
          // apply heuristic: sort the 4 moves by ascending cost
          moves.sort(function (a,b) { return a.cost - b.cost });
          for (i = 0; i < 4; i++) {
              //console.log('=== move === ' +  moves[i].dir);
              path = recurse(moves[i]);
              if (path !== false) return [moves[i].dir].concat(path);
          }
          return false; // no solution found
      }
      // Enrich initial position with cost, and start recursive search 
      return recurse(evaluatedPosition({
          marbles: maze.marbles
      }, visited));
  }
  
  
  // # = wall
  // * = target
  // . = marble
  
  var mazeStr = `
  ###########
  #   #   #*#
  # # #.#  .#
  # #.  #.# #
  # # # ### #
  #   #     #
  ###########
  `.trim();
  
  var maze = createMaze(mazeStr);
  setDistances(maze);
  console.log('#=wall, .=marble, *=target\n\n' + mazeStr);
  
  var moves = solve(maze);
  console.log('moves (0=north,1=east,2=south,3=west): ' + moves);
  

  找到的解决方案不一定是最佳的 . 它执行深度为1的评估 . 为了获得更好的解决方案，该算法可以在更深的位置进行评估 .

  回复于 2024-05-02T22:56:49+08:00