Perguntas[algorithm](coding)

Estou procurando um algoritmo de busca de caminho que tenha algumas propriedades:

1. A velocidade é muito necessária, e uma vez que um objetivo é selecionado, um caminho subótimo precisa ser feito rapidamente, e então pode ser melhorado durante o movimento. Isso me faz pensar que preciso de um " algoritmo a qualquer momento "
2. O ambiente tem outros atores nele, e então muda constantemente . Isso me faz pensar em um algoritmo baseado em D* ou D* Lite , para que o caminho possa ser rapidamente substituído.

Esses dois requisitos me indicaram o Anytime D* , que parece funcionar bem, exceto pelo meu requisito final:

3. O caminho retornado deve ser rápido de seguir e direto . Caminhos produzidos pelo Campo D* são ótimos exemplos.

Existe um algoritmo que combina os aspectos desses dois algoritmos (Anytime D* e Field D*)? Se não, é possível incluir as melhorias do Anytime D* no Field D*? Ou estou esquecendo de algo e já tenho o que preciso?

Estou escrevendo isso mais tarde à noite no meu tempo, então não poderei responder a nada por algumas horas. Espero ter contexto suficiente.

Obrigado por toda e qualquer ajuda!

Existe um algoritmo que produz um embaralhamento eficiente de um uint32 em um uint32 diferente que resulta em um mapeamento 1:1 quando recebe uma semente aleatória alterável?

Minha orientação inicial sobre isso é um algoritmo em que a semente expressa de alguma forma quais bits reorganizar no número (de modo que 0000 0101 se torne 0100 1000 com a semente [0->6, 2->3]), mas não tenho certeza de como gerar uma maneira de fazer esse embaralhamento de forma eficiente.

Algumas restrições:

• A produção do algoritmo para realizar o embaralhamento a partir da semente não precisa ser muito rápida
• Na verdade, executar o shuffle em um uint32 deve ser rápido
• Não deve haver repetições na saída para uma semente fornecida (um uint32 exclusivo produz um uint32 exclusivo)

Eu estava resolvendo um teste em uma plataforma online e o problema era parecido com este.

Stuart tem que ir de um lugar para outro (A-> B) e ele pode pular 1 passo, 2 passos ou 3 passos de cada vez. Pode haver n número de paradas entre A e B.

Precisamos descobrir quantas maneiras ele pode fazer isso.

Eu sinto que isso é similar ao problema clássico de subir escadas com pouca diferença de que lá você finalmente tinha que chegar ao n-ésimo degrau, enquanto neste problema em particular você tem que descer, o que faz provavelmente n+1 degrau. Estou certo?

Então o código que escrevi é este:

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

Isso não foi aceito. Então, estou apenas me perguntando o que há de errado nisso. Eu deveria ter adicionado base case para n==2também?

if (n === 2) return 4

Isso ainda não adianta nada, pois n = 3retornaria 6, enquanto visualmente posso ver que haveria 7 maneiras se houvesse 3 paradas.

Outra pergunta que quero fazer é:

No caso clássico de escada, o caso base para n === 0seria 1. Ainda seria o mesmo aqui? Isso me confunde um pouco, pois quando não há mais degraus para subir, como o resultado pode ser 1. Por outro lado, aqui, quando n === 1você ainda tem um caminho que deve seguir para chegar ao destino.

Além disso, f(3)a lógica e a intuição dizem que deveria ser:

number of ways to reach first stopover + f(2)

E number of ways to reach first stopoverseria apenas um, já que só há uma maneira de fazer isso (dando um salto).

No entanto, não posso colocar if(n == 1) return 1no caso base, pois seria incorreto. Digamos que há apenas uma parada (n = 1), na verdade há duas maneiras de chegar:

1. Pular 2 passos
2. Pule 1 passo e depois mais um.

Então isso também está criando um pouco de confusão.

Nas pp.296 Algoritmo de Sedgewick & et al. , 4ª edição, o autor escreveu:

O valor ideal do ponto de corte M depende do sistema, mas qualquer valor entre 5 e 15 provavelmente funcionará bem na maioria das situações.

Mas não entendo o que significa que o valor de corte é dependente do sistema, porque o desempenho de um algoritmo é medido com base no número de operações que ele executa e não independe da velocidade do processador do computador?

