需要帮助来创建广度优先搜索功能

Question

我目前正在执行Knight's Travails项目。在这个项目中，您需要找到国际象棋骑士从A到B的最短路程。

我不知道为什么广度优先搜索功能导致我的程序崩溃。我无法通过调试器捕获它，因为VScode在读取knight_moves中的变量“ root”时冻结了。

您能帮我找到使用方法吗？

我创建了董事会。它根据单元的位置链接到电路板上的每个单元。我已经使用add_edges函数在单元格之间创建了链接。链接是可能的移动方式。

到目前为止，我已经在下面的代码中

class Node
  attr_reader :pos
  attr_accessor :children, :search_info
  def initialize (row, column)
    @pos = [row, column]
    @children = nil
    @search_info = Hash.new
  end
end

class Board
  attr_reader :show
  def initialize
    create_board
  end


  def create_board
    board = []
    8.times do |x|
      board<<[x]
    end
    board.each_with_index do |item, index|
      8.times do |x|
      board[index] << x unless x == index
      end
    end
    board.each do |x|
      x.sort!
    end
    @board = board
  end

  def show
    @board
  end

  def fill_with_nodes
    @board.each_with_index do |item, index|
      item.map! {|column| Node.new(index,column)}
    end
  end

  def add_edges
    @board.each_with_index do |row, index|
      row.each do |node|
        node.children = []

        node.children = node.children << @board[node.pos[0]-2][node.pos[1]-1] if (0..7).include?(node.pos[0]-2) && (0..7).include?(node.pos[1]-1)
        node.children = node.children << @board[node.pos[0]-2][node.pos[1]+1] if (0..7).include?(node.pos[0]-2) && (0..7).include?(node.pos[1]+1)

        node.children = node.children << @board[node.pos[0]+2][node.pos[1]-1] if (0..7).include?(node.pos[0]+2) && (0..7).include?(node.pos[1]-1)
        node.children = node.children << @board[node.pos[0]+2][node.pos[1]+1] if (0..7).include?(node.pos[0]+2) && (0..7).include?(node.pos[1]+1)

        node.children = node.children << @board[node.pos[0]-1][node.pos[1]-2] if (0..7).include?(node.pos[0]-1) && (0..7).include?(node.pos[1]-2)
        node.children = node.children << @board[node.pos[0]+1][node.pos[1]-2] if (0..7).include?(node.pos[0]+1) && (0..7).include?(node.pos[1]-2)

        node.children = node.children << @board[node.pos[0]-1][node.pos[1]+2] if (0..7).include?(node.pos[0]-1) && (0..7).include?(node.pos[1]+2)
        node.children = node.children << @board[node.pos[0]+1][node.pos[1]+2] if (0..7).include?(node.pos[0]+1) && (0..7).include?(node.pos[1]+2)

      end
    end
  end

  def cell (row, column)
    @board[row][column]
  end

  def knight_moves (start, finish)
    raise StandardError.new("Invalid start") unless (0..7).include?(start[0]) || (0..7).include?(start[1])
    raise StandardError.new("Invalid finish") unless (0..7).include?(finish[0]) || (0..7).include?(finish[1])


    queue = []

    root = @board[finish[0]][finish[1]]
    root.search_info[:distanse] = 0
    queue << root
    until queue.empty?
      node = queue.shift
      break if node.pos == [start[0],start[1]]
      node.children.each do |child|
        unless child.search_info[:distanse] 
        child.search_info[:distanse] = node.search_info[:distanse] + 1
        child.search_info[:predecessor] = node
        queue << child
        end
      end
    end
  end

end 


#This part is for testing
puts a = Board.new
puts a.show.to_s
a.fill_with_nodes
puts a.show.to_s
a.add_edges
a.knight_moves([0,0], [0,1])
def show_cell(board,row, column)
  puts ""
  puts board.cell(row,column).pos.to_s, board.cell(row,column).children.map {|child| child.pos}.to_s ,board.cell(row,column).search_info.to_s
end
show_cell(a,2,2)

编辑：我发现“ child.search_info [：predecessor] = node”行使程序崩溃。而且，如果我使用@variable来存储“前任”而不是哈希，则程序将运行。我不知道为什么。什么原因？

Answer 1

对我来说，代码的主要问题是它不必要的（偶然的）复杂性。

是的，您要解决的任务可以简化为图遍历的问题，但是这并不意味着您必须明确表示图]。对于此特定任务-从任意单元格开始的所有可能移动均已定义好，并且电路板本身受到限制-您可以轻松地动态计算图形边缘（并且无需使用所有其他会使机器难以推理的额外机制）关于-甚至是您）。董事会的明确表示也显得多余（再次针对此特定任务）。

考虑到所有这些，解决方案可能很简单：

class Knight
  def initialize
    @knight_moves = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]
  end

  def move(start, stop)
    visited = {}
    queue = [[stop, nil]]

    while queue.any?
      current_cell, next_cell = queue.shift
      next if visited.has_key?(current_cell)

      visited[current_cell] = next_cell

      return build_path(start, stop, visited) if current_cell == start

      possible_moves(current_cell).each do |next_move|
        queue << [next_move, current_cell] unless visited.has_key?(next_move)
      end
    end
  end

  private

  def possible_moves(cell)
    @knight_moves.
      map { |x, y| [cell.first + x, cell.last + y] }.
      select(&method(:valid_move?))
  end

  def build_path(start, stop, visited)
    path = [start]

    while next_cell = visited[path.last]
      path << next_cell
    end

    path.last == stop ? path : nil
  end

  def valid_move?(cell)
    cell.all? { |n| n >= 0 && n <= 7 }
  end
end

knight = Knight.new
knight.move [0,0], [0,1] #=> [[0, 0], [2, 1], [1, 3], [0, 1]]