Dado um labirinto bidimensional onde você pode dar 4 comandos "mover para cima / baixo / direita / esquerda". Conhecendo o labirinto, mas não onde está a pessoa, como encontrar a sequência mínima de comandos que garante a saída do labirinto? Estou procurando uma única sequência de comandos que funcione, não importa de onde você comece no labirinto.
Suponha que se o nosso parceiro receber o comando "mover para a direita" quando houver uma parede à direita, ele simplesmente permanecerá onde está.
Em outras palavras, recebemos um labirinto e precisamos escolher uma sequência de comandos. Então, nosso parceiro será colocado em algum lugar do labirinto e seguirá a sequência de comandos que escolhemos com antecedência. Queremos que essa sequência garanta que nosso parceiro escape, independentemente de onde ele foi colocado inicialmente. Observe que os comandos permitidos não possuem nenhuma declaração condicional; portanto, eles não podem seguir uma sequência diferente, dependendo da sua parceira.
Existe um algoritmo de tempo polinomial para construir essa sequência, dada uma descrição do labirinto?
Yuval Filmus menciona que este é um caso especial de um problema de sincronização de palavras e pode estar relacionado a sequências transversais universais. Eu também encontrei um artigo que parece relevante:
O Problema Simultâneo de Resolução de Labirinto . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.
Infelizmente para gráficos gerais isso parece ser um problema não resolvido, mas estou me perguntando se pode haver um bom algoritmo para esse caso específico. Eu vim com uma abordagem candidata: identifique todas as posições com o número mínimo de etapas necessárias para sair e acompanhe todos os agentes no labirinto. Pode ser possível fazer uma pesquisa A * dessa maneira.
fonte
Respostas:
fonte