ALGO(A,s,d)
    m=d-s+1
    if m>=2 then
        q=⌊m/2⌋
        return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
    else
        return 1
    endif

Eu tenho esse pedaço de código e preciso encontrar a relação de recorrência em função de n. O problema afirma que o algoritmo é inicialmente chamado com ALGO(A, 1, n). A é um array de tamanho n, se dsão inteiros, qé a função de chão de m/2.

A solução que encontrei foi:

T(n) = 1 if n<2

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) if n>=2.

Meu raciocínio foi que if s=1e d=nentão m=n, q=⌊n/2⌋e na primeira chamada recursiva eu ​​tenho s=1e d=⌊n/2⌋então m=⌊n/2⌋, para a segunda chamada s=s+q=1+⌊n/2⌋ d=nentão m=⌈n/2⌉então T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1)porque dentro do if eu calculo qqual custa 1. Eu não sei se a solução que eu criei está correta ou não e eu não sei como resolver isso. Para a resolução eu não sei se eu posso dizer que T(⌊n/2⌋) + T(⌈n/2⌉) = T(n).

Estou trabalhando em um desafio envolvendo um autômato celular infinito 3D (cúbico) definido como:

• Estado inicial : Começamos com 8 células posicionadas nos vértices de um cubo e cada célula está em um dos 4 estados {0: rosa, 1: vermelho, 2: verde, 3: azul}.

• Crescimento : A cada passo, o cubo se expande inserindo novas células entre cada par de células existentes. O estado da nova célula é determinado pela soma dos estados de seus vizinhos mais próximos módulo 4. Note que, dependendo de sua posição, uma nova célula tem 2, 4 ou 8 vizinhos mais próximos (é a vizinhança de Moore 3D).

Para ilustrar isso, aqui estão algumas ilustrações dos primeiros passos:

Estado inicial

Passo 1

O nó central por exemplo será Verde porque tem 8 vizinhos, a soma dos tipos deles é 2 (Verde) + 1 (Vermelho) + 1 (Vermelho) + 0 (Rosa) + 2 (Verde) + 0 (Rosa) + 3 (Azul) + 1 (Vermelho) = 10% 4 = 2 (Verde)

Passo 2

Estamos interessados ​​em rastrear a evolução do número de células de cada estado [0, 1, 2, 3]. Aqui estão as contagens para os primeiros passos:

• Inicial: 2, 3, 2, 1
• Passo 1: 6, 10, 7, 4
• Passo 2: 30, 36, 31, 28
• Etapa 3: 196, 192, 155, 186
• Etapa 4: 1'162, 1'276, 1'207, 1'268

Nosso objetivo é determinar a contagem de cada estado de célula na etapa 19. Dado o crescimento exponencial, a força bruta não é viável. Disseram-me que é possível resolver isso em menos de um segundo. Alguém tem alguma ideia de como resolver esse problema?

Agradecemos desde já a sua ajuda!

Eu me deparei com uma implementação bastante trigonométrica para converter cores de RGB para HSI. Em particular, converter de RGB para o "espaço de cores HSI, dado por um cone duplo ", que eu presumo ser outro nome para o modelo bi-hexcone de HSL .

Os autores descrevem equações para "sua escolha preferida de transformação" de RGB-->HSI, que implementei em Python como abaixo. Nada é dado a transformação reversa, HSI-->RGB.

def rgb_to_hsi(r, g, b):
    # r, g, b in [0..1]
    x = min(r, g, b)
    y = max(r, g, b)
    I = (x + y) / 2.0
    S = y - x
    c1 = r - (g + b) / 2.0
    c2 = (np.sqrt(3) * (b - g)) / 2.0
    H = np.arctan2(c2, c1)
    H = np.mod(-H, 2 * pi) # re-range to [0..2PI], rotating from red at 0 to green at 2/3PI, etc.

    return [H, S, I] # H in [0..2PI], S in [0..1], I in [0..1]

Tanto o algoritmo quanto minha implementação parecem estar corretos e fornecem resultados que estão de acordo com este diagrama (ou seja, red ( rgb(1,0,0) ) fornece [0.0, 1, 0.5]):

Mas não consigo encontrar ou derivar um inverso funcional dessa conversão – um hsi_to_rgb()método.

