Início / coding / Perguntas / 77810560
Accepted
ABGR
Asked: 2024-01-13 14:50:02 +0800 CST

Alcançando o vértice d em um tetraedro em n etapas

  • 772

Eu estava resolvendo este problema:

Dado um tetraedro com vértices A, B, C e D. Uma formiga está no vértice D. A formiga não fica parada. Ele continuará se movendo de um vértice para outro ao longo de alguma aresta do tetraedro. Sua tarefa é contar o número de maneiras pelas quais a formiga pode ir do vértice inicial D até si mesma em exatamente n passos.

Então, para entrada 2 Saída: 3

Consegui resolver isso confortavelmente usando recursão da seguinte maneira. Mas não parece muito eficiente para uma entrada grande, digamos, 15, devido à sua complexidade de tempo.

Isso pode ser resolvido através de programação dinâmica, mas não vejo nenhum escopo de memoização na minha abordagem atual. Talvez eu precise mudar a abordagem. Então aprecio qualquer ajuda.

Eu gostaria de resolver isso usando recursão + memoização 

var count = 0;
function recursion(n, arr=['d']){
    if(n <=1) return 0;
  
  if(arr.length === n+1 && arr[arr.length-1] ==='d'){
    console.log(arr.join(" -> "))
    count++;
    return;
  }

  if(arr.length > n+1) return;

  for(let el of ['a', 'b', 'c', 'd']){
    if(arr[arr.length-1] != el){
       recursion(n, [...arr, el]);
    }
  }
}
recursion(3)

console.log(count);

algorithm

1 respostas

  1. Best Answer

    Você realmente pode usar memoização aqui.

    Primeiro vamos analisar as relações de recorrência.

    Definir:

    • 𝑆 𝑛 como o número de caminhos de comprimento 𝑛 para ir de um vértice até ele mesmo.

    • 𝐷 𝑛 como o número de caminhos de comprimento 𝑛 para ir de um vértice a outro escolhido . Não importa qual vértice de destino escolhemos, pois o tetraedro é completamente simétrico.

    Agora as relações de recorrência:

    Para obter o número de caminhos de comprimento 𝑛 até o vértice original (𝑆 𝑛 ), você pode escolher um vizinho entre três vizinhos e depois contar o número de caminhos (mais curtos) de lá até o vértice inicial, que é dado por 𝐷. Então:

          𝑆 𝑛 = 3𝐷 𝑛−1

    Para obter o número de caminhos de comprimento 𝑛 para um vértice diferente (𝐷 𝑛 ), você pode escolher esse vizinho e contar o número de caminhos (1 passo mais curto) dele até ele mesmo, ou pode escolher um dos outros dois vizinhos e conte o número de caminhos (1 passo mais curto) de lá até o vértice de destino. Então:

          𝐷 𝑛 = 𝑆 𝑛−1 + 2𝐷 𝑛−1

    A última equação pode ser expandida por substituição a esta relação de recorrência:

          𝐷 𝑛 = 3𝐷 𝑛−2 + 2𝐷 𝑛−1

    Ao referenciarmos 𝑛−2, precisamos ter pelo menos dois casos base:

    • 𝐷 0 = 0 (não existem caminhos de tamanho 0 que levem você a outro vértice)
    • 𝐷 1 = 1 (há um caminho de tamanho 1 de um vértice para outro)

    Implementação

    Como temos uma boa relação de recorrência para 𝐷, poderíamos primeiro implementar uma função que devolve o número de caminhos de um vértice para outro . E então use a primeira relação para traduzir a consulta original (para o número de caminhos para o mesmo vértice) nesse problema:

    // Memoize the number of paths from one vertex to a different one
const memo = new Map().set(0, 0).set(1, 1);

function numPathsToOther(size) {
    let result = memo.get(size);
    if (result === undefined) {
        result = 3*numPathsToOther(size-2) + 2*numPathsToOther(size-1);
        memo.set(size, result);
    }
    return result;
}

function numPathsToSelf(size) {
    return size ? 3 * numPathsToOther(size - 1) : 1;
}

// Demo runs for the first few path-sizes:
for (let i = 0; i <= 10; i++) {
    console.log(i, numPathsToSelf(i));
     console.log((3*0^i-(-4)^i)/4)
}

    Exemplo

    Digamos que rotulamos os quatro vértices como 𝑎, 𝑏, 𝑐 e 𝑑 como você fez, e que 𝑛 é 3. Queremos saber o número de caminhos de tamanho 𝑛 que começam e terminam no vértice 𝑎.

    Existem três maneiras de iniciar esse caminho: 𝑎→𝑏, 𝑎→𝑐 ou 𝑎→𝑑. Vamos pegar 𝑎→𝑏. Agora precisamos saber quantos caminhos existem de tamanho 2 que começam em 𝑏 e terminam em 𝑎.

    Aqui, vamos parar por um minuto. Você pode perceber que não há nada de especial em 𝑎 e 𝑏. Eles são apenas vizinhos, mas aí vem: quaisquer dois vértices em um tetraedro são vizinhos e se relacionam entre si da mesma maneira que 𝑎 a 𝑏. Portanto, podemos generalizar este caso como “o número de caminhos de um vértice a outro” !

    Para o caso em que o tamanho desse caminho precisa ser 2, existem apenas dois caminhos possíveis de 𝑏 que terminam em 𝑎: ou passamos por 𝑐 ou passamos por 𝑑.

    Agora voltamos à situação inicial. Dissemos que caminhos de tamanho 3 de 𝑎 de volta a 𝑎 poderiam passar primeiro por 𝑏, e agora sabemos que de 𝑏 existem duas possibilidades. Mas também poderíamos ter passado de 𝑎 para 𝑐, ou de 𝑎 para 𝑑. E como o tetraedro é completamente simétrico, podemos concluir imediatamente que também essas duas alternativas representam 2 caminhos cada. Portanto, no total encontramos 3x2=6 caminhos.

    Esta pequena análise mostra que é útil saber qual é o número de caminhos de um vértice a outro vértice.

    Fórmula fechada

    A relação de recorrência tem solução. oeis.org fornece:

    Número de passeios fechados de comprimento n ao longo das arestas de um tetraedro baseado em um vértice.

    FÓRMULA a(n) = (3^n + (-1)^n*3)/4.

    for (let i = 0; i <= 10; i++) {
    console.log(i, (3**i + (-1)**i*3)/4)
}

    • 1

relate perguntas