fundo
Eu estava jogando o jogo para PC "Darkest Dungeon" recentemente. No jogo, você precisa explorar as masmorras, que consistem em salas conectadas, como mostrado na figura abaixo.
Aqui estão as regras:
- Você começa em sala fixa (entrada). Você não pode escolher por onde começar.
- O objetivo é visitar todos os quartos pelo menos uma vez
- A distância entre os quartos adjacentes é a mesma para todos os quartos.
- Você pode visitar quartos e percorrer caminhos sempre que desejar
Questão
Qual é o caminho mais curto desde a entrada que visita todos os quartos pelo menos uma vez?
Subquestões:
- Que algoritmo (s) poderia ser usado para resolver este problema?
- Existem implementações gratuitas (e bastante simples) para serem usadas por alguém como eu?
O que eu tentei
Encontrei outras perguntas como esta ou esta sem encontrar uma resposta. Estou familiarizado com o TSP (básico) e sou capaz de codificar e resolver TSPs simples. Os caminhos hamiltonianos não resolveram meu problema, porque não permitem várias visitas. O problema do carteiro chinês também não se aplica aqui em sua forma básica, porque não preciso visitar todos os cantos.
Atualizar
Como afirmei nos comentários, não sou cientista da computação e não estou interessado em provar declarações matemáticas (talvez eu deva postar esta pergunta no stackoverflow posteriormente). Além disso, não sou programador e as chances de codificar uma solução são muito pequenas. Mas suspeito que não sou o primeiro a lidar com um problema dessa natureza.
De acordo com @Shreesh e @Dib, o seguinte procedimento pode ser aplicado:
- Crie uma matriz de distância aos pares com todas as salas, adicionando arestas entre todas as salas.
- Resolva o TSP usando um solucionador padrão (por exemplo, concorde)
- A partir da entrada, visite todos os quartos de acordo com a solução. Para salas não adjacentes, substitua a menor distância entre essas salas.
Este procedimento fornecerá a resposta para o problema?
fonte
Respostas:
O problema do vendedor ambulante, mesmo que você permita a repetição de nós é difícil para o NP. Veja Complexidade Computacional do TSP .
Umans e Lenhart mostram resultados de dureza para Hamiltonian Graphs em Solid Grid Graphs, 1997 .
TSP para Euclideal Case (ou gráficos com desigualdade de triângulo) também implica dureza NP de TSP com repetição de nó. TSP mesmo para distância de manhattanL1 (ou L∞ ) métrica é NP-completa. Veja o artigo original de Papadimitriou sobre o assunto .
Você pode provar a dureza NP do TSP para o seu caso adicionando arcos aos nós com distância correspondente como o comprimento do caminho mais curto entre os nós, que simulará repetições dos nós. O TSP para seu caso especial parece um problema completo de NP.
Portanto, escreva um ramo exponencial e algoritmo vinculado suficientemente bom (em termos heurísticos) para calcular um tour mais curto (que pode não ser tão ineficiente, se o gráfico for pequeno) ou esqueça a otimização e calcule uma aproximação suficientemente boa.
fonte
Você pode tratar isso como um problema de planejamento de cobertura de caminho modificado que pode ser resolvido em algumas etapas simples:
1) Construa um gráfico não direcionado não ponderado a partir das salas de grade, as junções de caminho são nós e limita os caminhos entre esses nós.
2) Encontre a árvore de abrangência mínima a partir do seu ponto de partida usando a primeira pesquisa de profundidade.
3) "Subdivide" a grade subjacente para que sua árvore de abrangência mínima crie duas "faixas".
4) No seu ponto de partida, caminhe no sentido horário na faixa da direita, de nó em nó, até retornar ao ponto de partida na faixa complementar.
Isso fornecerá um tour mínimo pelas salas, em tempo proporcional ao número de peças na masmorra, e é essencialmente o algoritmo de planejamento de caminho da Cobertura em Árvore de Abrangência em Espiral aplicado a uma configuração reduzida. (Cf. "Spiral-stc: um algoritmo de cobertura on-line de ambientes de grade por um robô móvel")
fonte
Além da resposta acima, eu indicaria alguns solucionadores de TSP já disponíveis.
fonte