Tentei algumas implementações, mas elas tendem a mapear hsi(0.0, 1, 0.5)( rgb(0.5, 0, 0)vermelho com metade do brilho, em vez de brilho total).

Suspeito que isso ocorra porque a maioria das implementações de HSL usa o modelo cilíndrico de HSL, e não o modelo de cone duplo – isso é verdade?

De qualquer forma, qual é um algoritmo funcional (e idealmente trigonométrico) para conversões do modelo de cone duplo HSL para RGB?

Dado um inteiro de 64 bits sem sinal y, existe uma maneira eficiente de encontrar todos os inteiros de 64 bits sem sinal xtais que (x & (x + y)) == 0?

Alguns exemplos para pequenos y:

• y=0: única solução possívelx=0
• y=1: todas as soluções são da forma x=(1<<n)-1para algum n>=0
• y=2: todas as soluções são da forma x=(1<<n)-2para algum n>=1
• y=3: ou x=(1<<n)-3, n>=2, ou x=(1<<n)-2, n>=1

Em geral, o número de casos a serem considerados depende do número de execuções de uns e zeros na representação de bits de y.

Uma solução para o problema poderia ser uma função iteradora, que encontra o próximo válido x, como o seguinte:

uint64 next(uint64 x, uint64 y) {
    x++;
    while (x & (x+y)) x++;
    return x;
}

Como o critério (x & (x + y)) == 0é bastante simples, esse pode ser um problema conhecido para o qual existe uma solução mais eficiente do que a acima.

Estou tentando encontrar uma solução para este desafio:

Dado é n, que é o tamanho de um array preenchido com uns. Há dois tipos de operações possíveis neste array:

• Aumentar (x, y, m): adiciona m a todos os elementos da matriz no intervalo da posição x até y (inclusive). 1 <= x <= y <= n.
• Dê (x, y): retorna o comprimento máximo de uma sequência não decrescente no intervalo fornecido.

Exemplo:

Entrada: n = 5:

Operações:

1. Aumentar 1 2 3 (x = 1, y = 2, m = 3)

   Agora nossa matriz é[4, 4, 1, 1, 1]

2. Dê 2 4 (x = 2, y = 4)

   O comprimento máximo é 2 porque a sequência máxima não decrescente é 1, 1.

Procuro uma solução em que cada operação tenha complexidade de tempo O(log(n)).

Minha abordagem

Notei que podemos armazenar esse array como um array de zeros, onde cada elemento representa como ele é maior que o anterior. Por exemplo, em vez de [1, 4, 2, 5]temos [0, 3, -2, 3]. Agora podemos encontrar facilmente sequências não decrescentes apenas olhando para números negativos. Tentei ir por esse caminho e otimizar a localização de números negativos (por exemplo, usando um conjunto ou árvore), mas para algumas situações a operação "Give" ainda terá uma complexidade O(n), que não é o que eu quero.

Aqui está como meu algoritmo funcionou:
Observe que, se usarmos um array de zeros, podemos alterá-lo (quando houver operação de aumento) em apenas duas etapas: arr[x] += m e arr[y + 1] -= m (presumo que arr seja baseado em 1). No começo, tenho um novo conjunto vazio. Durante a operação de aumento, faço essas duas etapas acima e então:

1. Se arr[x] após a operação "+= m" não for menor que 0, basta remover x do conjunto.

2. Se arr[y + 1] após a operação "-= m" não for mais igual ou maior que 0, basta adicionar y + 1 ao conjunto.

Depois de todas as operações de aumento, teremos um conjunto de todos os números negativos. E como escrevi acima, esses são intervalos não decrescentes. Por exemplo, se tivermos n = 6e set = {2, 6}, teremos 3 intervalos não decrescentes: (1, 1), (2, 5), (6, 6). Então, podemos fazer operações Give em O(set.size()), o que não é bom.

Como posso executar cada operação com complexidade de tempo O(logn)?

Estou resolvendo um problema leetcode 1372. Por que esses dois códigos retornam resultados diferentes? O primeiro dá a resposta correta. O segundo não.

# Definition for a binary tree node.

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            l_path = 1 + self.helper(root.left, d='l')
            self.longest_path = max(self.longest_path, l_path)
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')
        



class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

A única mudança é esta linha:

"self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))"