Нужна помощь в создании функции поиска в ширину - PullRequest
Новая
       0

Нужна помощь в создании функции поиска в ширину

0 голосов
/ 24 января 2020

В настоящее время я работаю над проектом Knight's Travails. В этом проекте вам нужно найти кратчайший путь от А до Б для шахматного рыцаря.

Я не знаю, почему моя программа падает, когда дело доходит до функции поиска в ширину. Я не могу поймать его с помощью отладчика, потому что VScode зависает при чтении переменной «root» внутри knight_moves.

Не могли бы вы помочь мне найти ошибку?

Я создал доску. Он имеет ссылки на каждую ячейку доски в соответствии с положением ячейки. Я создал ссылки между ячейками с помощью функции 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 [: priorcessor] = node" вылетает программа. И если я использую @variable для хранения «предшественника» вместо ha sh, программа запускается. Хотя я не знаю почему. В чем причина?

1 Ответ

0 голосов
/ 25 января 2020

Что касается меня, то основная проблема с кодом заключается в его ненужной («случайной») сложности.

Да, решаемая вами задача может быть сведена к задаче обхода графа, но это не значит, что вы должны представлять граф явно . Для этой конкретной задачи - где все возможные перемещения из произвольной ячейки четко определены, а сама доска ограничена - вы можете легко вычислить края графа на лету (и без всего этого дополнительного механизма, который делает ваш код настолько трудным для рассуждения о - даже для вас). Явное представление платы также выглядит избыточным (опять же, для этой конкретной задачи).

Принимая все это во внимание, решение может быть таким простым: 

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