Problema de reconfiguração "Cobra"

13

Enquanto escrevia um pequeno post sobre a complexidade dos videogames Nibbler e Snake ; Descobri que ambos podem ser modelados como problemas de reconfiguração em gráficos planares; e parece improvável que esses problemas não tenham sido bem estudados na área de planejamento de movimento (imagine, por exemplo, uma cadeia de carros ou robôs interligados). Os jogos são bem conhecidos, no entanto, esta é uma breve descrição do modelo de reconfiguração relacionado:

PROBLEMA DA SERPENTE

Entrada : dado um gráfico planar , l seixos p 1 , . . . , P l são colocados nos nós u 1 , . . . , U l que formam um caminho simples. As pedras representam a cobra , ea primeira p 1 é sua cabeça. A cabeça pode ser movida de sua posição atual para um nó livre adjacente e o corpo a segue. Alguns nós são marcados com um ponto; quando a cabeça atinge um nó com um ponto, o corpo aumenta emG=(V,E)eup1,...,peuvocê1,...,vocêeup1 seixos nas seguintes e movimentos da cabeça. O ponto no nó é excluído após a travessia da cobra.ee

Problema : Perguntamos se a cobra pode ser movida ao longo do gráfico e alcançamos uma configuração alvo onde a configuração alvo é a descrição completa da posição da cobra, ou seja, a posição dos seixos.T

É fácil provar que o problema SNAKE é NP-difícil em gráficos planares de grau máximo 3, mesmo que nenhum ponto seja usado e também em gráficos de grade SOLID, se pudermos usar um número arbitrário de pontos. As coisas ficam complicadas em gráficos de grade sólidos sem pontos (isso está relacionado a outro problema em aberto).

Gostaria de saber se o problema foi estudado sob outro nome.
e, em particular, se houver uma prova de que está em NP ...

Edit: o problema acabou sendo completo no PSPACE, mesmo em gráficos planares, e o resultado parece muito interessante; portanto, resta descobrir se é um problema novo e se há resultados conhecidos sobre ele.

insira a descrição da imagem aqui
Um exemplo simples (seixos são mostrados em verde, a cabeça da cobra é P1).

Marzio De Biasi
fonte
1
NPNPeNP
Você pode fornecer uma definição melhor e clara para a configuração do destino? por exemplo, o que você quer dizer com descrição completa da posição da cobra?
Saeed
@ Saeed: a configuração do alvo é simplesmente a posição final dos seixos (isto é, a cobra). Vou adicionar uma figura para esclarecer o problema.
Marzio De Biasi
Sua pergunta foi clara o suficiente, mas eu misturei a terminologia no meu comentário. Deve ler "pontos" em todos os lugares, em vez de "seixos".
Tom van der Zanden
@ TomvanderZanden: ok obrigado, concordo com você (veja também meu comentário à resposta do Zimmux). Escrevi "... com ou sem pontos ..." para dizer que são irrelevantes; mas não estava claro o suficiente; então editei a pergunta e a tornei mais explícita.
Marzio De Biasi

Respostas:

8

Mover uma cobra de uma posição para outra é o PSPACE completo. Snake está trivialmente no PSPACE. Damos uma redução na dureza do PSPACE a partir da lógica de restrições não determinísticas de Hearn.

Lógica de restrição não determinística

12223132Gadgets NCL

Serpente

Em nossa construção, a cabeça da cobra estará perseguindo sua cauda a uma pequena distância e será forçada a repetir o mesmo ciclo com pequenas modificações. Incorporamos cada aresta do gráfico de restrição como na figura (arestas mostradas em vermelho), onde indicamos a posição da cobra por linhas grossas. Uma aresta tem dois lados (vértices) e a cobra segue a rota central no vértice para o qual a aresta é direcionada. Invertendo uma aresta

Para inverter uma aresta, a cobra primeiro limpa a rota central e depois segue a rota central quando sua cabeça atinge o vértice oposto.

2

Cobra E Cobra Ou

Finalmente, as linhas pretas de todos os dispositivos de borda são conectadas para formar um único ciclo, de modo que a cabeça da cobra persegue sua cauda. Se entre dois dispositivos de borda, tornamos o caminho preto suficientemente longo, a cobra sempre deve atravessar os caminhos pretos na mesma ordem cíclica.

Para mostrar que os caminhos pretos sempre podem ser construídos de maneira plana, considere uma subárvore de abrangência (arestas grossas na figura abaixo) do gráfico de restrição. Em seguida, podemos fazer com que as bordas pretas sigam essa árvore, conforme ilustrado abaixo, resultando em um gráfico planar.

Subárvore de abrangência Ciclo Planar

A posição alvo da cobra pode ser derivada pela mesma transformação. Portanto, a reconfiguração de uma cobra é completa no PSPACE, mesmo em gráficos planares.

Tim
fonte
Ótimo! :-) :-) :-)
Marzio De Biasi