5521
Comentário: Resolvedor de Labirintos
|
9413
Algoritmo A* para solucionar labirintos, busca de menor caminho, etc.
|
Deleções são marcadas assim. | Adições são marcadas assim. |
Linha 1: | Linha 1: |
## page was renamed from Labirinto | |
Linha 168: | Linha 169: |
=== Resolvendo com A* === Contribuição de João Paulo Farias: {{{ #!python #!/usr/bin/python # -*- coding: iso-8859-1 -*- """ Implementação do algoritmo AStar utilizando uma Priority Queue. Foi escrito para a solução de labirintos, encontrando o menor caminho para sair de E e chegar a S. O labirinto é composto por: # significando que não pode andar nesta posição . significando que pode andar nesta posição E ponto de início (Entrada) S ponto de destino (Saída) """ import Queue, bisect class PriorityQueue(Queue.Queue): def _put(self, item): bisect.insort(self.queue, item) def AStar(mapa): """ Algoritmo AStar. mapa deve ser um vetor de strings ou uma matriz de caracteres de tamanho NxM. """ # listas do algoritmo AStar aberta = PriorityQueue(0) fechada = [] # PriorityQueue(0) n = len(mapa) #linhas m = len(mapa[0]) #colunas # procurar pela entrada e saída entrada = None saida = None for i, linha in enumerate(mapa): for j, char in enumerate(linha): if char == 'E': entrada = [i, j] elif char == 'S': saida = [i, j] # ajuda a calcular a distância def dist(orig, dest): return abs(orig[0] - dest[0]) + abs(orig[1] - dest[1]) # retorna os vizinhos de um nó no mapa, caso possa caminhar por eles def vizinhos(no): pos = no.pos res = [] if pos[0] > 0 and mapa[pos[0]-1][pos[1]] in ('.','S'): # tenta ir para cima novo = No([pos[0]-1, pos[1]], no, no.g+1, dist([pos[0]-1,pos[1]], saida)) res.append(novo) if pos[0] < n-1 and mapa[pos[0]+1][pos[1]] in ('.','S'): # tenta ir para baixo novo = No([pos[0]+1, pos[1]], no, no.g+1, dist([pos[0]+1,pos[1]], saida)) res.append(novo) if pos[1] > 0 and mapa[pos[0]][pos[1]-1] in ('.','S'): # tenta ir para esquerda novo = No([pos[0], pos[1]-1], no, no.g+1, dist([pos[0],pos[1]-1], saida)) res.append(novo) if pos[1] < m-1 and mapa[pos[0]][pos[1]+1] in ('.','S'): # tenta ir para direita novo = No([pos[0], pos[1]+1], no, no.g+1, dist([pos[0],pos[1]+1], saida)) res.append(novo) return res # representação de cada nó do AStar class No(object): def __init__(self, pos=None, pai=None, g=0, h=0): self.pos = pos self.pai = pai self.g = g self.h = h def __eq__(self, other): return self.pos == other.pos def __ne__(self, other): return self.pos != other.pos def __le__(self, other): return self.g+self.h <= other.g+other.h def __ge__(self, other): return self.g+self.h >= other.g+other.h def __str__(self): return 'pos = %s, g = %d, h = %d' % (self.pos, self.g, self.h) at = No() at.h = dist(entrada, saida) at.pos = entrada[:] at.pai = None aberta.put(at, False) mapa1 = [list(l) for l in mapa] achou = False while not aberta.empty(): at = aberta.get(False) fechada.append(at) if at.pos == saida: # achou achou = True break viz = vizinhos(at) for no in viz: if not no in fechada: if not no in aberta.queue: aberta.put(no) # reconstrução do caminho if achou: caminho = [at.pos] while True: at = at.pai if at is None: break caminho.insert(0, at.pos) print caminho else: print 'Caminho não encontrado' AStar([ '##########', '#E..#...S#', '#..#.#..##', '#.......##', '##########']) AStar([ '############## ####################', '#E.#.S#..#...###.....#.#..........#', '#..#.............###.#............#', '##...##...######## #...#..........#', '############## ################']) }}} João Paulo Farias ------------- |
Este código utiliza recursão para resolver um labirinto.
O mapa deve ser dado em formato texto, vide exemplo no fim do código.
A versão mais atual encontra-se em: http://gsbarbieri.sytes.net/labirinto.py
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3 # -*- mode: python -*-
4
5
6 # Configuração de caracteres do mapa
7 parede = '#'
8 corredor = '.'
9 percorrido = '='
10 errado = 'x'
11 solucao = '@'
12 entrada = 'E'
13 saida = 'S'
14
15
16 class Labirinto( object ):
17 def __init__( self ):
18 self.mapa = None
19 self.entrada = None
20 self.saida = None
21 # __init__()
22
23
24 def le_mapa( self, texto ):
25 """Lê um mapa, este deve ter uma entrada e uma saída."""
26 self.mapa = texto.split( '\n' )
27
28 for i, l in enumerate( self.mapa ):
29 # encontra entrada:
30 p = l.find( entrada )
31 if p >= 0:
32 self.entrada = ( i, p )
33 # encontra saida:
34 p = l.find( saida )
35 if p >= 0:
36 self.saida = ( i, p )
37
38 # converte string para lista
39 self.mapa[ i ] = list( l )
40
41 if not self.entrada:
42 raise ValueError( "O mapa não possui uma entrada!" )
43 if not self.saida:
44 raise ValueError( "O mapa não possui uma saída!" )
45 # le_mapa()
46
47
48 def le_mapa_arquivo( self, arquivo ):
49 """Lê um mapa de um arquivo"""
50 f = open( arquivo )
51 self.le_mapa( f.read() )
52 f.close()
53 # le_mapa_arquivo()
54
55
56
57 def __str__( self ):
58 m = []
59 for l in self.mapa:
60 m.append( ''.join( l ) )
61 return '\n'.join( m )
62 # __str__()
63
64
65 def resolve( self ):
66 """Resolve o labirinto, tenta encontrar a saída.
67
68 Se a saída foi encontrada, retorna True, caso contrário False.
69 """
70 def posicao_valida( linha, coluna ):
71 "Função utilizada para conferir se a posição está dentro do mapa"
72 if linha > len( self.mapa ) or \
73 coluna > len( self.mapa[ linha ] ):
74 "Posição inválida, sai fora do mapa"
75 return False
76 else:
77 return True
78 # posicao_valida()
79
80
81 def encontra_saida( linha, coluna ):
82 """Função recursiva para encontrar a saída."""
83
84 if self.mapa[ linha ][ coluna ] == saida:
85 "Caso base da recursão, estamos em cima da saída"
86 return True
87 else:
88 """Marque como percorrido e entre em recursão
89
90 No caso iremos pela direita, depois para cima, para esquerda e
91 então para baixo.
92
93 Lembrando que isto é uma recursão e que marcamos nosso caminho,
94 temos magicamente a lembrança dos caminhos já testados.
95 """
96 self.mapa[ linha ][ coluna ] = percorrido
97 achou = False
98
99 if not achou and \
100 posicao_valida( linha, coluna + 1 ) and \
101 self.mapa[ linha ][ coluna + 1 ] in ( corredor, saida ):
102 """Ainda não encontrou e
103 a posição à direita é corredor ou é a saída.
104 Prossiga pela direita."""
105 achou = encontra_saida( linha, coluna + 1 )
106
107 if not achou and \
108 posicao_valida( linha - 1, coluna ) and \
109 self.mapa[ linha - 1 ][ coluna ] in ( corredor, saida ):
110 """Ainda não encontrou e
111 a posição acima é corredor ou é a saída.
112 Prossiga para cima."""
113 achou = encontra_saida( linha - 1, coluna )
114
115 if not achou and \
116 posicao_valida( linha, coluna - 1 ) and \
117 self.mapa[ linha ][ coluna - 1 ] in ( corredor, saida ):
118 """Ainda não encontrou e
119 a posição à esquerda é corredor ou é a saída.
120 Prossiga para esquerda."""
121 achou = encontra_saida( linha, coluna - 1 )
122
123 if not achou and \
124 posicao_valida( linha + 1, coluna ) and \
125 self.mapa[ linha + 1 ][ coluna ] in ( corredor, saida ):
126 """Ainda não encontrou e
127 a posição abaixo é corredor ou é a saída.
128 Prossiga para baixo."""
129 achou = encontra_saida( linha + 1, coluna )
130
131 # Caso o caminho adotado foi correto, marque como solução
132 # senão marque como errado
133 if achou:
134 self.mapa[ linha ][ coluna ] = solucao
135 else:
136 self.mapa[ linha ][ coluna ] = errado
137
138 return achou
139 # encontra_saida()
140
141 return encontra_saida( self.entrada[ 0 ], self.entrada[ 1 ] )
142 # resolve()
143 # Labirinto
144
145
146 # Exemplo de uso:
147 l = Labirinto()
148 l.le_mapa(
149 """
150 ############## ####################
151 #E.#.S#..#...###.....#.#..........#
152 #..#.............###.#............#
153 ##...##...######## #...#..........#
154 ############## ################
155 """ )
156 print l
157 print "achou?",l.resolve()
158 print l
Resolvendo com A*
Contribuição de João Paulo Farias:
1 #!/usr/bin/python
2 # -*- coding: iso-8859-1 -*-
3
4 """ Implementação do algoritmo AStar utilizando uma Priority Queue.
5
6 Foi escrito para a solução de labirintos, encontrando o menor caminho
7 para sair de E e chegar a S. O labirinto é composto por:
8 # significando que não pode andar nesta posição
9 . significando que pode andar nesta posição
10 E ponto de início (Entrada)
11 S ponto de destino (Saída)
12
13 """
14
15 import Queue, bisect
16
17 class PriorityQueue(Queue.Queue):
18 def _put(self, item):
19 bisect.insort(self.queue, item)
20
21
22 def AStar(mapa):
23 """ Algoritmo AStar.
24
25 mapa deve ser um vetor de strings ou uma matriz de caracteres de
26 tamanho NxM.
27 """
28 # listas do algoritmo AStar
29 aberta = PriorityQueue(0)
30 fechada = [] # PriorityQueue(0)
31
32 n = len(mapa) #linhas
33 m = len(mapa[0]) #colunas
34
35 # procurar pela entrada e saída
36 entrada = None
37 saida = None
38 for i, linha in enumerate(mapa):
39 for j, char in enumerate(linha):
40 if char == 'E':
41 entrada = [i, j]
42 elif char == 'S':
43 saida = [i, j]
44
45 # ajuda a calcular a distância
46 def dist(orig, dest):
47 return abs(orig[0] - dest[0]) + abs(orig[1] - dest[1])
48
49 # retorna os vizinhos de um nó no mapa, caso possa caminhar por eles
50 def vizinhos(no):
51 pos = no.pos
52 res = []
53 if pos[0] > 0 and mapa[pos[0]-1][pos[1]] in ('.','S'): # tenta ir para cima
54 novo = No([pos[0]-1, pos[1]], no, no.g+1, dist([pos[0]-1,pos[1]], saida))
55 res.append(novo)
56 if pos[0] < n-1 and mapa[pos[0]+1][pos[1]] in ('.','S'): # tenta ir para baixo
57 novo = No([pos[0]+1, pos[1]], no, no.g+1, dist([pos[0]+1,pos[1]], saida))
58 res.append(novo)
59 if pos[1] > 0 and mapa[pos[0]][pos[1]-1] in ('.','S'): # tenta ir para esquerda
60 novo = No([pos[0], pos[1]-1], no, no.g+1, dist([pos[0],pos[1]-1], saida))
61 res.append(novo)
62 if pos[1] < m-1 and mapa[pos[0]][pos[1]+1] in ('.','S'): # tenta ir para direita
63 novo = No([pos[0], pos[1]+1], no, no.g+1, dist([pos[0],pos[1]+1], saida))
64 res.append(novo)
65 return res
66
67 # representação de cada nó do AStar
68 class No(object):
69 def __init__(self, pos=None, pai=None, g=0, h=0):
70 self.pos = pos
71 self.pai = pai
72 self.g = g
73 self.h = h
74
75 def __eq__(self, other):
76 return self.pos == other.pos
77
78 def __ne__(self, other):
79 return self.pos != other.pos
80
81 def __le__(self, other):
82 return self.g+self.h <= other.g+other.h
83
84 def __ge__(self, other):
85 return self.g+self.h >= other.g+other.h
86
87 def __str__(self):
88 return 'pos = %s, g = %d, h = %d' % (self.pos, self.g, self.h)
89
90 at = No()
91 at.h = dist(entrada, saida)
92 at.pos = entrada[:]
93 at.pai = None
94 aberta.put(at, False)
95 mapa1 = [list(l) for l in mapa]
96 achou = False
97 while not aberta.empty():
98 at = aberta.get(False)
99 fechada.append(at)
100 if at.pos == saida: # achou
101 achou = True
102 break
103 viz = vizinhos(at)
104 for no in viz:
105 if not no in fechada:
106 if not no in aberta.queue:
107 aberta.put(no)
108
109 # reconstrução do caminho
110 if achou:
111 caminho = [at.pos]
112 while True:
113 at = at.pai
114 if at is None:
115 break
116 caminho.insert(0, at.pos)
117 print caminho
118 else:
119 print 'Caminho não encontrado'
120
121 AStar([
122 '##########',
123 '#E..#...S#',
124 '#..#.#..##',
125 '#.......##',
126 '##########'])
127
128 AStar([
129 '############## ####################',
130 '#E.#.S#..#...###.....#.#..........#',
131 '#..#.............###.#............#',
132 '##...##...######## #...#..........#',
133 '############## ################'])
João Paulo Farias
Por GustavoBarbieri.