1. Introdução
A pesquisa pode ser complexa ou simples. Quando não é conhecido (ou apenas parcialmente conhecido) tanto o objetivo em si quanto a maneira de alcançá-lo, o acaso é importante
O objetivo do artigo de pesquisa é comparar os métodos de encontrar o alvo como móvel (objeto amarelo) e imóvel.
Estes métodos:
- Pesquisa aleatória (objeto vermelho)
- Pesquisa aleatória com memória (objeto azul)
- Pesquisa aleatória com memória e hierarquia (objeto verde)
- Procure a primeira rota (objeto roxo)
- Procure uma rota curta (objeto marrom)
Na Fig. 1, esses objetos são mostrados. Código de programa totalmente publicado no
github
2. A parte principal
2.1 Classe P - Pesquisa Aleatória
O construtor inicializa os atributos e variáveis da classe: janela principal, cor, coordenada ye x, contador, dicionário visitado, destino, dicionário de hierarquia, dicionário de vizinhos. O método init_3_dict preenche três dicionários. O método show pinta a célula na cor desejada. O método update atualiza o objeto. O método top_show cria uma janela de nível superior e mostra quantas etapas foram tomadas para o destino.
class P(): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] P.target = target self.count = 0 self.visit = {} P.hierarchy = {} P.neighbor = {} self.init_3_dict(maps, ban)
A função is_en é declarada no método init_3_dict, que verifica se a coordenada não foi banida e não vai além do mapa.
def init_3_dict(self, maps, ban): def is_en(yx): if yx[0] < 0 or yx[0] > len(maps)-1: return if yx[1] < 0 or yx[1] > len(maps[0])-1: return if yx in ban: return return True
Em um ciclo, no dicionário visitado com a tecla de coordenadas, escreva o valor inicial zero. No dicionário da hierarquia com a mesma chave, escreva o nome hierárquico dessa coordenada. Em seguida, preenchemos o dicionário de vizinhos chamando a função is_en.
for y in range(len(maps)): for x in range(len(maps[0])): self.visit[(y,x)] = 0 P.hierarchy[(y,x)] = maps[y][x] n = [] if is_en((y-1,x)): n.append((y-1,x)) if is_en((y+1,x)): n.append((y+1,x)) if is_en((y,x-1)): n.append((y,x-1)) if is_en((y,x+1)): n.append((y,x+1)) P.neighbor[(y,x)] = n
O método show pinta uma célula com coordenadas y, x na cor desejada.
def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=P.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1)
O método move move o objeto. Nas variáveis y, x, escrevemos a coordenada do vizinho, que é selecionada aleatoriamente na lista de vizinhos. Em seguida, redesenhamos com as novas coordenadas.
Nós aumentamos o contador. Verifique se o objetivo foi alcançado. Se o objetivo for alcançado, na variável da classe J.disable, escrevemos corretamente. Chamamos o método top_show ().
def move(self): v = [] for i in P.neighbor[(self.y, self.x)]: v.append(i) y,x = random.choice(v) self.show(self.y, self.x, 'white') self.y = y self.x = x self.show(y, x, self.color) self.count +=1 if P.target == P.hierarchy[(self.y, self.x)]: J.disable = True self.top_show()
O método de atualização chama mover e atualiza a cada meio segundo.
def update(self): self.move() self.root.after(500, self.update)
O método top_show exibe os resultados.
def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop()
2.2 Classe M - Pesquisa Aleatória em Memória
O construtor chama o construtor da classe pai e aumenta o valor da célula do campo para onde estamos indo. O método move move o objeto. O método de escolha retorna a coordenada que o algoritmo de pesquisa aleatória com memória selecionou.
No método de movimentação, chame o método de escolha. Caso contrário, seu trabalho é semelhante ao método dos pais.
def move(self): yx = self.choice((self.y, self.x))
O método de escolha itera sobre as coordenadas dos vizinhos e adiciona tuplas à lista v. O primeiro elemento da tupla será a coordenada do vizinho, o segundo - quantas vezes ele foi visitado. Depois, classificamos de pequeno a grande. Classificamos todas as tuplas e, na lista v, deixamos apenas aquelas que ocorreram quantas vezes foram registradas na primeira tupla. Selecione aleatoriamente qualquer um deles.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.3 Classe N - pesquisa aleatória com memória e hierarquia.
O método de escolha seleciona as tuplas que mais se aproximam do nome hierárquico do destino. Se essa correspondência for a mesma, as coordenadas menos visitadas serão selecionadas.
O construtor chama o construtor do pai e inicializa o atributo de coincidência, o número de correspondências de caracteres do nome hierárquico com o destino.
def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0
O método de escolha no loop grava o nome hierárquico da coordenada atual do vizinho. A variável r armazena o número de correspondências dessa variável com o destino. Se o número de correspondências r for maior, a coincidência será substituída. Nesse caso, a tupla (coordenadas, número de visitas) da lista v é gravada na lista d. Se r é igual a coincidência, então em d adicionamos uma tupla de v.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) d = [] for l in v: c = P.hierarchy[l[0]] r = 0 for i in range(len(P.target)): if c[i] == P.target[i]: r +=1 else: break if r > self.coincidence: self.coincidence = r d = [l] if r == self.coincidence: d.append(l) if d: v = d v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.4 Classe K - procure uma rota e procure a rota mais curta.
O construtor grava coordenadas finais na variável final. Se o parâmetro curto for False, chamaremos a pesquisa de rota. Caso contrário, encontraremos o caminho mais curto.
O método find_path adiciona a coordenada atual à rota. Se a meta for atingida, retornará a rota. Separamos todos os vizinhos. Se não houver vizinho no caminho, então nos chamamos recursivamente. E o fato de o método retornar é gravado em newpath. A primeira rota encontrada será newpath. A diferença entre o método find_short_path é que, se o comprimento do caminho novo for maior ou igual ao comprimento do menor, o menor será substituído.
def find_path(self, node, end, path=[]): path = path + [node] if node == end: return path for v in P.neighbor[node]: if v not in path: newpath = self.find_path(v, end, path) if newpath: return newpath
2.5 A classe J é um alvo em movimento.
Um objeto da classe J se move como a classe P. Se a variável da classe J.disable for verdadeira, o objeto será interrompido.
2.6 Função principal.
Crie a janela principal. Na variável de destino, escreva o nome hierárquico do destino. A lista de proibições contém as coordenadas das células proibidas. Na lista de mapas, o próprio mapa. No loop, desenhamos um mapa. Crie objetos de classe. Em seguida, chamamos a função update, que atualiza os objetos.
3. Conclusões
Foram realizadas cinco experiências, tanto para um alvo em movimento quanto para um imóvel.
A Tabela 1 mostra que o melhor algoritmo é a rota mais curta. O segundo mais eficaz é uma pesquisa aleatória com memória e hierarquia. O pior é a pesquisa aleatória.
Tabela 1. Alvo fixo
No caso de um alvo em movimento, os resultados são diferentes. Os piores algoritmos foram aqueles que inicialmente calcularam a rota para a meta. Na tabela 2, um traço indica que o objetivo não foi alcançado. Brown acabou sendo pior que Violet. Pior, porque Violet tem uma trajetória mais longa (a chance de atingir um alvo em movimento é maior). O melhor algoritmo ao procurar um alvo em movimento é uma pesquisa aleatória com memória e hierarquia. Em segundo lugar, é uma pesquisa aleatória com memória.
Tabela 2. Alvo Móvel
Se não se sabe se o destino está se movendo ou não, é melhor usar o algoritmo de pesquisa aleatória com memória e hierarquia ou apenas pesquisa aleatória com memória.
4. Conclusão
A aleatoriedade é importante se a busca por um alvo ocorrer diante da incerteza. A pesquisa é reduzida se os dados forem apresentados hierarquicamente. A memória, é claro, também é valiosa.