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

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 来存储 "predecessor" 而不是散列程序运行。我不知道为什么。什么原因？

Answer 1

对我来说，代码的主要问题是不必要的 ("incidental") 复杂性。

是的，您要解决的任务可以简化为图形遍历问题，但是这并不意味着您必须显式表示图形。对于这个特定的任务——任意单元格的所有可能移动都被明确定义并且棋盘本身是有限的——你可以轻松地动态计算图形边缘（并且没有所有这些使你的代码难以推理的额外机制关于 - 甚至对你来说）。董事会的明确表示看起来也多余（同样，对于这个特定任务）。

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

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]]

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

Need help to create a breadth-first search function

ruby

breadth-first-search