Извлечение родительских узлов из объекта узла - PullRequest
Новая
       1

Извлечение родительских узлов из объекта узла

0 голосов
/ 26 мая 2020

Я пытаюсь создать простой решатель лабиринта, используя поиск по глубине в ruby, алгоритм работает нормально и находит решение, то, с чем я борюсь, - это печать решения, более конкретно доступ к родительским узлам из родительского атрибут объекта.

Вывод, который я получаю для пути: 

S  

  G
state: #<MazeLocation:0x000055999847fe50>, parent: [#<Node:0x000055999847ff68 @state=#<MazeLocation:0x0000559998490138 @row=1, @column=2>, @parent=[#<Node:0x00005599984902a0 @state=#<MazeLocation:0x00005599984904a8 @row=0, @column=2>, @parent=[#<Node:0x0000559998490610 @state=#<MazeLocation:0x0000559998490778 @row=0, @column=1>, @parent=[#<Node:0x0000559998490980 @state=#<MazeLocation:0x0000559998493ef0 @row=0, @column=0>, @parent=[]>]>]>]>]
Solution found

Я пытаюсь извлечь каждый MazeLocation в родительском элементе для отслеживания пути решения.

Код для воспроизведения выглядит следующим образом (извините, долго): классы, связанные с лабиринтом 

require_relative 'search.rb'

module Cells
  EMPTY = :" "
  BLOCKED = :X
  START = :S
  GOAL = :G
  PATH = :*
end

class MazeLocation
  attr_reader :row
  attr_reader :column
  def initialize(row, column)
    @row = row
    @column = column
  end

  def ==(x)
    @row == x.row && @column == x.column
  end

  def eql?(x)
    @row == x.row && @column == x.column
  end

  # needed for set include? method
  def hash
    @row.hash
  end

end

class Maze
  attr_reader :start
  def initialize(start, goal, rows = 10, columns = 10, sparseness = 0.1)
    @rows = rows
    @columns = columns
    @start = start
    @goal = goal
    @grid = []

    @rows.times do |row|
      @grid << Array.new(@columns)
    end

    random_fill(sparseness)

    @grid[start.row][start.column] = Cells::START
    @grid[goal.row][goal.column] = Cells::GOAL
  end

  def to_s
    output = ""
    @grid.each do |row|
      output += "" + row.join + "\n"
    end
    output
  end

  def mark(path)
    path.each do |maze_location|
      @grid[maze_location.row][maze_location.column] = Cells::PATH
    end
    @grid[@start.row][@start.column] = Cells::START
    @grid[@goal.row][@goal.column] = Cells::GOAL
  end

  def goal_test(current_location)
    current_location == @goal
  end

  def successors(current_location)
    possible_moves = []
    if current_location.row + 1 < @rows &&
      @grid[current_location.row + 1][current_location.column] != Cells::BLOCKED
      possible_moves << MazeLocation.new(current_location.row + 1, current_location.column)
    end
    if current_location.row - 1 >= 0 &&
      @grid[current_location.row - 1][current_location.column] != Cells::BLOCKED
      possible_moves << MazeLocation.new(current_location.row - 1, current_location.column)
    end
    if current_location.column + 1 < @columns &&
      @grid[current_location.row][current_location.column + 1] != Cells::BLOCKED
      possible_moves << MazeLocation.new(current_location.row, current_location.column + 1)
    end
    if current_location.column - 1 >= 0 &&
      @grid[current_location.row][current_location.column - 1] != Cells::BLOCKED
      possible_moves << MazeLocation.new(current_location.row, current_location.column - 1)
    end
    possible_moves
  end

  private

  def random_fill(sparseness)
    @grid.each_with_index do |column, row|
      column.each_with_index do |cell, element|
        if rand() < sparseness
          @grid[row][element] = cell = Cells::BLOCKED
        else
          @grid[row][element] = cell = Cells::EMPTY
        end
      end
    end
  end
end

start = MazeLocation.new(0,0)
goal = MazeLocation.new(2,2)

maze = Maze.new(start, goal,3,3)
puts maze

solution = DSF.new(maze, start)
unless solution.solution_found
  puts "No solution found using depth-first search!"
else
  puts "Solution found"
  maze.mark(solution.solution_path)
  puts maze
end

классы, связанные с поиском: 

require 'set'

class Node
    attr_reader :state
    attr_reader :parent
    attr_reader :cost
    attr_reader :heuristic
    def initialize(state, *parent)
        @state = state
        @parent = parent
    end

    def to_s
        "state: #{@state}, parent: #{@parent}"
    end
end

class DSF
    attr_reader :solution_found
    attr_reader :solution_path
    def initialize(maze, inital)
        # the object being searched
        @maze = maze
        # frontier to where we've yet to go
        @frontier = []
        @frontier.push(Node.new(inital))
        @solution_found = false
        @solution_path = []
        # explored is where we have been
        @explored = Set.new
        search
    end

    def node_to_path(node)
        puts node
        path = []
        path << node.state
        path << node.parent
        while node.parent.empty?
            node = node.parent
            path.append(node.state)
        end
        path.reverse
    end

    private

    def search
        while not @frontier.empty?
            current_node = @frontier.pop
            current_state = current_node.state
            #goal check
            if @maze.goal_test(current_state)
                @solution_found = true
                @solution_path = node_to_path(current_node)
            end
            @maze.successors(current_state).each do |child|
                if @explored.include?(child) 
                    next
                end
                @explored << child
                @frontier.push(Node.new(child, current_node))
            end
        end
    end
end

Функция интересов будет следующей:

DFS # node_to_path 

    def node_to_path(node)
        puts node
        path = []
        path << node.state
        path << node.parent
        while node.parent.empty?
            node = node.parent
            path.append(node.state)
        end
        path.reverse
    end

Я действительно думал о передаче родительского узла как object_id, но это казалось неправильным.

1 Ответ

0 голосов
/ 27 мая 2020

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

Я сделал следующие правки:

К классу Node: 

class Node
    attr_reader :state
    attr_reader :parent
    def initialize(state, parent = nil)
        @state = state
        @parent = parent
    end

    def to_s
        "state: #{@state}, parent: #{@parent}"
    end
end

К DFS # node_to_path 

    def node_to_path(node)
        path = []
        path << node.state
        while not node.parent.nil?
            node = node.parent
            path.append(node.state)
        end
        path.reverse
    end

Теперь это работает и дает простой алгоритм решения лабиринта с поиском в глубину.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...