मैं वर्तमान में नाइट्स ट्रैवेल्स प्रोजेक्ट कर रहा हूं। इस परियोजना में आपको शतरंज नाइट के लिए ए से बी तक का सबसे छोटा रास्ता खोजने की जरूरत है।

जब चौड़ाई-प्रथम खोज फ़ंक्शन की बात आती है तो मुझे नहीं पता कि मेरा प्रोग्राम क्यों क्रैश हो जाता है। मैं इसे डीबगर के साथ नहीं पकड़ सकता क्योंकि VScode 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 [: पूर्ववर्ती] = नोड" प्रोग्राम को क्रैश करती है। और अगर मैं हैश के बजाय "पूर्ववर्ती" स्टोर करने के लिए @variable का उपयोग करता हूं तो प्रोग्राम चलता है। हालांकि मुझे नहीं पता क्यों। क्या कारण है?

-1
Infectos 24 जिंदा 2020, 23:34

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]]
0
Konstantin Strukov 25 जिंदा 2020, 00:26