Renan Fernandes Linux, Technology, Programming and Free Software.

Problema do caixeiro viajante

De acordo com a wikipédia:

O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial

Resolvi esse problema rapidamente com ruby. Pode não ser o código mais belo mas ao menos funciona :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

City = Struct.new(:x, :y, :name)
Route = Struct.new(:cities, :distance)
 
CITIES = []
 
def add_city(x, y, name)
  CITIES << City.new(x, y, name)
end
 
def calculate_distance(from, to)
  Math.sqrt((to.x-from.x)**2 + (to.y-from.y)**2).to_i
end
 
def go_route(route, routes)
  if route.cities.length == CITIES.length
    route.distance += calculate_distance(route.cities[-1], route.cities[0])
    route.cities << route.cities[0]
    routes << route
    return
  end
 
  for city in CITIES - route.cities
    new_route = Route.new(route.cities + [city], route.distance + calculate_distance(route.cities.last, city))
    go_route(new_route, routes)
  end
end
 
def go(routes, start_city)
  route = Route.new([start_city], 0)
  go_route(route, routes)
  routes
end
 
def r(n=10000)
  (rand*n).to_i
end
 
for name in ["Foo", "Bar", "LOL", "WIN!", "Ruby", "Perl", "LOL!!!"]
  add_city(r, r, name)
end
 
 
best_routes = go([], CITIES.shuffle[0]).sort_by(&:distance)[0...10]
 
puts "10 Best routes!"
best_routes.each_with_index do |route, i|
  puts "\n"*2
  puts "Route ##{i+1}"
  puts " Distance: #{route.distance}"
  puts " Cities:"
 
  last_city = nil
  distance  = 0
  puts "  %10s | %07s, %7s | %10s | %s" % [ "City", "Cord X", "Cord Y", "Total dist", "Distance from last city"]
  route.cities.each do |city|
    distance_between_cities = (last_city.nil? ? 0 : calculate_distance(last_city, city))
    puts "  %10s | x:%.05i, y:%.05i | %.10i | %.10i" % [city.name, city.x, city.y, distance+=distance_between_cities, distance_between_cities]
    last_city = city
  end
 
end

Certo, vamos começar as explicações:

• Nas linhas 38, 39 e 40 nós criamos algumas cidades com posições aleatórias.
• Na linha 43 nós chamamos o método "go" passando uma Array e uma cidade aleatória. Após ele terminar de executar os resultados vão ser ordenados pela distância da rota e será pego apenas os 10 menores.
• No método go(linha 28) nós criamos uma nova rota(linha 29) tendo a cidade aleatória(ponto de partida) e a distância de 0. Então passamos essa nova rota e a array de rotas pro método go_route(linha 30)
• No método go_route(linha 14) verificamos se a rota já tem todas as cidades(linha 15).
• Caso tenha, então adicionamos a cidade inicial(linha 17) e a distância da última cidade até ela(linha 16), então adicionamos essa rota a array de rotas(linha 18).
• Caso não tenha, então iniciamos um 'for' com as cidades restantes(linha 22). Para cada cidade é criada uma nova rota com todas as cidades que já passou + a cidade atual do for e calculado a distância até ela(linha 23). Com essa nova rota chamamos o método go_route novamente, só que dessa vez com a nova rota(linha 24).

Pra quem não entender o que está acontecendo na linha 11, é só lembrar daquela frase do Teorema de Pitágoras:

Em um triângulo retângulo, o quadrado da medida da hipotenusa é igual à soma dos quadrados das medidas dos catetos.

Ou seja, o x do ponto final menos o x do ponto inicial elevado ao quadrado mais o y do ponto final menos o y do ponto inicial elevado ao quadrado é igual ao quadrado da distância entre os 2 pontos, então é só tirar a raiz quadrado do resultado.

More From Renan Fernandes

• Resolvendo (parcialmente) o problema de threads no QtRuby4
• Stickvania: Clone do Castlevania
• Tirando o lixo do sistema

Renan Fernandes Recommends

• The Twelve Days of Christmas begins on December 25 until January 5th  (verenetta)
• Top 11 Legal Advisors Giving Green Tech a Boost  (U.S. Green Technology)

Ask Renan Fernandes To Recommend Your Posts

Popularity: 10% [?]

Sobre ShadowBelmolve

Arch Linux user and Ruby on Rails Developer :)