Meu primeiro programa em Ruby

Este blog deixou de ser mantido, mas o autor continua escrevendo aqui. Não deixe de assinar o novo feed!

Antes de pegar esse troço de RoR pra aprender, eu decidi começar a estudar o ‘core’ da linguagem. Pois bem! Nada melhor do que implementar um algoritmo besta para iniciar o aprendizado de uma linguagem de programação.

O algoritmo besta que escolhi para isso é uma adaptação sub-desenvolvida da resolução do PCV. Nada de sofisticado: apenas vai pegando os nós vizinhos, escolhe o de menor custo e bola pre frente. :D

Bom.. o código não está tão ‘bonito’ quanto eu gostaria que estivesse.. mas não está tão ruim assim. :P Bom…. aí vai o código!

  1.  
  2. #!/usr/bin/ruby
  3.  
  4. # ——–
  5. # Classe para a resolução do Problema do Caixeiro Viajante,
  6. # seguindo o algoritmo de construção por vizinho mais próximo.
  7. #
  8. # Autor: Daniel Fernandes Martins
  9. # ——–
  10. class Pcv
  11.  
  12.    # Métodos Get
  13.    attr_reader :n , :h , :l , :matrix
  14.  
  15.    # Método Set e Get
  16.    attr_accessor :i
  17.  
  18.    # Inicializa o objeto
  19.    def initialize()
  20.       @h = Array.new
  21.       @l = @i = 0
  22.    end
  23.  
  24.    # Seta o grafo a ser utilizado no algoritmo
  25.    def matrix=(value)
  26.       if value.is_a? Array
  27.          @matrix = value
  28.          @n = (1 .. value.length).each {|e|}.collect
  29.       end
  30.    end
  31.  
  32.    # Implementação do algoritmo
  33.    def process
  34.       @n.delete @i
  35.       @h << @i
  36.  
  37.       # Enquanto ainda existirem elementos a serem verificados…
  38.       while @n.any?
  39.  
  40.          minor = nil
  41.          j = nil
  42.  
  43.          # Encontra o menor elemento em N
  44.          @n.each do |v|
  45.             if (minor == nil || @matrix[@i-1][v-1] < minor)
  46.                   && @matrix[@i-1][v-1] != 0
  47.                minor = @matrix[@i-1][v-1]
  48.                j = v
  49.             end
  50.          end
  51.  
  52.          # J é o vizinho mais próximo
  53.  
  54.          # Adiciona J ao caminho e ajusta o custo do caminho atual
  55.          @h << j
  56.          @l += minor
  57.          @i = j
  58.  
  59.          # Remove J do vetor de elementos disponíveis
  60.          @n.delete j
  61.       end
  62.  
  63.       # Fecha o ciclo
  64.       @l += @matrix[@i-1][ @h[0]-1 ]
  65.    end
  66. end
  67.  
  68. # ——–
  69. # Métodos utilitários
  70. # ——–
  71. def print_header
  72.    puts “”
  73.    puts “Problema do Caixeiro Viajante”
  74.    puts “”
  75. end
  76.  
  77. def print_array (array)
  78.    array.each { |v| print “#{v} “}
  79.    puts “”
  80. end
  81.  
  82. def print_matrix (matrix)
  83.    matrix.each { |i| print_array i }
  84. end
  85.  
  86. def print_result (pcv)
  87.    print “Caminho.: “
  88.    print_array pcv.h
  89.  
  90.    puts “Custo…: #{pcv.l}“
  91.    puts “”
  92. end
  93.  
  94. def read_initial_node (pcv)
  95.    begin
  96.       print “Digite o no inicial (1-5): “
  97.       pcv.i = gets.to_i
  98.    end while pcv.i < 1 || pcv.i > 5
  99. end
  100.  
  101. # ——–
  102. # Loop principal
  103. # ——–
  104. begin
  105.  
  106.    # Criação de um objeto para resolução do problema
  107.    pcv = Pcv.new();
  108.  
  109.    print_header
  110.  
  111.    puts “Matriz de teste”
  112.    puts “***************”
  113.    puts “”
  114.  
  115.    # Grafo a ser calculado
  116.    matrix = Array.new
  117.    matrix << [0, 1, 2, 7, 5]
  118.    matrix << [1, 0, 3, 4, 3]
  119.    matrix << [2, 3, 0, 5, 2]
  120.    matrix << [7, 4, 5, 0, 3]
  121.    matrix << [5, 3, 2, 3, 0]
  122.    pcv.matrix = matrix
  123.  
  124.    # Mostra a matrix na tela
  125.    print_matrix pcv.matrix
  126.    puts “”
  127.  
  128.    # Usuário indica o primeiro nó
  129.    read_initial_node (pcv)
  130.  
  131.    # Calcula e mostra o resultado
  132.    pcv.process
  133.  
  134.    puts “”
  135.    puts “Resultado”
  136.    puts “*********”
  137.  
  138.    print_result (pcv)
  139.    print “Calcular novamente (S/N)? “
  140. end while gets.chomp.upcase == “S”
  141.  

*PS: Os nomes das variáveis (i, j, l, etc) estão assim pois eu segui um documento que explicava o algoritmo utilizando tipo uma linguagem matemática. É, tá zuado, mas tá bão! :D

Tags: , , ,
18 de abril de 2006 | programação