Resolvendo um labirinto com funil de números

18

Meu filho de 8 anos se cansou de criar labirintos convencionais e passou a criar variantes que se parecem com isso:

Amostra do funil de número

A idéia é começar de x e alcançar o através das regras normais. Além disso, você pode "saltar" de qualquer número inteiro para qualquer outro número inteiro b , mas você deve pagar | a - b | dólares pelo privilégio. O objetivo é resolver o labirinto pelo menor custo. No exemplo acima, poderíamos ir de x para o via x-14-18-27-28-o no custo 5, mas é mais barato ir para x-13-11-9-8-29-28-o apenas 4)ab|ab|

Então, aqui está a minha pergunta: qual é a melhor solução (em termos de tempo de execução assintótica) que você pode pensar para resolver isso? Você pode fazer suposições razoáveis ​​sobre o formato de entrada.

Nota: Estou usando a tag "puzzles" aqui porque tenho uma resposta em mente, mas não tenho certeza se é o ideal e gostaria de ver se alguém pode melhorar minha solução. (Aqui n é o número de números inteiros no labirinto.)O(n2)n

Fixee
fonte
7
Adereços para o seu filho para criar esses quebra-cabeças criativos e matemáticos!
bbejot 2/11/11
2
@bbejot Você deve ver algumas das coisas que ele me pergunta ... às vezes não consigo responder às perguntas dele. Por exemplo, math.stackexchange.com/questions/33094/…
Fixee
1
Não tenho certeza de que seus cálculos de custos estejam corretos. x-14-18-27-28-o deve custar e x-13-11-9-8-29-28-o deve custar 2 + 2 + 1 + 21 + 1 = 27 . 4+9+1=142+2+1+21+1=27
Dave Clarke
1
@ Nem todas as transições são saltos. Poderíamos escrever 'ab' para saltos (que têm um custo de ) e 'a-> b' para caminhar no gráfico de a para b (que tem um custo de 0 ), o que é permitido somente se eles são acessíveis sem quebrar uma parede no labirinto. Nesta notação, temos x-> 14-18-> 27-28-> o e um custo de 5 e x-> 13-11-> 9-8-> 29-28-> o. Fino que Fixee não introduziu essa notação por ser redundante: não há razão para pular duas vezes e, portanto, os saltos e caminhadas no labirinto se alternam. |ab|0
Artem Kaznatcheev
2
Este é um excelente problema de lição de casa!
Jeffε 3/11/11

Respostas:

15

O(nlogn)yyyy+yy

Essas atualizações são suficientes para manter a pilha retornando o elemento mínimo porque qualquer nó mais próximo para o qual você salta deve estar numericamente logo acima ou logo abaixo de um nó já visitado.

yy+O(nlogn)O(n)O(nlogn)O(nlogn)

Dave
fonte
x1,,xnxo2xi2xi+1xixixi
O(nlgn)y+yO(nlgn)
O(nloglogn)O(n)
4

O(n2)

Parece natural converter isso no problema de caminho mais curto com um nó inicial especial (x) e um nó final (0). Também haveria um outro nó para cada um dos números. Tanto x como 0 têm arestas de peso 0 para todos os nós numéricos que são alcançáveis ​​no labirinto. Todos os nós numéricos são conectados com o peso 0 (se os números forem acessíveis pelo labirinto) ou com a diferença entre os números (se não for possível com o labirinto).

O(n2)n2O(n2)

bbejot
fonte
O(n2)O(n2lgn)
1
rO(r2)
O(nlogn)O(r2+nlogn)Ω(nlogn)
Ω(n2)