Dicas e Truques de Algoritmos Profissionais
Dicas e Truques de Algoritmos Profissionais
Algoritmos
Conteúdo
Sobre .................................................. .................................................. .................................................. ............................. 1
2.2: Comparação das notações assintóticas Seção 2.3: Notação .................................................. ........................................... 6
Seção 4.3: Para verificar se duas árvores binárias são iguais ou não .................................................. ................................... 15
Capítulo 6: Verifique se uma árvore é BST ou não Seção 6.1: .................................................. .................................................. ...... 24
Algoritmo para verificar se uma determinada árvore binária é BST Seção 6.2: .................................................. ................................ 24
Se uma determinada árvore de entrada segue a propriedade da árvore de busca binária ou não .................................................. ..... 25
Seção 9.5: Detecção de um ciclo em um grafo direcionado usando Depth First Traversal Seção 9.6: .................................................. 40
Seção 12.2: A* Encontrando caminho através de um labirinto sem obstáculos .................................................. ........................... 49
Seção 13.1: Exemplo simples de A* Pathfinding: Um labirinto sem obstáculos .................................................. ........ 59
Seção 20.1: Algoritmo de caminho mais curto de fonte única (Dado que há um ciclo negativo em um gráfico) ................. 113
Seção 22.1: Algoritmo do caminho mais curto para todos os pares ......................................................................................................... 124
Capítulo 23: Algoritmo do Número Catalão ....................................................................................................... 127
Seção 23.1: Informações básicas do algoritmo numérico catalão .................................................. .............................. 127
Seção 26.1: Edições mínimas necessárias para converter a string 1 em string 2 .................................................. ................. 133
por mesclagem Seção 30.2: Implementação de classificação por .................................................. .................................................. 150
por mesclagem em Java Seção 30.5: Implementação de classificação por mesclagem em Python ................................................................................................
153
Seção 34.1: Informações básicas sobre classificação .................................................. .................................................. ... 162
Seção 39.3: Análise de busca linear (pior, médio e melhor caso) ........................................................ 176
Seção 39.4: Busca binária: em números ordenados Seção .................................................. ................................................ 178
39.5: Busca linear .................................................. .................................................. .................................. 178
Seção 41.1: Encontrando o caminho mais curto da fonte para outros nós Seção .................................................. ................ 190
Seção 41.3: Componentes conectados de grafos não direcionados usando BFS Capítulo .................................................. ........... 197
Capítulo 43: Funções de hash Seção 43.1: .................................................. .................................................. ............................ 207
Códigos de hash para tipos comuns em C# Seção 43.2: .................................................. ............................................. 207
Introdução às funções de hash .................................................. .................................................. ...... 208
Capítulo 44: Caixeiro Viajante Seção 44.1: Algoritmo .................................................. .................................................. ................ 210
Seção 45.1: Noções básicas sobre o problema .................................................. .................................................. .............. 212
Seção 48.1: Informações básicas sobre a maior subsequência crescente .................................................. .................... 225
Capítulo 51: Algoritmo: Imprima uma matriz m*n ao quadrado.................................................. ........................... 232
Seção 52.1: Exponenciação de matrizes para resolver problemas de exemplo .................................................. ....................... 233
Capítulo 53: Algoritmo limitado em tempo polinomial para cobertura mínima de vértices ........................ 237
Sobre
[Link]
Este livro Algorithms Notes for Professionals foi compilado da documentação do Stack Overflow ,
o conteúdo é escrito pelas maravilhosas pessoas do Stack Overflow.
O conteúdo do texto é liberado sob Creative Commons BY-SA, veja os créditos no final deste livro
que contribuíram para os vários capítulos. As imagens podem ser protegidas por direitos autorais de
seus respectivos proprietários, a menos que especificado de outra forma
Este é um livro gratuito não oficial criado para fins educacionais e não é afiliado a grupos ou
empresas oficiais de Algoritmos nem ao Stack Overflow. Todas as marcas comerciais e marcas
registradas são propriedade de seus respectivos
donos de empresas
As informações apresentadas neste livro não são garantidas como corretas ou precisas, use
por sua conta e risco
Problema:
Classificação Entrada: Uma sequência de n chaves, um.
a_1, a_2, ..., Saída: A reordenação da sequência de entrada de modo que a'_1 <= a'_2...<= <= a'_{n-1} <= a'_n
Uma instância de classificação pode ser uma matriz de strings, como { Haskell, Emacs } ou uma sequência de números, como
{ 154, 245, 1337 }.
Para aqueles que são novos em programação em Swift e aqueles que vêm de diferentes bases de programação, como Python ou
Java, este artigo deve ser bem útil. Nesta postagem, discutiremos uma solução simples para implementar algoritmos swift.
Zumbido efervescente
Você pode ter visto Fizz Buzz escrito como Fizz Buzz, FizzBuzz ou Fizz-Buzz; todos eles se referem à mesma coisa. Essa "coisa" é o
principal tópico de discussão hoje. Primeiro, o que é FizzBuzz?
1 2 3 4 5 6 7 8 9 10
Fizz e Buzz referem-se a qualquer número que seja múltiplo de 3 e 5, respectivamente. Em outras palavras, se um número for divisível por 3,
ele é substituído por fizz; se um número for divisível por 5, ele é substituído por buzz. Se um número for simultaneamente múltiplo de 3 E 5, o
número é substituído por "fizz buzz". Em essência, ele emula o famoso jogo infantil "fizz buzz".
Para resolver esse problema, abra o Xcode para criar um novo playground e inicialize um array como abaixo:
Para encontrar todo o fizz e buzz, precisamos iterar pelo array e verificar quais números são fizz e quais são buzz. Para fazer
isso, crie um loop for para iterar pelo array que inicializamos:
Depois disso, podemos simplesmente usar a condição "if else" e o operador de módulo no swift ie - % para localizar o fizz e o buzz
Ótimo! Você pode ir ao console de depuração no playground do Xcode para ver a saída. Você verá que os "fizzes" foram classificados em seu
array.
Para a parte do Buzz, usaremos a mesma técnica. Vamos tentar antes de rolar o artigo — você pode conferir seus resultados com este artigo
quando terminar de fazer isso.
Verifique a saída!
É bem direto — você dividiu o número por 3, fizz e dividiu o número por 5, buzz. Agora, aumente os números na matriz
Aumentamos o intervalo de números de 1-10 para 1-15 para demonstrar o conceito de "fizz buzz". Como 15 é um múltiplo de 3 e 5, o número deve
ser substituído por "fizz buzz". Tente você mesmo e confira a resposta!
Espere... ainda não acabou! O propósito do algoritmo é personalizar o tempo de execução corretamente. Imagine se o intervalo aumentasse de
1-15 para 1-100. O compilador verificaria cada número para determinar se ele é divisível por 3 ou 5. Ele então executaria os números novamente
para verificar se eles são divisíveis por 3 e 5. O código essencialmente teria que executar cada número na matriz duas vezes — ele teria que
executar os números por 3 primeiro e depois executá-los por 5. Para acelerar o processo, podemos simplesmente dizer ao nosso código para
dividir os números por 15 diretamente.
se num % 15 == 0
{ print("\(num) zumbido efervescente")
} senão se num % 3 == 0
{ print("\(num) fizz") }
senão se num % 5 == 0 { print("\
(num) buzz") } senão
{ print(num)
}
}
Tão simples quanto isso, você pode usar qualquer idioma de sua escolha e começar
Aproveite a codificação
Uma maneira intuitiva de entender isso é que f(x) = ÿ(g(x)) significa que os gráficos de f(x) e g(x) crescem na mesma taxa, ou
que os gráficos 'se comportam' de forma semelhante para valores grandes o suficiente de x.
Um exemplo
Se o algoritmo para a entrada n leva 42n^2 + 25n + 4 operações para terminar, dizemos que é O(n^2), mas também é O(n^3)
e O(n^100). No entanto, é ÿ(n^2) e não é ÿ(n^3), ÿ(n^4) etc. Algoritmo que é ÿ(f(n)) também é O(f(n)), mas
não vice-versa!
ÿ(g(x)) = {f(x) tal que existem constantes positivas c1, c2, N tais que 0 <= c1*g(x) <= f(x)
<= c2*g(x) para todos os x > N}
Como ÿ(g(x)) é um conjunto, poderíamos escrever f(x) ÿ ÿ(g(x)) para indicar que f(x) é um membro de ÿ(g(x)). Em vez disso,
geralmente escreverá f(x) = ÿ(g(x)) para expressar a mesma noção - essa é a maneira comum.
Sempre que ÿ(g(x)) aparece em uma fórmula, nós o interpretamos como representando alguma função anônima que não conhecemos.
cuidado para nomear. Por exemplo, a equação T(n) = T(n/2) + ÿ(n), significa T(n) = T(n/2) + f(n) onde f(n) é um
função no conjunto ÿ(n).
Sejam f e g duas funções definidas em algum subconjunto dos números reais. Escrevemos f(x) = ÿ(g(x)) como
x->infinito se e somente se houver constantes positivas K e L e um número real x0 tal que seja válido:
A definição é igual a:
se limit(x->infinito) f(x)/g(x) = c ÿ (0,ÿ) ou seja, o limite existe e é positivo, então f(x) = ÿ(g(x))
Linear 10 100
Notação
f(n) = f(n) =
f(n) = O(g(n)) f(n) = ÿ(g(n)) f(n) = ÿ(g(n))
o(g(n)) ÿ(g(n))
ÿc>
ÿc> 0, ÿ
0, ÿ n0 >
n0 > 0 0:ÿ
Formal ÿ c1, c2 > 0, ÿ n0 > 0 : ÿ n ÿ n0, 0 ÿ c1 g(n) ÿ :ÿn nÿ
definição ÿ c > 0, ÿ n0 > 0 : ÿ n ÿ n0, 0 ÿ f(n) ÿ c g(n) ÿ c > 0, ÿ n0 > 0 : ÿ n ÿ n0, 0 ÿ c g(n) ÿ f(n)
f(n) ÿ c2 g(n) ÿ n0, n0, 0
0ÿ ÿc
f(n) < g(n)
c g(n) <
f(n)
Analogia
entre o
assintótico
comparação um ÿ b um ÿ b um = b um < ba > b
de f, g e
números reais
um, b
7n^2
5n^2 = =
Exemplo 7n + 10 = O(n^2 + n - 9) n^3 - 34 = ÿ(10n^2 - 7n + 1) 1/2 n^2 - 7n = ÿ(n^2)
o(n^3)
ÿ(n)
Gráfico
interpretação
Ligações
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introdução aos Algoritmos.
Definição formal
Sejam f(n) e g(n) duas funções definidas no conjunto dos números reais positivos. Escrevemos f(n) = ÿ(g(n)) se houver
constantes positivas c e n0 tais que:
Notas
f(n) = ÿ(g(n)) significa que f(n) cresce assintoticamente não mais devagar que g(n). Também podemos dizer sobre ÿ(g(n))
quando a análise do algoritmo não é suficiente para a declaração sobre ÿ(g(n)) ou / e O(g(n)).
Para duas funções quaisquer f(n) e g(n), temos f(n) = ÿ(g(n)) se e somente se f(n) = O(g(n)) e f(n) = ÿ(g(n)).
Por exemplo, vamos ter f(n) = 3n^2 + 5n - 4. Então f(n) = ÿ(n^2). Também é correto f(n) = ÿ(n), ou mesmo f(n) = ÿ(1).
Outro exemplo para resolver o algoritmo de correspondência perfeita: se o número de vértices for ímpar, a saída será "Sem correspondência
perfeita". Caso contrário, tente todas as correspondências possíveis.
Gostaríamos de dizer que o algoritmo requer tempo exponencial, mas na verdade você não pode provar um limite inferior
ÿ(n^2) usando a definição usual de ÿ, já que o algoritmo roda em tempo linear para n ímpares. Em vez disso,
deveríamos definir f(n)=ÿ(g(n)) dizendo para alguma constante c>0, f(n)ÿ c g(n) para infinitamente muitos n.
Isso dá uma boa correspondência entre limites superior e inferior: f(n)=ÿ(g(n)) iff f(n) != o(g(n)).
Referências
A definição formal e o teorema foram retirados do livro "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to
Algorithms".
A notação Big-O é, em sua essência, uma notação matemática usada para comparar a taxa de convergência de funções.
Sejam n -> f(n) e n -> g(n) funções definidas sobre os números naturais. Então dizemos que f = O(g) se e somente se f(n)/g(n) é
limitado quando n se aproxima do infinito. Em outras palavras, f = O(g) se e somente se existe uma constante A, tal que para todo
n, f(n)/g(n) <= A.
Na verdade, o escopo da notação Big-O é um pouco mais amplo em matemática, mas para simplificar, eu o reduzi ao que é usado na análise de
complexidade de algoritmos: funções definidas em naturais, que têm valores diferentes de zero, e o caso de n crescendo até o infinito.
Vamos pegar o caso de f(n) = 100n^2 + 10n + 1 e g(n) = n^2. É bem claro que ambas as funções tendem ao infinito assim como n
tende ao infinito. Mas às vezes saber o limite não é suficiente, e também queremos saber a velocidade na qual as funções se aproximam
de seu limite. Noções como Big-O ajudam a comparar e classificar funções por sua velocidade de
convergência.
Vamos descobrir se f = O(g) aplicando a definição. Temos f(n)/g(n) = 100 + 10/n + 1/n^2. Como 10/n é 10 quando n é 1 e está
diminuindo, e como 1/n^2 é 1 quando n é 1 e também está diminuindo, temos ÿf(n)/g(n) <= 100 + 10 + 1 = 111. A definição é satisfeita
porque encontramos um limite de f(n)/g(n) (111) e então f = O(g) (dizemos que f é um Big-O de n^2).
Isso significa que f tende ao infinito aproximadamente na mesma velocidade que g. Agora, isso pode parecer uma coisa estranha de se dizer,
porque o que descobrimos é que f é no máximo 111 vezes maior que g, ou em outras palavras, quando g cresce em 1, f cresce no máximo 111.
Pode parecer que crescer 111 vezes mais rápido não é "aproximadamente a mesma velocidade". E, de fato, a notação Big-O não é uma
maneira muito precisa de classificar a velocidade de convergência de funções, e é por isso que em matemática usamos a relação de
equivalência quando queremos uma estimativa precisa de velocidade. Mas para os propósitos de separar algoritmos em grandes
classes de velocidade, Big-O é o suficiente. Não precisamos separar funções que crescem um número fixo de vezes mais rápido que umas das
outras, mas apenas funções que crescem infinitamente mais rápido que umas das outras.
Por exemplo, se tomarmos h(n) = n^2*log(n), vemos que h(n)/g(n) = log(n), que tende ao infinito com n, então h não é O(n^2), porque h cresce
infinitamente mais rápido que n^2.
Agora preciso fazer uma observação lateral: você deve ter notado que se f = O(g) e g = O(h), então f = O(h). Por exemplo, em
nosso caso, temos f = O(n^3), e f = O(n^4)... Na análise de complexidade de algoritmos, frequentemente dizemos f = O(g) para significar
que f = O(g) e g = O(f), o que pode ser entendido como "g é o menor Big-O para f". Em matemática, dizemos que tais
funções são Big-Thetas umas das outras.
Como é usado?
Ao comparar o desempenho do algoritmo, estamos interessados no número de operações que um algoritmo realiza. Isso é chamado de
complexidade de tempo. Neste modelo, consideramos que cada operação básica (adição, multiplicação, comparação, atribuição,
etc.) leva um tempo fixo, e contamos o número dessas operações. Normalmente podemos expressar esse número como uma função do
tamanho da entrada, que chamamos de n. E, infelizmente, esse número geralmente cresce até o infinito com n (se não crescer, dizemos que
o algoritmo é O(1)). Separamos nossos algoritmos em grandes classes de velocidade definidas por Big-O: quando falamos sobre um
"algoritmo O(n^2)", queremos dizer que o número de operações que ele realiza, expresso como uma função de n, é um O(n^2). Isso diz que
nosso algoritmo é aproximadamente tão rápido quanto um algoritmo que faria um número de operações igual ao quadrado do tamanho
de sua entrada, ou mais rápido. A parte "ou mais rápido" está lá porque usei Big-O em vez de Big-Theta, mas normalmente as pessoas dizem
Big-O para significar Big-Theta.
Ao contar operações, geralmente consideramos o pior caso: por exemplo, se temos um loop que pode ser executado no máximo n vezes
e que contém 5 operações, o número de operações que contamos é 5n. Também é possível considerar a complexidade média do
caso.
Nota rápida: um algoritmo rápido é aquele que executa poucas operações, então se o número de operações cresce até o infinito mais
rápido, então o algoritmo é mais lento: O(n) é melhor que O(n^2).
Às vezes também estamos interessados na complexidade de espaço do nosso algoritmo. Para isso, consideramos o número de
bytes na memória ocupados pelo algoritmo como uma função do tamanho da entrada, e usamos Big-O da mesma forma.
} retornar máximo;
}
Essas duas atribuições são feitas apenas uma vez, então são 2 operações. As operações que são colocadas em loop são:
máximo = array[i]
Como há 3 operações no loop, e o loop é feito n vezes, adicionamos 3n às nossas 2 operações já existentes para obter 3n + 2.
Então nossa função leva 3n + 2 operações para encontrar o máximo (sua complexidade é 3n + 2). Este é um polinômio onde o termo de
crescimento mais rápido é um fator de n, então é O(n).
Você provavelmente notou que "operação" não é muito bem definida. Por exemplo, eu disse que if (max < array[i]) era uma operação, mas
dependendo da arquitetura esta declaração pode compilar para, por exemplo, três instruções: uma leitura de memória, uma comparação e
uma ramificação. Eu também considerei todas as operações como as mesmas, embora, por exemplo, as operações de memória
sejam mais lentas do que as outras, e seu desempenho varie muito devido, por exemplo, aos efeitos de cache. Eu também ignorei
completamente a declaração return, o fato de que um quadro será criado para a função, etc. No final, não importa para a análise de
complexidade, porque qualquer maneira que eu escolher para contar as operações, isso mudará apenas o coeficiente do fator n e a
constante, então o resultado ainda será O(n).
A complexidade mostra como o algoritmo é dimensionado com o tamanho da entrada, mas não é o único aspecto do desempenho!
}
}
} retornar 0;
}
O loop interno realiza em cada iteração um número de operações que é constante com n. O loop externo também realiza algumas operações
constantes e executa o loop interno n vezes. O loop externo em si é executado n vezes. Então as operações dentro do loop interno são
executadas n^2 vezes, as operações no loop externo são executadas n vezes e a atribuição a i é feita uma vez. Assim, a complexidade será
algo como an^2 + bn + c, e como o termo mais alto é n^2, a notação O é O(n^2).
Como você deve ter notado, podemos melhorar o algoritmo evitando fazer as mesmas comparações várias vezes.
Podemos começar com i + 1 no loop interno, porque todos os elementos anteriores a ele já terão sido verificados em relação a todos
os elementos do array, incluindo aquele no índice i + 1. Isso nos permite descartar a verificação i == j .
}
}
} retornar 0;
}
Obviamente, esta segunda versão faz menos operações e, portanto, é mais eficiente. Como isso se traduz na notação Big-O? Bem,
...
agora o corpo do loop interno é executado 1 + 2 + + n - 1 = n(n-1)/2 vezes. Este ainda é um polinômio de segundo grau e, portanto, ainda é
apenas O(n^2). Nós claramente diminuímos a complexidade, já que dividimos aproximadamente por 2 o número de operações que estamos
fazendo, mas ainda estamos na mesma classe de complexidade definida pelo Big-O. Para diminuir a complexidade para uma classe menor,
precisaríamos dividir o número de operações por algo que tende ao infinito com n.
Problema de Etapa
1 n/2
2 n/4
3 n/8
4 n/16
Quando o espaço do problema é reduzido (ou seja, resolvido completamente), ele não pode ser reduzido mais (n se torna igual a 1)
após sair da condição de verificação.
tamanho do problema = 1
3. De 1 e 2:
n/2k = 1 ou
n = 2k
logaritmo n = k logaritmo2
ou
k = logaritmo n / logaritmo 2
k = log2 n
ou simplesmente k = log n
Agora sabemos que nosso algoritmo pode ser executado no máximo até log n, portanto a complexidade de tempo surge como
O(log n)
Então, agora, se alguém lhe perguntar se n é 256, quantas etapas esse loop (ou qualquer outro algoritmo que reduza o tamanho do problema pela metade)
k = log2 256
k=8
enquanto(baixo<=alto)
{ médio=baixo+(alto-baixo)/
2; se(arr[médio]==item)
retornar
médio; senão
se(arr[médio]<item)
baixo=médio+1; senão alto=médio-1; }
return –1;// Resultado sem sucesso
}
L é uma lista ordenada contendo n inteiros assinados ( sendo n grande o suficiente), por exemplo [-5, -2, -1, 0, 1, 2, 4] (aqui, n
tem um valor de 7). Se L é conhecido por conter o inteiro 0, como você pode encontrar o índice de 0?
Abordagem ingênua
A primeira coisa que vem à mente é apenas ler cada índice até que 0 seja encontrado. No pior caso, o número de
operações é n, então a complexidade é O(n).
Isso funciona bem para valores pequenos de n, mas existe uma maneira mais eficiente?
Dicotomia
a=0
b = n-1
enquanto Verdadeiro:
a e b são os índices entre os quais 0 deve ser encontrado. Cada vez que entramos no loop, usamos um índice entre a
e b e usá-lo para restringir a área a ser pesquisada.
No pior caso, temos que esperar até que a e b sejam iguais. Mas quantas operações isso leva? Não n, porque
cada vez que entramos no loop, dividimos a distância entre a e b por cerca de dois. Em vez disso, a complexidade é O(log
e).
Explicação
Nota: Quando escrevemos "log", queremos dizer o logaritmo binário, ou log base 2 (que escreveremos "log_2"). Como O(log_2 n) = O(log
n) (você pode fazer as contas) usaremos "log" em vez de "log_2".
Conclusão
Ao se deparar com divisões sucessivas (seja por dois ou por qualquer número), lembre-se de que a complexidade é logarítmica.
Capítulo 4: Árvores
Então iteramos sobre os irmãos e recursivamente descemos pelos filhos. Como a maioria das árvores é relativamente rasa - muitos
filhos, mas apenas alguns níveis de hierarquia, isso dá origem a um código eficiente. Observe que as genealogias humanas são
uma exceção (muitos níveis de ancestrais, apenas alguns filhos por nível).
Se necessário, ponteiros de volta podem ser mantidos para permitir que a árvore seja escalada. Esses são mais difíceis de manter.
Observe que é comum ter uma função para chamar na raiz e uma função recursiva com parâmetros extras, neste caso, profundidade da
árvore.
estrutura nó {
int eu;
enquanto(nó)
{
se(nó->filho) {
para(i=0;i<profundidade*3;i++)
printf(" ");
printf("{\n"):
printtree_r(nó->filho, profundidade +1);
para(i=0;i<profundidade*3;i++)
printf(" "); printf("{\n"):
para(i=0;i<profundidade*3;i++)
printf(" ");
printf("%s\n", nó->data.c_str());
nó = nó->próximo;
}
}
}
printree_r(raiz, 0);
}
A estrutura de dados em árvore é bem comum na ciência da computação. Árvores são usadas para modelar muitas estruturas de dados algorítmicas diferentes, como
árvores binárias comuns, árvores rubro-negras, árvores B, árvores AB, árvores 23, Heap e tries.
Seção 4.3: Para verificar se duas árvores binárias são iguais ou não
1. Por exemplo, se as entradas forem:
Exemplo:1
um)
b)
Exemplo:2
Se as entradas forem:
um)
b)
Após o trecho de código, cada imagem mostra a visualização da execução, o que facilita a visualização de como esse código funciona.
classe Nó:
def __init__(self, val): self.l_child =
Nenhum self.r_child = Nenhum
[Link] = val
raiz.r_child = nó
outro:
inserir(root.r_child, nó)
retornar
retornar
impressão [Link]
pre_order_print(root.l_child) pre_order_print(root.r_child)
Antes de começar com a exclusão, eu só quero colocar algumas luzes sobre o que é uma árvore de busca binária (BST). Cada nó em
uma BST pode ter no máximo dois nós (filho esquerdo e direito). A subárvore esquerda de um nó tem uma chave menor ou igual à
chave do nó pai. A subárvore direita de um nó tem uma chave maior que a chave do nó pai.
1. Quando o nó a ser excluído for um nó folha, basta excluir o nó e passar nullptr para seu nó pai.
2. Quando um nó a ser excluído tiver apenas um filho, copie o valor do filho para o valor do nó e exclua o filho (convertido para
o caso 1)
3. Quando um nó a ser excluído tem dois filhos, o mínimo de sua subárvore direita pode ser copiado para o nó e, em seguida, o
valor mínimo pode ser excluído da subárvore direita do nó (convertido para o caso 2)
Observação: o mínimo na subárvore direita pode ter no máximo um filho, e o filho direito, se tiver o filho esquerdo, significa que não é
o valor mínimo ou não segue a propriedade BST.
estrutura nó {
int dados; nó
*esquerda, *direita;
};
outro
{
if(root->left == nullptr && root->right == nullptr) // Caso 1 {
livre(raiz); raiz =
nullptr;
} // Caso 3
outro {
nó* temp = raiz->direita;
} retornar raiz;
}
Considere o BST:
A propriedade da árvore de pesquisa binária pode ser usada para encontrar nós ancestrais mais baixos
Pseudocódigo:
lowerCommonAncestor(raiz,nó1, nó2){
se(raiz == NULL)
retornar NULL;
retornar raiz;
}
senão
{ return lowestCommonAncestor(raiz->direita, nó1, nó2);
}
}
classe BinarySearchTree(objeto):
def insert(self, raiz, nó):
[Link](root.l_child, nó)
retornar raiz
retornar Nenhum
outro:
self.in_order_place(root.l_child) imprimir [Link]
self.in_order_place(root.r_child)
imprimir [Link]
self.pre_order_place(root.l_child)
self.pre_order_place(root.r_child)
retornar Nenhum
outro:
self.post_order_place(root.l_child)
self.post_order_place(root.r_child) imprimir [Link]
r = Nó(3) nó =
BinarySearchTree() lista de nós = [1, 8,
5, 12, 14, 6, 15, 7, 16, 8]
para nd em nodeList:
nó.inserir(r, Nó(nd))
Seção 6.1: Algoritmo para verificar se uma determinada árvore binária é BST
Uma árvore binária é BST se satisfaz qualquer uma das seguintes condições:
1. Está vazio 2.
Não tem subárvores
3. Para cada nó x na árvore, todas as chaves (se houver) na subárvore esquerda devem ser menores que a chave(x) e todas as chaves
(se houver) na subárvore direita devem ser maiores que a chave(x).
is_BST(raiz): se raiz
== NULL:
retornar verdadeiro
O algoritmo recursivo acima está correto, mas é ineficiente, porque percorre cada nó várias vezes.
Outra abordagem para minimizar as múltiplas visitas de cada nó é lembrar os valores mínimos e máximos possíveis das chaves na subárvore
que estamos visitando. Seja o valor mínimo possível de qualquer chave K_MIN e o valor máximo K_MAX. Quando começamos da raiz da
árvore, o intervalo de valores na árvore é [K_MIN,K_MAX]. Seja a chave do nó raiz x. Então o intervalo de valores na subárvore esquerda é
[K_MIN,x) e o intervalo de valores na subárvore direita é (x,K_MAX]. Usaremos essa ideia para desenvolver um algoritmo mais
eficiente.
is_BST(minha_raiz_da_árvore,CHAVE_MIN,CHAVE_MAX)
Outra abordagem será fazer a travessia inorder da árvore binária. Se a travessia inorder produzir uma sequência ordenada de chaves,
então a árvore dada é uma BST. Para verificar se a sequência inorder está ordenada, lembre-se do valor de
Por exemplo
se a entrada for:
Se a entrada for:
1234567
Código:
#incluir<iostream>
#incluir<fila>
#incluir<malloc.h>
estrutura nó{
int dados;
nó *esquerda;
nó *direita;
};
fila<nó *> Q;
[Link](raiz);
enquanto(![Link]()){
estrutura nó* curr = [Link](); cout<<
curr->data <<" "; if(curr->left !=
NULL) [Link](curr-> left);
se(atual->direita != NULL) [Link](atual-> direita);
[Link]();
retornar(nó);
}
int principal(){
retornar 0;
A travessia de pré-ordem (raiz) consiste em percorrer o nó, depois a subárvore esquerda do nó e depois a subárvore direita do nó.
1245367
A travessia em ordem (raiz) consiste em percorrer a subárvore esquerda do nó, depois o nó e depois a subárvore direita do nó.
nó.
4251637
A travessia pós-ordem (raiz) consiste em percorrer a subárvore esquerda do nó, depois a subárvore direita e, por fim, o nó.
4526731
Capítulo 9: Gráfico
Um gráfico é uma coleção de pontos e linhas conectando algum subconjunto (possivelmente vazio) deles. Os pontos de um gráfico são
chamados de vértices do gráfico, "nós" ou simplesmente "pontos". Similarmente, as linhas conectando os vértices de um gráfico são chamadas
de arestas do gráfico, "arcos" ou "linhas".
Um grafo G pode ser definido como um par (V,E), onde V é um conjunto de vértices e E é um conjunto de arestas entre os vértices E ÿ {(u,v) |
u, v ÿ V}.
Matriz de Adjacência
Lista de Adjacências
Uma matriz de adjacência é uma matriz quadrada usada para representar um grafo finito. Os elementos da matriz indicam se pares
de vértices são adjacentes ou não no grafo.
Adjacente significa 'próximo ou adjacente a outra coisa' ou estar ao lado de algo. Por exemplo, seus vizinhos são adjacentes a você. Na
teoria dos grafos, se pudermos ir do nó A para o nó B, podemos dizer que o nó B é adjacente ao nó A. Agora aprenderemos como
armazenar quais nós são adjacentes a qual via Matriz de Adjacência. Isso significa que representaremos quais nós compartilham arestas
entre eles. Aqui, matriz significa matriz 2D.
Aqui você pode ver uma tabela ao lado do gráfico, esta é nossa matriz de adjacência. Aqui Matrix[i][j] = 1 representa que há uma aresta
entre i e j. Se não houver aresta, simplesmente colocamos Matrix[i][j] = 0.
Essas arestas podem ser ponderadas, como se pudessem representar a distância entre duas cidades. Então colocaremos o valor em
Matrix[i][j] em vez de colocar 1.
O gráfico descrito acima é Bidirecional ou Não Direcionado, ou seja, se podemos ir do nó 2 para o nó 1, também podemos ir do nó 1 para
o nó 2. Se o gráfico fosse Direcionado, então haveria um sinal de seta em um lado do gráfico. Mesmo assim, poderíamos representá-lo
usando matriz de adjacência.
Representamos os nós que não compartilham aresta por infinito. Uma coisa a ser notada é que, se o gráfico for não direcionado, a matriz se torna
simétrica.
Memória é um problema enorme. Não importa quantas arestas existam, sempre precisaremos de uma matriz de tamanho N * N, onde N é o
número de nós. Se houver 10000 nós, o tamanho da matriz será 4 * 10000 * 10000, cerca de 381 megabytes.
Isso é um enorme desperdício de memória se considerarmos gráficos que têm poucas arestas.
Suponha que queremos descobrir para qual nó podemos ir de um nó u. Precisaremos verificar toda a linha de u, o que leva muito tempo.
O único benefício é que podemos encontrar facilmente a conexão entre os nós UV e seus custos usando a Matriz de Adjacência.
importar [Link];
público Representar_Grafo_Matriz_de_Adjacência(int v) {
vértices = v;
matriz_de_adjacência = novo int[vértices + 1][vértices + 1];
}
tentar
adjacency_matrix[para][de] = aresta;
tentar
retornar adjacency_matrix[para][de];
} retornar -1;
}
para = [Link](); de =
[Link]();
[Link]("A matriz de adjacência para o grafo dado é: "); [Link](" "); for (int i = 1; i <=
v; i++)
} catch (Exceção E) {
[Link]();
}
}
Exemplo:
$ java Representar_Grafo_Matriz_de_Adjacência
Insira o número de vértices:
4
Digite o número de arestas: 6
Insira as arestas: 1
13
42
31
42
41
2
A matriz de adjacência para o gráfico dado é: 1 2 3 4 1 1 1 0 1 2 0 0 1 1
30001
40000
Você sabia que quase todos os problemas do planeta Terra podem ser convertidos em problemas de Estradas e Cidades, e
resolvidos? A Teoria dos Grafos foi inventada há muitos anos, antes mesmo da invenção do computador. Leonhard Euler escreveu
um artigo sobre as Sete Pontes de Königsberg que é considerado o primeiro artigo da Teoria dos Grafos. Desde então, as
pessoas perceberam que se pudermos converter qualquer problema para este problema Cidade-Estrada, podemos resolvê-lo
facilmente pela Teoria dos Grafos.
A Teoria dos Grafos tem muitas aplicações. Uma das aplicações mais comuns é encontrar a menor distância entre uma cidade e
outra. Todos nós sabemos que para chegar ao seu PC, esta página da web teve que viajar por muitos roteadores do servidor.
A Teoria dos Grafos ajuda a descobrir os roteadores que precisam ser cruzados. Durante a guerra, qual rua precisa ser
bombardeada para desconectar a capital das outras, isso também pode ser descoberto usando a Teoria dos Grafos.
Vamos primeiro aprender algumas definições básicas sobre Teoria dos Grafos.
Gráfico:
Digamos que temos 6 cidades. Nós as marcamos como 1, 2, 3, 4, 5, 6. Agora conectamos as cidades que têm estradas entre si.
Este é um gráfico simples onde algumas cidades são mostradas com as estradas que as conectam. Na Teoria dos Grafos, chamamos cada uma dessas
cidades de Nó ou Vértice e as estradas são chamadas de Aresta. O gráfico é simplesmente uma conexão desses nós e arestas.
Um nó pode representar muitas coisas. Em alguns gráficos, nós representam cidades, alguns representam aeroportos, alguns representam um
quadrado em um tabuleiro de xadrez. A aresta representa a relação entre cada nó. Essa relação pode ser o tempo para ir de um aeroporto para outro, os
Em palavras simples, um Nó representa qualquer objeto e uma Aresta representa a relação entre dois objetos.
Nó adjacente:
Se um nó A compartilha uma aresta com o nó B, então B é considerado adjacente a A. Em outras palavras, se dois nós estão
diretamente conectados, eles são chamados de nós adjacentes. Um nó pode ter vários nós adjacentes.
Em grafos direcionados, as arestas têm sinais de direção em um lado, o que significa que as arestas são unidirecionais. Por
outro lado, as arestas de grafos não direcionados têm sinais de direção em ambos os lados, o que significa que são bidirecionais.
Normalmente, gráficos não direcionados são representados sem sinais em ambos os lados das arestas.
Vamos supor que haja uma festa acontecendo. As pessoas na festa são representadas por nós e há uma aresta entre duas
pessoas se elas apertam as mãos. Então este gráfico é não direcionado porque qualquer pessoa A aperta a mão da pessoa B se
e somente se B também aperta a mão de A. Em contraste, se as arestas de uma pessoa A para outra pessoa B correspondem à
admiração de A por B, então este gráfico é direcionado, porque a admiração não é necessariamente recíproca. O primeiro tipo de
gráfico é chamado de gráfico não direcionado e as arestas são chamadas de arestas não direcionadas , enquanto o último tipo de
gráfico é chamado de gráfico direcionado e as arestas são chamadas de arestas direcionadas.
Um grafo ponderado é um grafo no qual um número (o peso) é atribuído a cada aresta. Tais pesos podem representar, por exemplo,
custos, comprimentos ou capacidades, dependendo do problema em questão.
Um gráfico não ponderado é simplesmente o oposto. Assumimos que o peso de todas as arestas é o mesmo (presumivelmente 1).
Caminho:
Um caminho representa uma maneira de ir de um nó para outro. Ele consiste em uma sequência de arestas. Pode haver vários
No exemplo acima, há dois caminhos de A para D. A->B, B->C, C->D é um caminho. O custo desse caminho é 3 + 4 + 2 = 9. Novamente,
há outro caminho A->D. O custo desse caminho é 10. O caminho que custa menos é chamado de caminho mais curto.
Grau:
O grau de um vértice é o número de arestas que estão conectadas a ele. Se houver alguma aresta que se conecte ao vértice em
ambas as extremidades (um loop) é contado duas vezes.
Algoritmo Bellman–Ford
Algoritmo de Dijkstra
Algoritmo Ford–Fulkerson
Algoritmo de Kruskal
Algoritmo do vizinho mais próximo
Algoritmo de Prim
Busca em profundidade
Busca em largura
Isso é chamado de lista de adjacência. Ela mostra quais nós estão conectados a quais nós. Podemos armazenar essas informações
usando uma matriz 2D. Mas vai nos custar a mesma memória que a Matriz de Adjacência. Em vez disso, vamos usar memória
alocada dinamicamente para armazenar esta.
Muitas linguagens suportam Vector ou List , que podemos usar para armazenar listas de adjacência. Para estas, não precisamos
especificar o tamanho da List. Precisamos apenas especificar o número máximo de nós.
O pseudocódigo será:
Como este é um gráfico não direcionado, se há uma aresta de x para y, também há uma aresta de y para x. Se fosse um gráfico
direcionado, omitiríamos o segundo. Para gráficos ponderados, precisamos armazenar o custo também. Criaremos outro vetor ou lista
chamada cost[] para armazená-los. O pseudocódigo:
entrada -> x, y, w
edge[x].push(y)
cost[x].push(w) fim para
Retornar
aresta, custo
A partir daí, podemos descobrir facilmente o número total de nós conectados a qualquer nó e quais são esses nós.
Leva menos tempo do que a Matriz de Adjacência. Mas se precisássemos descobrir se há uma aresta entre u e v, seria mais fácil se mantivéssemos
uma matriz de adjacência.
Formalmente, em um gráfico G = (V, E), então uma ordenação linear de todos os seus vértices é tal que se G contém uma aresta
(u, v) ÿ E do vértice u ao vértice v então u precede v na ordenação.
É importante observar que cada DAG tem pelo menos uma classificação topológica.
Existem algoritmos conhecidos para construir uma ordenação topológica de qualquer DAG em tempo linear, um exemplo é:
1. Chame depth_first_search(G) para calcular os tempos de conclusão vf para cada vértice v 2. À medida
que cada vértice é concluído, insira-o na frente de uma lista encadeada 3. a lista
encadeada de vértices, como está agora classificada.
Uma classificação topológica pode ser realizada em (V + E) de tempo, já que o algoritmo de busca em profundidade leva (V + E) de
tempo e leva ÿ(1) (tempo constante) para inserir cada um dos vértices |V| na frente de uma lista encadeada.
Muitas aplicações usam grafos acíclicos direcionados para indicar precedências entre eventos. Usamos ordenação topológica para obter uma ordenação
para processar cada vértice antes de qualquer um de seus sucessores.
Os vértices em um gráfico podem representar tarefas a serem executadas e as arestas podem representar restrições de que uma tarefa deve ser
executada antes de outra; uma ordenação topológica é uma sequência válida para executar o conjunto de tarefas descrito em V.
Deixe um vértice v descrever uma Tarefa(horas_para_concluir: int), ou seja , Tarefa(4) descreve uma Tarefa que leva 4 horas para ser
concluída, e uma aresta e descreve um Tempo de Resfriamento(horas: int) tal que Tempo de Resfriamento(3) descreve uma duração de
tempo para esfriar após uma tarefa concluída.
Seja nosso grafo chamado dag (já que é um grafo acíclico direcionado) e contenha 5 vértices:
onde conectamos os vértices com arestas direcionadas de modo que o grafo seja acíclico,
// A ---> C ----+
// | // | |
v // B você você
Um ciclo em um grafo direcionado existe se houver uma aresta posterior descoberta durante um DFS. Uma aresta posterior é uma aresta de um
nó para si mesmo ou um dos ancestrais em uma árvore DFS. Para um grafo desconectado, obtemos uma floresta DFS, então você tem que
iterar por todos os vértices no grafo para encontrar árvores DFS disjuntas.
Implementação C++:
#incluir <iostream>
#incluir <lista>
#define NUM_V 4
visitou[u]=true;
recStack[u]=true;
lista<int>::iterador i; para(i =
gráfico[u].begin();i!=gráfico[u].end();++i) {
if(recStack[*i]) //se o vértice v for encontrado na pilha de recursão desta travessia DFS
retornar
verdadeiro; senão if(*i==u) //se houver uma aresta do vértice para ele mesmo retornar
verdadeiro; senão
if(!visited[*i]) { if(helper(graph, *i,
visited, recStack))
retornar verdadeiro;
}
} recStack[u]=falso; retornar
falso;
}/
* / A função wrapper chama a função auxiliar em cada vértice que não foi visitado. Auxiliar
a função retorna verdadeiro se detectar uma aresta posterior no subgrafo (árvore) ou falso. */
bool visited[V]; //matriz para rastrear vértices já visitados bool recStack[V]; //matriz para
rastrear vértices na pilha de recursão da travessia.
for(int u = 0; u < V; u++) //Verifica iterativamente se todos os vértices foram visitados { if(visited[u]==false) { if(helper(graph, u,
visited, recStack)) //verifica se a árvore
DFS do vértice
contém um ciclo
retornar verdadeiro;
} retornar falso;
} /*
Função do motorista
*/
int principal() {
Resultado: Conforme mostrado abaixo, há três arestas traseiras no gráfico. Uma entre o vértice 0 e 2; entre o vértice 0, 1 e 2; e o vértice 3. A
complexidade de tempo da busca é O(V+E), onde V é o número de vértices e E é o número de arestas.
As ideias básicas são as seguintes. (Desculpe, ainda não tentei implementar, então posso perder alguns detalhes menores. E o artigo original
é pago, então tentei reconstruí-lo a partir de outras fontes que o referenciam. Por favor, remova este comentário se puder verificar.)
Existem maneiras de encontrar a árvore de abrangência em O(m) (não descritas aqui). Você precisa "crescer" a árvore de abrangência
da aresta mais curta para a mais longa, e seria uma floresta com vários componentes conectados antes
totalmente crescido.
Selecione um inteiro b (b>=2) e considere apenas as florestas de abrangência com limite de comprimento b^k.
Mescle os componentes que são exatamente os mesmos, mas com k diferente, e chame o k mínimo de nível do
componente. Então, logicamente, faça os componentes em uma árvore. u é o pai de v iff u é o menor componente distinto
de v que contém v completamente. A raiz é o gráfico inteiro e as folhas são vértices únicos no gráfico original (com o
nível de infinito negativo). A árvore ainda tem apenas O(n) nós.
Mantenha a distância de cada componente para a fonte (como no algoritmo de Dijkstra). A distância de um
componente com mais de um vértice é a distância mínima de seus filhos não expandidos. Defina a distância do
vértice de origem para 0 e atualize os ancestrais de acordo.
Considere as distâncias na base b. Ao visitar um nó no nível k pela primeira vez, coloque seus filhos em buckets
compartilhados por todos os nós do nível k (como em bucket sort, substituindo o heap no algoritmo de Dijkstra) pelo dígito
k e maior de sua distância. Cada vez que visitar um nó, considere apenas seus primeiros b buckets, visite e remova
cada um deles, atualize a distância do nó atual e revincule o nó atual ao seu próprio pai usando a nova distância e aguarde
a próxima visita para os buckets seguintes.
Quando uma folha é visitada, a distância atual é a distância final do vértice. Expanda todas as arestas dela no gráfico
original e atualize as distâncias de acordo.
Visite o nó raiz (gráfico inteiro) repetidamente até que o destino seja alcançado.
Baseia-se no fato de que não há uma aresta com comprimento menor que l entre dois componentes conectados da floresta de
abrangência com limitação de comprimento l, então, começando na distância x, você pode focar apenas em um
componente conectado até atingir a distância x + l. Você visitará alguns vértices antes que os vértices com distância menor sejam
todos visitados, mas isso não importa porque é sabido que não haverá um caminho mais curto para cá a partir desses vértices. Outras
partes funcionam como a ordenação por balde / ordenação por radix MSD e, claro, requer a árvore de abrangência O(m).
retornar;
// definido como visitado para evitar visitar o mesmo nó duas vezes (*visited)
[node] = true;
Algoritmo de Dijkstra é conhecido como algoritmo de caminho mais curto de fonte única. É usado para encontrar os caminhos mais curtos
entre nós em um gráfico, que pode representar, por exemplo, redes rodoviárias. Foi concebido por Edsger W.
Dijkstra em 1956 e publicado três anos depois.
Podemos encontrar o caminho mais curto usando o algoritmo de busca Breadth First Search (BFS). Esse algoritmo funciona bem, mas o
problema é que ele assume que o custo de percorrer cada caminho é o mesmo, o que significa que o custo de cada aresta é o mesmo. O
algoritmo de Dijkstra nos ajuda a encontrar o caminho mais curto onde o custo de cada caminho não é o mesmo.
Primeiro, veremos como modificar o BFS para escrever o algoritmo de Dijkstra e, depois, adicionaremos uma fila de prioridades para torná-
lo um algoritmo de Dijkstra completo.
Digamos que a distância de cada nó da fonte é mantida no array d[] . Como em, d[3] representa que d[3] tempo é levado para alcançar o nó 3
da fonte. Se não soubermos a distância, armazenaremos infinito em d[3]. Além disso, deixe cost[u][v] representar o custo de uv.
Isso significa que leva cost[u][v] para ir do nó u para o nó v .
Precisamos entender o Relaxamento de Borda. Digamos que, da sua casa, que é a fonte, leva 10 minutos para ir ao local A. E leva 25
minutos para ir ao local B. Temos,
d[A] = 10
d[B] = 25
Agora digamos que leva 7 minutos para ir do ponto A ao ponto B, isso significa:
custo[A][B] = 7
Então podemos ir para o lugar B da fonte indo para o lugar A da fonte e então do lugar A, indo para o lugar B, o que levará 10 + 7 = 17
minutos, em vez de 25 minutos. Então,
Então atualizamos,
Isso é chamado de relaxamento. Iremos do nó u para o nó v e se d[u] + cost[u][v] < d[v] então atualizaremos d[v] = d[u] + cost[u][v].
No BFS, não precisamos visitar nenhum nó duas vezes. Só verificamos se um nó é visitado ou não. Se não foi visitado, colocamos o nó na
fila, marcamos como visitado e incrementamos a distância em 1. No Dijkstra, podemos empurrar um nó
na fila e em vez de atualizá-lo com o visitado, relaxamos ou atualizamos a nova aresta. Vejamos um exemplo:
d[1] = 0 d[2]
= d[3] = d[4] = infinito (ou um valor grande)
Definimos d[2], d[3] e d[4] para infinito porque ainda não sabemos a distância. E a distância da fonte é, claro , 0. Agora, vamos para outros nós da
Digamos, por exemplo, que atravessaremos a aresta 1-2. Como d[1] + 2 < d[2], o que fará com que d[2] = 2. Da mesma forma, atravessaremos a aresta
1-3 , o que fará com que d[3] = 5.
Podemos ver claramente que 5 não é a menor distância que podemos cruzar para ir ao nó 3. Então, atravessar um nó apenas uma vez, como BFS, não
funciona aqui. Se formos do nó 2 ao nó 3 usando a aresta 2-3, podemos atualizar d[3] = d[2] + 1 = 3. Então podemos ver que um nó pode ser atualizado
muitas vezes. Quantas vezes você pergunta? O número máximo de vezes que um nó pode ser atualizado é o número de graus de entrada de um nó.
Vamos ver o pseudocódigo para visitar qualquer nó várias vezes. Simplesmente modificaremos o BFS:
fim enquanto
Distância de retorno
Isso pode ser usado para encontrar o caminho mais curto de todos os nós da fonte. A complexidade desse código não é tão boa.
Aqui está o porquê,
No BFS, quando vamos do nó 1 para todos os outros nós, seguimos o método primeiro a chegar, primeiro a ser atendido . Por exemplo, fomos para o nó
3 da fonte antes de processar o nó 2. Se formos para o nó 3 da fonte, atualizamos o nó 4 como 5 + 3 = 8.
Quando atualizamos novamente o nó 3 do nó 2, precisamos atualizar o nó 4 como 3 + 3 = 6 novamente! Então o nó 4 é atualizado
duas vezes.
Dijkstra propôs, em vez de ir para o método Primeiro a chegar, primeiro a ser atendido , se atualizarmos os nós mais próximos primeiro, então serão
necessárias menos atualizações. Se processássemos o nó 2 antes, então o nó 3 teria sido atualizado antes, e depois de atualizar o nó 4
adequadamente, obteríamos facilmente a distância mais curta! A ideia é escolher da fila, o nó, que está mais próximo da fonte. Então usaremos a Fila de
Prioridade aqui para que, quando estourarmos a fila, ela nos traga o nó mais próximo u da fonte. Como ela fará isso? Ela verificará o valor de d[u] com
ela.
[Link](v) fim
se fim
para fim
enquanto
Distância de retorno
O pseudocódigo retorna a distância de todos os outros nós da fonte. Se quisermos saber a distância de um único nó v, podemos simplesmente retornar o
valor quando v for retirado da fila.
Agora, o Algoritmo de Dijkstra funciona quando há uma borda negativa? Se houver um ciclo negativo, então o loop infinito ocorrerá, pois continuará
reduzindo o custo a cada vez. Mesmo se houver uma borda negativa, Dijkstra não funcionará, a menos que retornemos logo após o alvo ser estourado.
Mas então, não será um algoritmo de Dijkstra. Precisaremos do algoritmo Bellman–Ford para processar a borda/ciclo negativo.
Complexidade:
A complexidade do BFS é O(log(V+E)) onde V é o número de nós e E é o número de arestas. Para Dijkstra, a complexidade é similar, mas a ordenação
da Priority Queue leva O(logV). Então a complexidade total é: O(Vlog(V)+E)
Abaixo está um exemplo Java para resolver o Algoritmo do Caminho Mais Curto de Dijkstra usando Matriz de Adjacência
classe ShortestPath {
min = dist[v];
índice_min = v;
}
retornar min_index;
}
dist[fonte] = 0;
sptSet[u] = verdadeiro;
imprimirSolução(dist, V);
}
[Link](gráfico, 0);
}
}
A* (A estrela) é um algoritmo de busca que é usado para encontrar o caminho de um nó para outro. Então ele pode ser comparado com
Breadth First Search, ou algoritmo de Dijkstra, ou Depth First Search, ou Best First Search. O algoritmo A* é amplamente utilizado
na busca por gráficos para melhorar a eficiência e a precisão, onde o pré-processamento de gráficos não é uma opção.
A* é uma especialização de Best First Search , em que a função de avaliação f é definida de uma maneira particular.
f(n) = g(n) + h(n) é o custo mínimo desde o nó inicial até os objetivos condicionados a passar pelo nó n.
A* é um algoritmo de busca informado e sempre garante encontrar o menor caminho (caminho com custo mínimo) em
o menor tempo possível (se usar heurística admissível). Então é completo e ótimo. A animação a seguir
demonstra pesquisa A*-
Vamos supor que este seja um labirinto. Não há paredes/obstáculos, no entanto. Temos apenas um ponto de partida (o
quadrado verde) e um ponto final (o quadrado vermelho). Vamos também supor que, para ir do verde ao vermelho, não podemos
nos mover na diagonal. Então, começando pelo quadrado verde, vamos ver para quais quadrados podemos nos mover e destacá-los em
azul:
Para escolher para qual quadrado mover em seguida, precisamos levar em conta duas heurísticas:
Para calcular essas heurísticas, esta é a fórmula que usaremos: distância = abs(de.x - para.x) + abs(de.y - para.y)
Vamos calcular o valor "g" para o quadrado azul imediatamente à esquerda do quadrado verde: abs(3 - 2) + abs(2 - 2) = 1
Ótimo! Temos o valor: 1. Agora, vamos tentar calcular o valor "h": abs(2 - 0) + abs(2 - 0) = 4
Vamos fazer o mesmo para todos os outros quadrados azuis. O número grande no centro de cada quadrado é o valor "f", enquanto o número
no canto superior esquerdo é o valor "g", e o número no canto superior direito é o valor "h":
Entretanto, neste caso, temos 2 nós com o mesmo valor f, 5. Como escolher entre eles?
Simplesmente, escolha um aleatoriamente ou tenha uma prioridade definida. Eu geralmente prefiro ter uma prioridade assim: "Direita > Cima >
Baixo > Esquerda"
Um dos nós com o valor f de 5 nos leva na direção "Down", e o outro nos leva "Left". Como Down tem prioridade maior que Left, escolhemos
o quadrado que nos leva "Down".
Agora, marco os nós para os quais calculamos a heurística, mas não movemos, como laranja, e o nó que escolhemos como ciano:
Tudo bem, agora vamos calcular a mesma heurística para os nós ao redor do nó ciano:
Novamente, escolhemos o nó que desce do nó ciano, pois todas as opções têm o mesmo valor f:
Vamos lá:
Por fim, podemos ver que temos um quadrado vencedor ao nosso lado, então nos movemos para lá e pronto.
Definição do problema:
Um quebra-cabeça 8 é um jogo simples que consiste em uma grade 3 x 3 (contendo 9 quadrados). Um dos quadrados está vazio. O objetivo
é mover os quadrados em diferentes posições e ter os números exibidos no "estado objetivo".
Dado um estado inicial de jogo de 8 quebra-cabeças e um estado final a ser alcançado, encontre o caminho mais econômico para atingir o
estado final a partir do estado inicial.
Estado inicial:
_ 13
425
786
Estado final:
123
456
78 _
Vamos considerar a distância de Manhattan entre o estado atual e o estado final como a heurística para este problema
declaração.
h(n) = | x - p | + | y - q |
onde x e y são coordenadas da célula no estado atual
p e q são coordenadas da célula no estado final
f(n) = g(n) + h(n), onde g(n) é o custo necessário para atingir o estado atual a partir do estado inicial dado
estado
Primeiro, encontramos o valor heurístico necessário para atingir o estado final a partir do estado inicial. A função de custo, g(n) = 0, como
estão no estado inicial
h(n) = 8
O valor acima é obtido, pois 1 no estado atual está a 1 distância horizontal de distância do que 1 no estado final. O mesmo
vale para 2, 5, 6. _ é 2 distância horizontal e 2 distância vertical. Então o valor total para h(n) é 1 + 1 + 1 + 1 +
Agora, os estados possíveis que podem ser alcançados a partir do estado inicial são encontrados e acontece que podemos mover para a _
1 3_4 413
25 _ 25
786 786
(1) (2)
Novamente a função de custo total é calculada para esses estados usando o método descrito acima e acaba sendo
6 e 7 respectivamente. Escolhemos o estado com custo mínimo que é o estado (1). Os próximos movimentos possíveis podem ser Esquerda,
Direita ou Baixo. Não vamos mover para a Esquerda como estávamos anteriormente naquele estado. Então, podemos mover para a Direita ou Baixo.
13 _ 123
425 4 _ 5
7 8 6 (3) 786
(4)
(3) leva a uma função de custo igual a 6 e (4) leva a 4. Também consideraremos (2) obtido antes que tem custo
função igual a 7. Escolher o mínimo deles leva a (4). Os próximos movimentos possíveis podem ser Esquerda ou Direita ou Baixo.
Obtemos estados:
(7)
Obtemos custos iguais a 5, 2 e 4 para (5), (6) e (7) respectivamente. Além disso, temos estados anteriores (3) e (2) com 6 e 7
respectivamente. Escolhemos o estado de custo mínimo que é (6). Os próximos movimentos possíveis são para cima, para baixo e claramente para baixo
nos levará ao estado final que leva ao valor da função heurística igual a 0.
Nota para futuros contribuidores: adicionei um exemplo para A* Pathfinding sem obstáculos, em uma grade 4x4. Um exemplo
com obstáculos ainda é necessário.
Vamos supor que este seja um labirinto. Não há paredes/obstáculos, no entanto. Temos apenas um ponto de partida (o
quadrado verde) e um ponto final (o quadrado vermelho). Vamos também supor que, para ir do verde ao vermelho, não podemos
mover diagonalmente. Então, começando pelo quadrado verde, vamos ver para quais quadrados podemos nos mover, e destacá-los em azul:
Para escolher para qual quadrado mover em seguida, precisamos levar em conta duas heurísticas:
Para calcular essas heurísticas, esta é a fórmula que usaremos: distância = abs(de.x - para.x) + abs(de.y - para.y)
Vamos calcular o valor "g" para o quadrado azul imediatamente à esquerda do quadrado verde: abs(3 - 2) + abs(2 - 2) = 1
Ótimo! Temos o valor: 1. Agora, vamos tentar calcular o valor "h": abs(2 - 0) + abs(2 - 0) = 4
Vamos fazer o mesmo para todos os outros quadrados azuis. O número grande no centro de cada quadrado é o valor "f", enquanto o número no
canto superior esquerdo é o valor "g", e o número no canto superior direito é o valor "h":
Entretanto, neste caso, temos 2 nós com o mesmo valor f, 5. Como escolher entre eles?
Simplesmente, escolha um aleatoriamente ou tenha uma prioridade definida. Eu geralmente prefiro ter uma prioridade assim: "Direita > Cima >
Baixo > Esquerda"
Um dos nós com o valor f de 5 nos leva na direção "Down", e o outro nos leva "Left". Como Down tem prioridade maior que Left, escolhemos
o quadrado que nos leva "Down".
Agora, marco os nós para os quais calculamos a heurística, mas não movemos, como laranja, e o nó que escolhemos como ciano:
Tudo bem, agora vamos calcular a mesma heurística para os nós ao redor do nó ciano:
Novamente, escolhemos o nó que desce do nó ciano, pois todas as opções têm o mesmo valor f:
Vamos lá:
Por fim, podemos ver que temos um quadrado vencedor ao nosso lado, então nos movemos para lá e pronto.
A declaração do problema é como se recebêssemos duas strings str1 e str2, então quantas operações mínimas podem ser
executadas na str1 para que ela seja convertida em str2?
Implementação em Java
} retornar dp[[Link]()][[Link]()];
}
Saída
O problema é que, dados certos trabalhos com seus horários de início e término, e um lucro que você obtém ao terminar o trabalho,
qual é o lucro máximo que você pode obter, já que não é possível executar dois trabalhos em paralelo?
Este parece Activity Selection usando Greedy Algorithm, mas há uma reviravolta adicional. Ou seja, em vez de
maximizando o número de trabalhos concluídos, focamos em obter o lucro máximo. O número de trabalhos realizados
não importa aqui.
Vejamos um exemplo:
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | UM
| B | C | E | E | F |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 6 | 4 | 2 | 5 | 11 | 5 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Os trabalhos são denotados com um nome, seu horário de início e término e lucro. Após algumas iterações, podemos descobrir se
realizamos o Trabalho-A e o Trabalho-E, podemos obter o lucro máximo de 17. Agora, como descobrir isso usando um algoritmo?
A primeira coisa que fazemos é classificar os trabalhos pelo tempo de conclusão em ordem não decrescente. Por que fazemos isso? É porque
se selecionarmos um trabalho que leve menos tempo para terminar, então deixaremos mais tempo para escolher outros trabalhos. Nós
ter:
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Teremos um array temporário adicional Acc_Prof de tamanho n (aqui, n denota o número total de trabalhos). Isso irá
contém o lucro máximo acumulado da execução dos trabalhos. Não entendeu? Espere e observe. Vamos inicializar o
valores do array com o lucro de cada trabalho. Isso significa que Acc_Prof[i] irá inicialmente conter o lucro da execução do i-ésimo
trabalho.
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Agora vamos denotar a posição 2 com i, e a posição 1 será denotada com j. Nossa estratégia será iterar j de 1 para
i-1 e após cada iteração, incrementaremos i em 1, até que i se torne n+1.
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Verificamos se Job[i] e Job[j] se sobrepõem, ou seja, se o tempo de término de Job[j] for maior que o tempo de início de Job[i] , então estes
dois trabalhos não podem ser feitos juntos. No entanto, se eles não se sobrepõem, verificaremos se Acc_Prof[j] + Profit[i] > Acc_Prof[i]. Se
este é o caso, atualizaremos Acc_Prof[i] = Acc_Prof[j] + Profit[i]. Ou seja:
Aqui Acc_Prof[j] + Profit[i] representa o lucro acumulado de fazer esses dois trabalhos juntos. Vamos verificar isso
nosso exemplo:
Aqui Job[j] se sobrepõe a Job[i]. Então estes dois não podem ser feitos juntos. Como nosso j é igual a i-1, incrementamos o
valor de i para i+1 que é 3. E fazemos j = 1.
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Agora Job[j] e Job[i] não se sobrepõem. O valor total de lucro que podemos obter escolhendo esses dois jobs é: Acc_Prof[j]
+ Profit[i] = 5 + 5 = 10 que é maior que Acc_Prof[i]. Então atualizamos Acc_Prof[i] = 10. Também incrementamos j em 1.
Nós conseguimos,
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Aqui, Job[j] se sobrepõe a Job[i] e j também é igual a i-1. Então incrementamos i em 1, e fazemos j = 1. Obtemos,
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
Agora, Job[j] e Job[i] não se sobrepõem, obtemos o lucro acumulado 5 + 4 = 9, que é maior que Acc_Prof[i]. Nós
atualize Acc_Prof[i] = 9 e incremente j em 1.
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Novamente Job[j] e Job[i] não se sobrepõem. O lucro acumulado é: 6 + 4 = 10, que é maior que Acc_Prof[i]. Nós
novamente atualizamos Acc_Prof[i] = 10. Incrementamos j em 1. Obtemos:
eu
eu
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Se continuarmos esse processo, depois de iterar por toda a tabela usando i, nossa tabela finalmente ficará assim:
+--------------+---------+---------+--- ------+---------+---------+------------+
| Nome | E | UM
| F | B | E | C |
+--------------+---------+---------+--- ------+---------+---------+------------+
|(Hora de início, hora de término)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Lucro | 5 | 6 | 5 | 4 | 11 | 2 |
+--------------+---------+---------+--- ------+---------+---------+------------+
| Acess_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+--------------+---------+---------+--- ------+---------+---------+------------+
Se iterarmos pelo array Acc_Prof, podemos descobrir que o lucro máximo é 17! O pseudocódigo:
Procedimento WeightedJobScheduling(Trabalho)
classificar o trabalho de acordo com o tempo de conclusão em ordem não decrescente
para i -> 2 para n
para j -> 1 para i-1
se Job[j].tempo_de_término <= Job[i].tempo_de_início
se Acc_Prof[j] + Lucro[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Lucro[i]
maxProfit = 0 para i
-> 1 para n se maxProfit
< Acc_Prof[i] maxProfit = Acc_Prof[i]
retornar maxProfit
A complexidade de popularização do array Acc_Prof é O(n2). A travessia do array leva O(n). Então a complexidade total desse algoritmo é O(n2).
Agora, se quisermos descobrir quais trabalhos foram realizados para obter o lucro máximo, precisamos percorrer o array na ordem inversa e se o
Acc_Prof corresponder ao maxProfit, colocaremos o nome do trabalho em uma pilha e subtrairemos o Profit desse trabalho do maxProfit.
Faremos isso até que nosso maxProfit > 0 ou atinjamos o ponto inicial do array Acc_Prof . O pseudocódigo ficará assim:
Uma coisa a lembrar: se houver várias programações de trabalho que podem nos dar o lucro máximo, só poderemos encontrar uma programação
de trabalho por meio deste procedimento.
Exemplo
Implementação em Java
se(m==0 || n==0)
retornar 0;
se([Link](m-1) == [Link](n-1))
retornar 1 + lcs(str1, str2, m-1, n-1);
outro
retornar [Link](lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
// Função iterativa
público int lcs2(String str1, String str2){
int lcs[][] = novo int[[Link]()+1][[Link]()+1];
para(int i=0;i<=[Link]();i++){
para(int j=0;j<=[Link]();j++){
se(i==0 || j== 0){
lcs[i][j] = 0;
}
senão se([Link](i-1) == [Link](j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}outro{
lcs[i][j] = [Link](lcs[i-1][j], lcs[i][j-1]);
}
}
}
retornar lcs[[Link]()][[Link]()];
}
Saída
Abordagem de baixo para cima para imprimir o enésimo número de Fibonacci usando Programação Dinâmica.
Árvore recursiva
mentira(5)
\
/ fib(4) \ fib(3) / \
Subproblemas sobrepostos
Aqui fib(0),fib(1) e fib(3) são os subproblemas [Link](0) está sendo repetido 3 vezes, fib(1) está sendo
repetido 5 vezes e fib(3) está sendo repetido 2 vezes.
Implementação
f[0]=0;f[1]=1; para(int
i=2;i<=n;i++){ f[i]=f[i-1]+f[i-2];
} retornar f[n];
}
Complexidade de tempo
Sobre)
Exemplos
Implementação em Java
}
senão arr[i][j] = 0;
}
} retornar máximo;
}
Complexidade de tempo
O(m*n)
puder identificar um subproblema simples que é calculado repetidamente, as chances são de que haja uma abordagem de programação dinâmica para o
problema.
Como este tópico é intitulado Aplicações da Programação Dinâmica, ele se concentrará mais nas aplicações do que no processo de criação de algoritmos de
programação dinâmica.
Números de Fibonacci são um assunto primordial para programação dinâmica, pois a abordagem recursiva tradicional faz muitos cálculos repetidos. Nestes
exemplos, usarei o caso base de f(0) = f(1) = 1.
Aqui está um exemplo de árvore recursiva para fibonacci(4), observe os cálculos repetidos:
Programação não dinâmica O(2^n) Complexidade de tempo de execução, O(n) Complexidade de pilha
retornar 1
retornar fibonacci(n-1) + fibonacci(n-2)
Esta é a maneira mais intuitiva de escrever o problema. No máximo, o espaço da pilha será O(n) conforme você desce o primeiro ramo recursivo fazendo
A prova da complexidade de tempo de execução O(2^n) que pode ser vista aqui: Complexidade computacional da sequência de Fibonacci. O ponto principal a
ser observado é que o tempo de execução é exponencial, o que significa que o tempo de execução para isso dobrará para cada termo subsequente,
Complexidade de tempo de execução O(n) memorizada , complexidade de espaço O(n) , complexidade de pilha O(n)
memorando
= [] [Link](1) # f(1) =
1 [Link](1) # f(2) = 1
def fibonacci(n): if
len(memo) > n: return
memo[n]
Com a abordagem memoizada, introduzimos um array que pode ser pensado como todas as chamadas de função anteriores. O memo[n]
de localização é o resultado da chamada de função fibonacci(n). Isso nos permite negociar a complexidade de espaço de O(n) para um tempo
de execução O(n), pois não precisamos mais calcular chamadas de função duplicadas.
Programação dinâmica iterativa O(n) Complexidade de tempo de execução, O(n) Complexidade de espaço, Sem pilha recursiva
def fibonacci(n):
memorando = [1,1] # f(0) = 1, f(1) = 1
Se dividirmos o problema em seus elementos principais, você notará que, para calcular fibonacci(n), precisamos de fibonacci(n-1) e
fibonacci(n-2). Também podemos notar que nosso caso base aparecerá no final disso
árvore recursiva como visto acima.
Com essas informações, agora faz sentido calcular a solução de trás para frente, começando nos casos base e trabalhando para cima.
Agora, para calcular fibonacci(n), primeiro calculamos todos os números de fibonacci até e através de n.
O principal benefício aqui é que agora eliminamos a pilha recursiva, mantendo o tempo de execução O(n) .
Infelizmente, ainda temos uma complexidade de espaço O(n), mas isso também pode ser alterado.
Programação dinâmica iterativa avançada O(n) Complexidade de tempo de execução, O(1) Complexidade de espaço, Sem pilha recursiva
def fibonacci(n):
memorando = [1,1] # f(1) = 1, f(2) = 1
Conforme observado acima, a abordagem de programação dinâmica iterativa começa nos casos base e trabalha até o resultado final. A
observação chave a ser feita para chegar à complexidade espacial para O(1) (constante) é a mesma observação que fizemos
para a pilha recursiva - precisamos apenas de fibonacci(n-1) e fibonacci(n-2) para construir fibonacci(n). Isso significa que
precisamos apenas salvar os resultados para fibonacci(n-1) e fibonacci(n-2) em qualquer ponto da nossa iteração.
Para armazenar esses 2 últimos resultados, uso uma matriz de tamanho 2 e simplesmente inverto o índice que estou atribuindo usando
i % 2, que alternará assim: 0, 1, 0, 1, 0, 1, ..., eu % 2.
Eu adiciono ambos os índices do array juntos porque sabemos que a adição é comutativa (5 + 6 = 11 e 6 + 5 == 11). O resultado é então
atribuído ao mais antigo dos dois pontos (denotado por i % 2). O resultado final é então armazenado na posição n%2
Notas
É importante observar que às vezes pode ser melhor criar uma solução iterativa memorizada para
funções que realizam grandes cálculos repetidamente, pois você criará um cache da resposta para a pergunta
chamadas de função e chamadas subsequentes podem ser O(1) se já tiverem sido computadas.
1. Heurística de compressão de caminho: findSet nunca precisa manipular uma árvore com altura maior que 2. Se ele acabar
iterando tal árvore, ele pode vincular os nós inferiores diretamente à raiz, otimizando travessias futuras;
2. Heurística de mesclagem baseada em altura: para cada nó, armazene a altura de sua subárvore. Ao mesclar, faça o
árvore mais alta é a mãe da menor, não aumentando assim a altura de ninguém.
se vRoot == uRoot:
retornar
Isso leva a um tempo O(alpha(n)) para cada operação, onde alfa é o inverso da função de Ackermann de crescimento rápido,
portanto, é de crescimento muito lento e pode ser considerado O(1) para fins práticos.
Isso torna todo o algoritmo de Kruskal O(m log m + m) = O(m log m), por causa da classificação inicial.
Observação
A compressão de caminho pode reduzir a altura da árvore, portanto, comparar alturas das árvores durante a operação de união pode
não ser uma tarefa trivial. Portanto, para evitar a complexidade de armazenar e calcular a altura das árvores, o pai resultante
pode ser escolhido aleatoriamente:
se vRoot == uRoot:
retornar
se aleatório() % 2 == 0:
[Link] = uRoot senão:
[Link] = vRoot
Na prática, este algoritmo aleatório juntamente com a compressão de caminho para a operação findSet resultará em
retornar findSet([Link])
[Link] = vRoot
makeSet(n)
para cada aresta e em G: se
findSet([Link]) != findSet([Link]): unionSet([Link], [Link])
Essa implementação ingênua leva a um tempo O(n log n) para gerenciar a estrutura de dados do conjunto disjunto, levando a um tempo O(m*n log n) para todo o
algoritmo de Kruskal.
retornar MST
Suponha que temos um arquivo de dados de 100.000 caracteres que desejamos armazenar de forma compacta. Assumimos que há
apenas 6 caracteres diferentes naquele arquivo. A frequência dos caracteres é dada por:
+-------------+-----+-----+-----+-----+ -----+-----+
| Personagem | um | b | c | d | e | f |
+-------------+-----+-----+-----+-----+ -----+-----+
|Frequência (em milhares)| 45 | 13 | 12 | 16 | 9 | 5 |
+-------------+-----+-----+-----+-----+ -----+-----+
Temos muitas opções de como representar tal arquivo de informações. Aqui, consideramos o problema de projetar um Código de Caracteres
Binários em que cada caractere é representado por uma string binária única, que chamamos de palavra-código.
+-------------+-----+-----+-----+-----+ -----+-----+
| Personagem | um | b | c | d | e | f |
+-------------+-----+-----+-----+-----+ -----+-----+
| Palavra-código de comprimento fixo | 000 | 001 | 010 | 011 | 100 | 101 |
+-------------+-----+-----+-----+-----+ -----+-----+
|Palavra-código de comprimento variável| 0 | 101 | 100 | 111 | 1101| 1100|
+-------------+-----+-----+-----+-----+ -----+-----+
Se usarmos um código de comprimento fixo, precisamos de três bits para representar 6 caracteres. Este método requer 300.000 bits
para codificar o arquivo inteiro. Agora a questão é: podemos fazer melhor?
Um código de comprimento variável pode ter um desempenho consideravelmente melhor do que um código de comprimento fixo, ao dar aos
caracteres frequentes palavras-código curtas e aos caracteres pouco frequentes palavras-código longas. Este código requer: (45 X 1 + 13 X 3 + 12 X 3
+ 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bits para representar o arquivo, o que economiza aproximadamente 25% de memória.
Uma coisa a lembrar, consideramos aqui apenas códigos nos quais nenhuma palavra-código também é um prefixo de alguma outra
palavra-código. Esses são chamados códigos de prefixo. Para codificação de comprimento variável, codificamos o arquivo de 3 caracteres abc
como 0.101.100 = 0101100, onde "." denota a concatenação.
Códigos de prefixo são desejáveis porque simplificam a decodificação. Como nenhuma palavra-código é um prefixo de qualquer outra,
a palavra-código que inicia um arquivo codificado é inequívoca. Podemos simplesmente identificar a palavra-código inicial, traduzi-la de volta para o
caractere original e repetir o processo de decodificação no restante do arquivo codificado. Por exemplo, 001011101 analisa exclusivamente
como 0.0.101.1101, que decodifica para aabe. Em suma, todas as combinações de representações binárias são únicas. Digamos, por
exemplo, que se uma letra for denotada por 110, nenhuma outra letra será denotada por 1101 ou 1100. Isso ocorre porque você pode enfrentar
confusão sobre selecionar 110 ou continuar concatenando o próximo bit e selecionar aquele.
Técnica de compressão:
A técnica funciona criando uma árvore binária de nós. Eles podem ser armazenados em uma matriz regular, cujo tamanho depende do
número de símbolos, n. Um nó pode ser um nó folha ou um nó interno. Inicialmente, todos os nós são nós folha, que contêm o símbolo em si,
sua frequência e, opcionalmente, um link para seus nós filhos. Como convenção, o bit '0' representa o filho esquerdo e o bit '1' representa o
filho direito. A fila de prioridade é usada para armazenar os nós, o que fornece ao nó a menor frequência quando estourado. O processo é descrito
abaixo:
[Link](n)
fim
enquanto [Link]() não for igual a 1 Z = new node()
[Link] = x = [Link]
[Link] = y = [Link]
[Link]ência = [Link]ência + [Link]ência [Link](Z) fim
enquanto
Retornar Q
Embora o tempo linear forneça uma entrada ordenada, em casos gerais de entrada arbitrária, usar esse algoritmo requer pré-
ordenação. Assim, como a ordenação leva tempo O(nlogn) em casos gerais, ambos os métodos têm a mesma complexidade.
Como n aqui é o número de símbolos no alfabeto, que normalmente é um número muito pequeno (comparado ao comprimento da
mensagem a ser codificada), a complexidade de tempo não é muito importante na escolha deste algoritmo.
Técnica de descompressão:
O processo de descompressão é simplesmente uma questão de traduzir o fluxo de códigos de prefixo para valor de byte individual, geralmente
atravessando a árvore de Huffman nó por nó, à medida que cada bit é lido do fluxo de entrada. Alcançar um nó folha necessariamente
encerra a busca por aquele valor de byte específico. O valor folha representa o desejado
personagem. Normalmente a Árvore de Huffman é construída usando dados estatisticamente ajustados em cada ciclo de compressão,
portanto a reconstrução é bastante simples. Caso contrário, as informações para reconstruir a árvore devem ser enviadas separadamente.
O pseudocódigo:
Procedimento HuffmanDecompression(root, S): // root representa a raiz da Árvore de Huffman n := [Link] // S refere-se ao fluxo de bits a ser descompactado para
i := 1 a n
atual = raiz
enquanto [Link] != NULL e [Link] != NULL se S[i] for igual a '0'
atual := [Link]
senão
atual := [Link] fimse
i := i+1
fimenquanto
imprimir [Link] fimpara
Explicação gananciosa:
A codificação de Huffman analisa a ocorrência de cada caractere e a armazena como uma sequência binária de forma
otimizada. A ideia é atribuir códigos de comprimento variável aos caracteres de entrada, o comprimento dos códigos
atribuídos é baseado nas frequências dos caracteres correspondentes. Criamos uma árvore binária e operamos nela de forma
ascendente para que os dois caracteres menos frequentes estejam o mais longe possível da raiz. Dessa forma, o caractere mais
frequente obtém o menor código e o caractere menos frequente obtém o maior código.
Referências:
Introdução aos Algoritmos - Charles E. Leiserson, Clifford Stein, Ronald Rivest e Thomas H. Cormen Huffman
Codificação - Wikipédia
Matemática Discreta e suas Aplicações - Kenneth H. Rosen
Você tem um conjunto de coisas para fazer (atividades). Cada atividade tem um horário de início e um horário de término. Você não
tem permissão para executar mais de uma atividade por vez. Sua tarefa é encontrar uma maneira de executar o número máximo de atividades.
Por exemplo, suponha que você tenha uma seleção de aulas para escolher.
Lembre-se, você não pode fazer duas aulas ao mesmo tempo. Isso significa que você não pode fazer a aula 1 e 2 porque elas compartilham
um horário comum das 10h30 às 11h00. No entanto, você pode fazer a aula 1 e 3 porque elas não compartilham um horário comum. Então
sua tarefa é fazer o máximo de aulas possível sem nenhuma sobreposição. Como você pode fazer isso?
Análise
Vamos pensar na solução por meio de uma abordagem gananciosa. Primeiro, escolhemos aleatoriamente alguma abordagem e verificamos se ela irá
trabalhar ou não.
classificar a atividade por hora de início, o que significa que a atividade que começa primeiro, nós a pegaremos primeiro. então pegue primeiro para
último da lista classificada e verifique se ele irá cruzar com a atividade anterior ou não. Se a atividade atual não for
intersectar com a atividade realizada anteriormente, realizaremos a atividade, caso contrário, não a realizaremos.
a abordagem funcionará para alguns casos como
a ordem de classificação será 4-->1-->2-->3. A atividade 4--> 1--> 3 será executada e a atividade 2 será pulada.
o máximo de 3 atividades será executado. Funciona para esse tipo de caso. mas falhará em alguns casos. Vamos aplicar
esta abordagem para o caso
A ordem de classificação será 4-->1-->2-->3 e apenas a atividade 4 será executada, mas a resposta pode ser atividade 1-->3 ou 2-
->3 será executado. Então nossa abordagem não funcionará para o caso acima. Vamos tentar outra abordagem
Classifique a atividade por duração de tempo , o que significa executar a atividade mais curta primeiro. que pode resolver o anterior
problema . Embora o problema não esteja completamente resolvido. Ainda há alguns casos que podem falhar a solução.
aplique esta abordagem no caso abaixo.
se classificarmos a atividade por duração de tempo, a ordem de classificação será 2--> . e se realizarmos a atividade nº 2 primeiro então
3 --->1, nenhuma outra atividade pode ser realizada. Mas a resposta será executar atividade 1, então executar 3, . Então podemos executar
no máximo 2 atividades. Então, isso não pode ser uma solução para esse problema. Devemos tentar uma abordagem diferente.
A solução
Classifique a atividade por hora de término, o que significa que a atividade termina primeiro. O algoritmo é fornecido
abaixo
classifique a atividade pelos horários de , Então a ordem de classificação será 1-->5-->2-->4-->3.. a resposta é 1-->3 essas duas atividades
término em que será realizada. Essa é a resposta. Aqui está o código sudo.
1. classificar: atividades
Sistemas monetários canônicos. Para alguns sistemas monetários, como os que usamos na vida real, a solução "intuitiva" funciona
perfeitamente. Por exemplo, se as diferentes moedas e notas de euro (excluindo centavos) forem 1€, 2€, 5€, 10€, dar a moeda ou nota
mais alta até atingirmos o valor e repetir esse procedimento levará ao conjunto mínimo de moedas.
restante *) let coin = [Link] ((>=) amount) money_system in loop (coin::given) (amount - coin) in loop [] amount
Esses sistemas são feitos para que a troca seja fácil. O problema fica mais difícil quando se trata de sistema monetário arbitrário.
Caso geral. Como dar 99€ com moedas de 10€, 7€ e 5€? Aqui, dar moedas de 10€ até que restem 9€ leva obviamente a nenhuma
solução. Pior do que isso, uma solução pode não existir. Este problema é de fato np-difícil, mas existem soluções aceitáveis misturando
ganância e memorização . A ideia é explorar todas as possibilidades e escolher aquela com
o número mínimo de moedas.
Para dar uma quantia X > 0, escolhemos uma peça P no sistema monetário e então resolvemos o subproblema correspondente a XP.
Tentamos isso para todas as peças do sistema. A solução, se existir, é então o menor caminho que levou a 0.
Aqui está uma função recursiva OCaml correspondente a este método. Ela retorna None, se nenhuma solução existir.
Alguns 1
Nenhum outro (*nós procuramos o menor caminho diferente de Nenhum com as peças restantes*) optmin (optsucc (loop x)) acc
em
Nota: Podemos observar que esse procedimento pode computar várias vezes o conjunto de alterações para o mesmo valor. Na
prática, usar memoização para evitar essas repetições leva a resultados mais rápidos (muito mais rápidos).
Dizemos que uma solicitação é um cache hit, quando o item já está no cache, caso contrário, é chamado de cache miss. Nesse caso,
devemos trazer o item solicitado para o cache e despejar outro, assumindo que o cache esteja cheio. O objetivo é um cronograma de despejo
que minimize o número de despejos.
Existem inúmeras estratégias gananciosas para esse problema, vamos ver algumas:
Atenção: Nos exemplos a seguir, removemos a página com o menor índice, caso mais de uma página possa ser removida.
Exemplo (FIFO)
Treze falhas de cache por dezesseis solicitações não parece muito ideal. Vamos tentar o mesmo exemplo com outra
estratégia:
Exemplo (LFD)
Autoteste: faça o exemplo para LIFO, LFU, RFU e veja o que aconteceu.
O esqueleto é uma aplicação que resolve o problema dependendo da estratégia gananciosa escolhida:
#incluir <iostream>
#incluir <memória>
// para redefinir
char originalCache[] = {'a','b','c'};
estratégia de classe {
público:
Estratégia(std::string nome) : strategyName(nome) {} virtual ~Strategy() =
default;
// calcula qual local de cache deve ser usado virtual int apply(int
requestIndex) = 0;
retornar éMiss;
}
int principal()
{
Estratégia* selectedStrategy[] = { novo FIFO, novo LIFO, novo LRU, novo LFU, novo LFD };
int cntPerdas = 0;
" "
corte << << solicitação[i] << "\t";
" "
para (int l=0; l < cacheSize; ++l) cout << cout << (isMiss ? << cache[l] << "\t";
"x" : "") << endl;
}
"
cout<< "\nTotal de falhas de cache: << cntPerde << endl;
}
A ideia básica é simples: para cada solicitação, tenho duas chamadas, minha estratégia:
1. apply: A estratégia tem que dizer ao chamador qual página usar 2. update: Depois
que o chamador usa o lugar, ele diz à estratégia se foi um erro ou não. Então a estratégia pode atualizar seus dados internos. A estratégia LFU, por exemplo,
tem que atualizar a frequência de acertos para as páginas de cache, enquanto a estratégia LFD tem que recalcular as distâncias para as páginas de
cache.
Agora vamos dar uma olhada em exemplos de implementações para nossas cinco estratégias:
FIFO
FIFO() : Estratégia("FIFO") {
se(!cacheMiss)
retornar;
outro
idade[i] = 0;
}
}
privado:
int idade[tamanhodocache];
};
O FIFO só precisa da informação de quanto tempo uma página fica no cache (e, claro, apenas em relação às outras páginas). Então
a única coisa a fazer é esperar por uma falha e então fazer as páginas, que não foram despejadas mais antigas. Para o nosso exemplo
acima a solução do programa é:
Estratégia: FIFO
UEPS
outro
idade[i] = 0;
}
}
privado:
int idade[tamanhodocache];
};
A implementação do LIFO é mais ou menos a mesma que a do FIFO , mas nós despejamos a página mais nova, não a mais velha.
os resultados do programa são:
Estratégia: LIFO
LRU
outro
idade[i] = 0;
}
}
privado:
int idade[tamanhodocache];
};
No caso de LRU a estratégia é independente do que está na página de cache, seu único interesse é o último uso.
Estratégia: LRU
LFU
retornar menos;
}
outro
++requestFrequency[cachePos];
}
privado:
O LFU despeja a página que menos usa. Então a estratégia de atualização é apenas contar cada acesso. Claro que depois de uma falha,
contagem reinicia. Os resultados do programa são:
Estratégia: LFU
LFD
classe LFD : estratégia pública {
público:
LFD() : Estratégia("LFD")
{
// pré-calcula o próximo uso antes de começar a atender às solicitações
para (int i=0; i<tamanhodocache; ++i) nextUse[i] = calcNextUse(-1, cache[i]);
}
privado:
retornar requestLength + 1;
}
A estratégia LFD é diferente de todas as anteriores. É a única estratégia que usa as solicitações futuras para seu
decisão de quem despejar. A implementação usa a função calcNextUse para obter a página cujo próximo uso é
Estratégia: LFD
A estratégia gananciosa LFD é de fato a única estratégia ótima das cinco apresentadas. A prova é bastante longa e pode
ser encontrado aqui ou no livro de Jon Kleinberg e Eva Tardos (veja as fontes nos comentários abaixo).
Algoritmo vs Realidade
A estratégia LFD é ótima, mas há um grande problema. É uma solução offline ótima. Na prática, o cache é geralmente
um problema online , o que significa que a estratégia é inútil porque não podemos saber a próxima vez que precisarmos de um determinado
item. As outras quatro estratégias também são estratégias online . Para problemas online, precisamos de uma estratégia geral diferente
abordagem.
Você tem um bilhete automático que dá troca em moedas com valores 1, 2, 5, 10 e 20. A dispensação do
a troca pode ser vista como uma série de quedas de moedas até que o valor correto seja dispensado. Dizemos que uma dispensação é ótima
quando sua contagem de moedas é mínima para seu valor.
Seja M em [1,50] o preço do bilhete T e P em [1,50] o dinheiro que alguém pagou por T, com P >= M. Seja D=PM.
Definimos o benefício de um passo como a diferença entre D e Dc com c a moeda que o automático dispensa neste
etapa.
Depois, a soma de todas as moedas é claramente igual a D. É um algoritmo ganancioso porque, após cada passo e após cada
repetição de um passo, o benefício é maximizado. Não podemos dispensar outra moeda com um benefício maior.
int principal() {
coinCount.push_back(contagemMoedas);
}
retornar 0;
}
// valores de moedas
std::vector<unsigned int> coinValues;
int valordamoeda;
cout << "Valor da moeda (<1 para parar): "; cin >>
coinValue;
se(valordamoeda > 0)
valoresdamoeda.push_back(valordamoeda);
senão
quebrar;
}
// classificar valores
sort([Link](), [Link](), std::greater<int>());
retornar coinValues;
}
Esteja ciente de que agora há uma verificação de entrada para manter o exemplo simples. Um exemplo de saída:
Enquanto 1 estiver nos valores da moeda, sabemos que o algoritmo será encerrado, porque:
1. Seja C o maior valor da moeda. O tempo de execução é polinomial apenas enquanto D/C for polinomial, porque o
a representação de D usa apenas bits de log D e o tempo de execução é pelo menos linear em D/C.
2. Em cada passo nosso algoritmo escolhe o ótimo local. Mas isso não é suficiente para dizer que o algoritmo encontra a solução ótima
global (veja mais informações aqui ou no Livro de Korte e Vygen).
Um simples contraexemplo: as moedas são 1,3,4 e D=6. A solução ótima é claramente duas moedas de valor 3, mas o ganancioso
escolhe 4 no primeiro passo, então ele tem que escolher 1 no passo dois e três. Então ele não dá uma solução ótima. Um possível
Algoritmo ótimo para este exemplo é baseado em programação dinâmica.
O objetivo é encontrar o subconjunto máximo de jobs mutuamente compatíveis. Existem várias abordagens gananciosas para esse
problema:
A questão agora é qual abordagem é realmente bem-sucedida. Início antecipado definitivamente não, aqui está um contra-exemplo
e menos conflitos pode realmente parecer ótimo, mas aqui está um caso problemático para esta abordagem:
O que nos deixa com o tempo de término mais cedo. O pseudocódigo é bem simples:
conjunto vazio 3. para j=1 a n se j for compatível com todos os trabalhos em A, defina A=A+{j}
// Horários de início do
trabalho const int startTimes[] = { 2, 3, 1, 4, 3, 2, 6, 7, 8, 9};
// Horários de término do
trabalho const int endTimes[] = { 4, 4, 3, 5, 5, 5, 8, 9, 9, 10};
int principal()
{
empregos vector<par<int,int>> ;
// passo 1: classificar
sort([Link](), [Link](),[](pair<int,int> p1, pair<int,int> p2) { return [Link] < [Link]; });
// passo 3:
para(int i=0; i<jobCnt; ++i) {
trabalho automático =
jobs[i]; bool isCompatible = true;
para(auto jobIndex : A) {
{
éCompatível = falso; quebrar;
}
}
se(éCompatível)
A.push_back(i);
}
//passo 4: imprimir A
cout << "Compatível: ";
para(auto i : A) cout
<< "(" << empregos[i].primeiro << "," << empregos[i].segundo << ") "; cout << fim;
retornar 0;
}
A implementação do algoritmo está claramente em ÿ(n^2). Há uma implementação ÿ(n log n) e o leitor interessado pode continuar
lendo abaixo (Exemplo Java).
Agora temos um algoritmo guloso para o problema de agendamento de intervalos, mas ele é ótimo?
Suponha que ganancioso não seja ótimo e i1,i2,...,ik denote o conjunto de trabalhos selecionados por ganancioso. Seja j1,j2,...,jm
denote o conjunto de trabalhos em uma solução ótima com i1=j1,i2=j2,...,ir=jr para o maior valor possível de r.
O trabalho i(r+1) existe e termina antes de j(r+1) (término mais cedo). Mas então j1,j2,...,jr,i(r+1),j(r+2),...,jm também é uma solução
ótima e para todo k em [1,(r+1)] é jk=ik. isso é uma contradição à maximalidade de r. Isso conclui a prova.
Este segundo exemplo demonstra que geralmente há muitas estratégias gananciosas possíveis, mas apenas algumas ou mesmo
nenhuma podem encontrar a solução ideal em todos os casos.
importar [Link];
importar [Link];
classe Trabalho
{
int início, fim, lucro;
}
}
int lo = 0, hi = índice - 1;
}
senão hi = mid - 1;
}
retornar -1;
}
int n = [Link];
int tabela[] = novo int[n]; tabela[0] =
empregos[0].lucro;
retornar tabela[n-1];
}
"
[Link](" O lucro ideal é + agendar(trabalhos));
}
}
E a saída esperada é:
123456
tj 3 2 1 4 3 2
DJ 6 8 9 9 10 11
Trabalho 3 2 2 5 5 5 4 4 4 4 1 1 1 6 6
Tempo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Nível -8 -5 -4 1 7 4
A solução L=7 obviamente não é ótima. Vamos dar uma olhada em algumas estratégias gananciosas:
É fácil ver que o menor tempo de processamento primeiro não é o ideal. Um bom contra-exemplo é
12
tj 1 5
DJ 10 5
12
tj 1 5
DJ 3 5
3. para j=1 a n
Atribuir tarefa j ao intervalo [t,t+tj]
// Horários de início do
trabalho const int processTimes[] = { 2, 3, 1, 4, 3, 2, 3, 5, 2, 1};
// Horários de término
do trabalho const int dueTimes[] = { 4, 7, 9, 13, 8, 17, 9, 11, 22, 25};
int principal()
{
empregos vector<par<int,int>> ;
// passo 1: classificar
sort([Link](), [Link](),[](pair<int,int> p1, pair<int,int> p2) { return [Link] < [Link]; });
// etapa 3:
vector<pair<int,int>> jobIntervals;
jobIntervals.push_back(make_pair(t,t+jobs[i].first)); t += jobs[i].first;
int atraso = 0;
cout << "(" << [Link] << "," << [Link] << ") "
<< "Atraso: " << [Link]-empregos[i].segundo << std::endl;
}
"
cout << "\natraso máximo é << atraso << fiml;
retornar 0;
}
Intervalos:
(0,2) Atraso:-2
(2,5) Atraso:-2
(5,8) Atraso: 0
(8,9) Atraso: 0
(9,12) Atraso: 3
(12,17) Atraso: 6
(17,21) Atraso: 8
(21,23) Atraso: 6
(23,25) Atraso: 3
(25,26) Atraso: 1
atraso máximo é 8
O tempo de execução do algoritmo é obviamente ÿ(n log n) porque a classificação é a operação dominante deste algoritmo.
Agora precisamos mostrar que é ótimo. Claramente, um cronograma ótimo não tem tempo ocioso. o prazo mais cedo primeiro
a programação também não tem tempo ocioso.
Vamos supor que os trabalhos sejam numerados de modo que d1<=d2<=...<=dn. Dizemos que uma inversão de um cronograma é um par de
trabalhos i e j de modo que i<j, mas j é agendado antes de i. Devido à sua definição, o primeiro cronograma com prazo mais cedo não tem
inversões. Claro que se um cronograma tem uma inversão, ele tem um com um par de trabalhos invertidos agendados consecutivamente.
Proposição: Trocar dois trabalhos adjacentes e invertidos reduz o número de inversões em um e não aumenta o atraso máximo.
Prova: Seja L o atraso antes da troca e M o atraso depois. Como trocar dois jobs adjacentes não move os outros jobs de suas
posições, é Lk=Mk para todo k != i,j.
Claramente é Mi<=Li, já que o trabalho i foi agendado mais cedo. Se o trabalho j estiver atrasado, segue a definição:
Isso significa que o atraso após a troca é menor ou igual ao anterior. Isso conclui a prova.
Vamos supor que S* seja um cronograma ótimo com o menor número possível de inversões. Podemos supor que S* não tem tempo ocioso. Se
S* não tem inversões, então S=S* e estamos prontos. Se S* tem uma inversão, então tem uma inversão adjacente. A última Proposição
afirma que podemos trocar a inversão adjacente sem aumentar o atraso, mas diminuindo o número de inversões. Isso contradiz a definição de S*.
O problema de minimização de atraso e seu problema de makespan mínimo quase relacionado , onde a questão para um cronograma
mínimo é feita, têm muitas aplicações no mundo real. Mas geralmente você não tem apenas uma máquina, mas muitas, e elas lidam com a
mesma tarefa em taxas diferentes. Esses problemas ficam NP-completos muito rápido.
Outra questão interessante surge se não olharmos para o problema offline , onde temos todas as tarefas e dados em
mão, mas na variante online , onde as tarefas aparecem durante a execução.
Nossa tarefa é configurar linhas de tal forma que todas as casas estejam conectadas e o custo de configuração de toda a conexão
seja mínimo. Agora, como descobrimos isso? Podemos usar o Algoritmo de Prim.
Algoritmo de Prim é um algoritmo guloso que encontra uma árvore geradora mínima para um grafo não direcionado ponderado. Isso
significa que ele encontra um subconjunto das arestas que formam uma árvore que inclui todos os nós, onde o peso total de todas
as arestas na árvore é minimizado. O algoritmo foi desenvolvido em 1930 pelo matemático tcheco Vojtÿch Jarník e mais tarde
redescoberto e republicado pelo cientista da computação Robert Clay Prim em 1957 e Edsger Wybe Dijkstra em 1959. Também é
conhecido como algoritmo DJP, algoritmo de Jarnik, algoritmo Prim-Jarnik ou algoritmo Prim-Dijsktra.
Agora, vamos olhar primeiro para os termos técnicos. Se criarmos um grafo, S usando alguns nós e arestas de um grafo não
direcionado G, então S é chamado de subgrafo do grafo G. Agora S será chamado de Spanning Tree se e somente se:
Pode haver muitas Spanning Tree's de um grafo. A Minimum Spanning Tree de um grafo não direcionado ponderado é uma árvore,
tal que a soma do peso das arestas é mínima. Agora usaremos o algoritmo de Prim para descobrir a spanning tree mínima,
que é como configurar as linhas telefônicas em nosso grafo de exemplo de tal forma que o custo de configuração seja mínimo.
Primeiro, selecionaremos um nó de origem . Digamos que o nó-1 seja nossa origem. Agora, adicionaremos a aresta do nó-1 que tem o
custo mínimo ao nosso subgrafo. Aqui, marcamos as arestas que estão no subgrafo usando a cor azul. Aqui, 1-5 é
Agora consideramos todas as arestas do nó-1 e nó-5 e pegamos o mínimo. Como 1-5 já está marcado, nós
pegue 1-2.
Desta vez, consideramos o nó-1, o nó-2 e o nó-5 e tomamos a aresta mínima que é 5-4.
O próximo passo é importante. Do nó-1, nó-2, nó-5 e nó-4, a aresta mínima é 2-4. Mas se selecionarmos
esse, ele criará um ciclo em nosso subgrafo. Isso ocorre porque o nó-2 e o nó-4 já estão em nosso subgrafo. Então
tomar a aresta 2-4 não nos beneficia. Selecionaremos as arestas de tal forma que adicione um novo nó em nosso subgrafo. Então nós
Se continuarmos dessa forma, selecionaremos as arestas 8-6, 6-7 e 4-3. Nosso subgrafo ficará assim:
Este é o nosso subgrafo desejado, que nos dará a árvore de abrangência mínima. Se removermos as arestas que não
selecione, obteremos:
Esta é nossa árvore de abrangência mínima (MST). Então o custo de configuração das conexões telefônicas é: 4 + 2 + 5 + 11 + 9
+ 2 + 1 = 34. E o conjunto de casas e suas conexões são mostrados no gráfico. Pode haver vários MST de um
gráfico. Depende do nó de origem que escolhermos.
Enew[] = {}
enquanto Vnew não for igual a V u -> um nó
de Vnew v -> um nó que não está
em Vnew tal que a aresta uv tenha o custo mínimo
// se dois nós tiverem o mesmo peso, escolha qualquer um deles
adicione v a Vnew
adicione aresta (u, v) a Enew fim
enquanto
Retornar Vnew e Enew
Complexidade:
A complexidade de tempo da abordagem ingênua acima é O(V²). Ela usa matriz de adjacência. Podemos reduzir a complexidade usando fila
de prioridade. Quando adicionamos um novo nó a Vnew, podemos adicionar suas arestas adjacentes na fila de prioridade. Então, retire a aresta
ponderada mínima dele. Então a complexidade será: O(ElogE), onde E é o número de arestas.
Novamente, um heap binário pode ser construído para reduzir a complexidade para O(ElogV).
Priority_Queue()
Q=V
enquanto Q não estiver vazio u
-> [Link] para
cada v adjacente a i se v pertencer a Q
e Edge(u,v) < key[v] // aqui Edge(u, v) representa // custo de edge(u,
v)
parent[v] := u key[v] :=
Edge(u, v) fim se fim para fim
enquanto
Aqui key[] armazena o custo mínimo de travessia do nó-v. parent[] é usado para armazenar o nó pai. É útil para travessia e impressão da árvore.
importar [Link].*;
Inteiro Nós N;
Gráfico(int[][] mat) {
int i, j; NNodes
= comprimento da esteira;
LinkCost = novo int[NNodes][NNodes]; para ( i=0; i <
NNodes; i++) {
CustoDoLink [ i ] [ j ] = mat [ i ] [ j ] ; se
( CustoDoLink [ i ] [ j ] == 0 )
LinkCost [ i ] [ j ] = infinito ;
}
int i, j, k, x, y ; boolean
[ ] Alcançado = novo boolean [ NNodes ] ; int [ ] predNode
= novo int [NNodes ] ;
Atingido [ 0 ] =
verdadeiro ; para ( k = 1 ; k < NNodes ; k+
+){
Atingido [ k ] = falso ;
} predNode [ 0 ] = 0 ;
printReachSet ( Alcançado ) ; para
(k = 1 ; k < NNodes ; k++ ) {
x=y=0;
para ( i = 0 ; i < NNodes ; i++ ) para ( j =
0;{ j < NNodes ; j++ )
} int [ ] a = predNode ;
para ( i = 0 ; i < NNodes ; i++ )
" --> "
Sistema .out .println ( a [ i ] + + eu ) ;
{
Sistema .out .print ("ReachSet = " ) ; para
(int i = 0 ; i < Alcanç[Link] ; i++ ) se ( Alcançado
[i])
Sistema .out .print ( i + " " ) ; //
[Link]();
}
público estático vazio principal (String [ ] args )
{
int [ ] [ ] conn = { { 0 { 3 { 0 , 3 , 0 , 2 , 0 , 0 , 0 , 0 , 4 }, // 0
, 0 , 0 , 0 , 0 , 0 , 0 , 4 , 0 }, // 1
, 0 , 0 , 6 , 0 , 1 , 0 , 2 , 0 }, // 2
, 0 , 6 , 0 , 1 , 0 , 0 , 0 , 0 }, // 3
, 0 , 0 , 1 , 0 , 0 , 0 , 0 , 8 }, // 4
, 0 , 1 , 0 , 0 , 0 , 8 , 0 , 0 }, // 5
, 0 , 0 , 0 , 0 , 8 , 0 , 0 , 0 }, // 6
, 4 , 2 , 0 , 0 , 0 , 0 , 0 , 0 }, // 7 0 } //
, 0, 0, 0, 8, 0, 0, 0, 8
{2{0{0{0{0{4};
Gráfico G = novo gráfico (conn ) ;
[Link] ( ) ;
}
}
Saída:
$ java Gráfico
*3*2****4
3******4*
***6*1*2*2*6*1****
***1****8
**1***8*******8***
*42******
4***8****
ReachSet = 0 Custo mínimo de borda : ( 0 , 3 )custo = 2
AlcanceConjunto = 0 3
Margem de custo mínimo : ( 3 , 4 )custo = 1
AlcanceConjunto = 0 3 4
Custo mínimo de vantagem(: 01 ,) custo = 3
ReachSet = 0 1 3 4 8 )custo
Margem de custo mínimo : ( 0 ,= 4
AlcanceConjunto = 0 1 3 4 8
Margem de custo mínimo : ( 1 , 7 )custo = 4
AlcanceConjunto = 0 1 3 4 7 8
Custo mínimo de vantagem( :72,) custo = 2
ReachSet = 0 1 2 3 4 7 8 5 )custo = 1
Margem de custo mínimo : ( 2,
AlcanceConjunto = 0 1 2 3 4 5 7 8
Custo mínimo de vantagem( :56,) custo = 8
AlcanceConjunto = 0 1 2 3 4 5 6 7 8
0 --> 0 0
--> 1
7 --> 2
0 --> 3 3
--> 4
2 --> 5
5 --> 6
1 --> 7
0 --> 8
Antes de ler este exemplo, é necessário ter uma breve ideia sobre relaxamento de borda. Você pode aprender aqui
Bellman-Ford O algoritmo calcula os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um dígrafo ponderado.
Embora seja mais lento que o Algoritmo de Dijkstra, ele funciona nos casos em que o peso da aresta é negativo e também encontra um ciclo de
peso negativo no gráfico. O problema com o Algoritmo de Dijkstra é que, se houver um ciclo negativo, você continua passando pelo ciclo
repetidamente e continua reduzindo a distância entre dois vértices.
A ideia desse algoritmo é percorrer todas as arestas desse gráfico, uma por uma, em alguma ordem aleatória. Pode ser qualquer ordem aleatória. Mas você deve
garantir que, se uv (onde u e v são dois vértices em um gráfico) for uma de suas ordens, então deve haver uma aresta de u a v. Normalmente, ela é tirada
Após selecionar a ordem, relaxaremos as arestas de acordo com a fórmula de relaxamento. Para uma aresta uv dada indo de u para v a fórmula de
relaxamento é:
Isto é, se a distância da fonte a qualquer vértice u + o peso da aresta uv for menor que a distância da fonte a outro vértice v, atualizamos a distância da
fonte a v. Precisamos relaxar as arestas no máximo (V-1) vezes, onde V é o número de arestas no gráfico. Por que (V-1), você pergunta? Explicaremos em
outro exemplo. Também manteremos o controle do vértice pai de qualquer vértice, ou seja, quando relaxamos uma aresta, definiremos:
pai[v] = u
Isso significa que encontramos outro caminho mais curto para chegar a v via u. Precisaremos disso mais tarde para imprimir o caminho mais curto da origem
até o vértice de destino.
Selecionamos 1 como o vértice de origem . Queremos descobrir o caminho mais curto da origem para todos os outros
vértices.
A princípio, d[1] = 0 porque é a fonte. E o resto é infinito, porque ainda não sabemos sua distância.
+--------+--------+--------+--------+--------+---- ----+--------+
| Série | 1 | 2 | 3 | 4| 5 | 6 |
+--------+--------+--------+--------+--------+---- ----+--------+
| Borda | 4->5 | 3->4 | 1->3 | 1->4 | 4->6 | 2->3 |
+--------+--------+--------+--------+--------+---- ----+--------+
Você pode pegar qualquer sequência que quiser. Se relaxarmos as bordas uma vez, o que obtemos? Obtemos a distância da fonte
para todos os outros vértices do caminho que usa no máximo 1 aresta. Agora vamos relaxar as arestas e atualizar os valores de d[]. Nós
pegar:
Não conseguimos atualizar alguns vértices, porque a condição d[u] + cost[u][v] < d[v] não correspondeu. Como dissemos
antes, encontrávamos os caminhos da origem para outros nós usando no máximo 1 aresta.
Nossa 3ª iteração atualizará apenas o vértice 5, onde d[5] será 8. Nosso gráfico ficará assim:
Depois disso, não importa quantas iterações fizermos, teremos as mesmas distâncias. Então, manteremos um sinalizador que verifica se alguma atualização
ocorre ou não. Se não ocorrer, simplesmente quebramos o loop. Nosso pseudocódigo será:
Para manter o controle do ciclo negativo, podemos modificar nosso código usando o procedimento descrito aqui. Nosso pseudocódigo
completo será:
fim para
d[fonte] := 0 para i de
1 a n-1
flag := false para
todas as arestas de (u,v) no gráfico se d[u] + custo[u]
[v] < d[v]
d[v] := d[u] + custo[u][v] pai[v] := u
sinalizador :=
verdadeiro fim se
fim para
se
sinalizador == falso
quebrar
fim para
todas as arestas de (u,v) em Graph se d[u] + cost[u]
[v] < d[v]
Retornar "Ciclo negativo detectado" fim se fim para
Retornar d
Caminho de impressão:
Para imprimir o caminho mais curto para um vértice, iteraremos de volta ao seu pai até encontrarmos NULL e então imprimiremos os vértices.
O pseudocódigo será:
Procedimento PathPrinting(u) v :=
parent[u] se v ==
NULL
retornar
PathPrinting(v) imprimir
-> u
Complexidade:
*
Como precisamos relaxar as arestas no máximo (V-1) vezes, a complexidade de tempo desse algoritmo será igual a O(VE), onde E denota
o número de arestas, se usarmos a lista de adjacência para representar o grafo. No entanto, se a matriz de adjacência for usada para
representar o grafo, a complexidade de tempo será O(V^3). O motivo é que podemos iterar por todas as arestas em tempo O(E) quando a
lista de adjacência é usada, mas leva tempo O(V^2) quando a matriz de adjacência é usada.
aqui
Usando o algoritmo Bellman-Ford, podemos detectar se há um ciclo negativo em nosso gráfico. Sabemos que, para descobrir o caminho mais
curto, precisamos relaxar todas as arestas do gráfico (V-1) vezes, onde V é o número de vértices em um gráfico.
Já vimos que neste exemplo, após iterações (V-1) , não podemos atualizar d[], não importa quantas iterações façamos. Ou podemos?
Se houver um ciclo negativo em um gráfico, mesmo após (V-1) iterações, podemos atualizar d[]. Isso acontece porque para cada iteração,
atravessar o ciclo negativo sempre diminui o custo do caminho mais curto. É por isso que o algoritmo Bellman-Ford limita o número de iterações
para (V-1). Se usássemos o Algoritmo de Dijkstra aqui, estaríamos presos em um loop infinito. No entanto, vamos nos concentrar em encontrar
o ciclo negativo.
Vamos escolher o vértice 1 como a fonte. Após aplicar o algoritmo de caminho mais curto de fonte única de Bellman-Ford ao gráfico, descobriremos
as distâncias da fonte para todos os outros vértices.
É assim que o gráfico se parece após (V-1) = 3 iterações. Deve ser o resultado, já que há 4 arestas, precisamos de no máximo 3 iterações para
descobrir o caminho mais curto. Então, ou esta é a resposta, ou há um ciclo de peso negativo no gráfico. Para descobrir isso, após (V-1) iterações,
fazemos mais uma iteração final e se a distância continuar a diminuir, significa que definitivamente há um ciclo de peso negativo no gráfico.
Para este exemplo: se verificarmos 2-3, d[2] + cost[2][3] nos dará 1, que é menor que d[3]. Então podemos concluir que há um ciclo
negativo em nosso gráfico.
Então como descobrimos o ciclo negativo? Fazemos uma pequena modificação no procedimento de Bellman-Ford:
fim para
todas as arestas de (u,v) em Graph se d[u] + cost[u][v]
< d[v]
Retornar "Ciclo negativo detectado" fim se
fim para
Retornar "Nenhum ciclo negativo"
É assim que descobrimos se há um ciclo negativo em um gráfico. Também podemos modificar o Algoritmo Bellman-Ford para manter o
controle de ciclos negativos.
No algoritmo Bellman-Ford, para descobrir o caminho mais curto, precisamos relaxar todas as arestas do gráfico. Esse processo é repetido
no máximo (V-1) vezes, onde V é o número de vértices no gráfico.
O número de iterações necessárias para descobrir o caminho mais curto da origem para todos os outros vértices depende da ordem
que selecionamos para relaxar as arestas.
Vejamos um exemplo:
Aqui, o vértice de origem é 1. Descobriremos a menor distância entre a origem e todos os outros vértices.
Podemos ver claramente que, para atingir o vértice 4, no pior caso, serão necessárias (V-1) arestas. Agora, dependendo da ordem em
que as arestas são descobertas, pode levar (V-1) vezes para descobrir o vértice 4. Não entendeu? Vamos usar Bellman-Ford
+--------+--------+--------+--------+
| Série | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Borda | 3->4 | 2->3 | 1->2 |
+--------+--------+--------+--------+
Podemos ver que nosso processo de relaxamento mudou apenas d[2]. Nosso gráfico ficará assim:
Segunda iteração:
Desta vez o processo de relaxamento mudou d[3]. Nosso gráfico ficará assim:
Terceira iteração:
Nossa terceira iteração finalmente descobriu o caminho mais curto de 1 para 4. Nosso gráfico ficará assim:
Então, levou 3 iterações para descobrir o caminho mais curto. Depois dessa, não importa quantas vezes relaxamos as bordas,
+--------+--------+--------+--------+
| Série | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Borda | 1->2 | 2->3 | 3->4 |
+--------+--------+--------+--------+
Teríamos:
Nossa primeira iteração encontrou o caminho mais curto da fonte para todos os outros nós. Outra sequência 1->2,
3->4, 2->3 é possível, o que nos dará o caminho mais curto após 2 iterações. Podemos chegar à decisão de que, não importa
como organizamos a sequência, não levará mais de 3 iterações para descobrir o caminho mais curto da fonte neste
exemplo.
Podemos concluir que, para o melhor caso, levará 1 iteração para descobrir o caminho mais curto da fonte. Para o pior
nesse caso, serão necessárias (V-1) iterações, e é por isso que repetimos o processo de relaxamento (V-1) vezes.
3. Calcular
Delx =| x2 – x1 |
Atraso = | y2 – y1 |
Se p < 0 então
X1 = x1 + 1
Pote(x1,y1)
P = p+ 2dely
Outro
X1 = x1 + 1
Y1 = y1 + 1
Gráfico(x1,y1)
P = p + 2dely – 2 * delx
Fim se
Fim para
6. FIM
Código fonte:
/ * Programa AC para implementar o algoritmo de desenho de linha de Bresenham para |m|<1 */ #include<stdio.h>
#incluir<conio.h>
#incluir<gráficos.h>
#incluir<matemática.h>
gdriver=DETECTAR,gmode; int
x1,y1,x2,y2,delx,dely,p,i; initgraph(&gdriver,&gmode,"c:
\\TC\\BGI");
putpixel(x1,y1,VERMELHO);
delx=fabs(x2-x1);
dely=fabs(y2-y1); p=(2*dely)-
delx; para(i=0;i<delx;i++)
{ se(p<0) { x1=x1+1;
putpixel(x1,y1,RED); p=p+(2*dely); }
senão { x1=x1+1;
y1=y1+1;
putpixel(x1,y1,RED); p=p+(2*dely)-
(2*delx); } } getch(); closegraph();
retornar 0; }
Delx =| x2 – x1 |
Dely = | y2 – y1 | 4.
Obtenha o parâmetro de decisão inicial como P =
2 * delx – dely 5.
Para I = 0 para dely no passo de 1
Se p < 0
então y1 = y1 + 1
Pote(x1,y1)
P = p+ 2delx
Outro
X1 = x1 + 1
Y1 = y1 + 1
Gráfico(x1,y1)
P = p + 2delx – 2 * dely
Fim se
Fim para
6. FIM
Código fonte:
/ * Programa AC para implementar o algoritmo de desenho de linha de Bresenham para |m|>1 */ #include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<math.h> int
main() { int
gdriver=DETECT,gmode; int
x1,y1,x2,y2,delx,dely,p,i; initgraph(&gdriver,&gmode,"c:
\\TC\\BGI"); printf("Digite os pontos iniciais: "); scanf("%d",&x1);
scanf("%d",&y1); printf("Digite os pontos finais: ");
scanf("%d",&x2);
scanf("%d",&y2);
putpixel(x1,y1,RED); delx=fabs(x2-x1); dely=fabs(y2-
y1); p=(2*delx)-dely;
for(i=0;i<delx;i++){ if(p<0)
{ y1=y1+1; putpixel(x1,y1,RED);
p=p+(2*delx); } senão
{ x1=x1+1; y1=y1+1;
putpixel(x1,y1,RED);
p=p+(2*delx)-(2*dely); } } getch();
closegraph();
return 0; }
De Floyd-Warshall O algoritmo é para encontrar os caminhos mais curtos em um grafo ponderado com pesos de aresta positivos ou negativos.
Uma única execução do algoritmo encontrará os comprimentos (pesos somados) dos caminhos mais curtos entre todos os pares de
vértices. Com uma pequena variação, ele pode imprimir o caminho mais curto e pode detectar ciclos negativos em um gráfico.
Floyd-Warshall é um algoritmo de Programação Dinâmica.
Vamos dar uma olhada em um exemplo. Vamos aplicar o algoritmo de Floyd-Warshall neste gráfico:
A primeira coisa que fazemos é pegar duas matrizes 2D. Essas são matrizes de adjacência. O tamanho das matrizes será
o número total de vértices. Para nosso gráfico, tomaremos matrizes 4 * 4. A Matriz de Distância armazenará o
distância mínima encontrada até agora entre dois vértices. A princípio, para as arestas, se houver uma aresta entre uv e o
distância/peso é w, armazenaremos: distância[u][v] = w. Para todas as arestas que não existem, colocaremos infinito.
A Matriz de Caminho é para regenerar o caminho de distância mínima entre dois vértices. Então, inicialmente, se houver um caminho
entre u e v, vamos colocar path[u][v] = u. Isso significa que a melhor maneira de chegar ao vértice-v a partir do vértice-u
é usar a aresta que conecta v com u. Se não houver caminho entre dois vértices, vamos colocar N lá
indicando que não há caminho disponível agora. As duas tabelas para nosso gráfico ficarão assim:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| |1|2|3|4| | |1| 2 |3|4|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 6 | 15 | |1|E|1|1|1|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | inf | 0 | -2 | inf | |2|E|E|2|E|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | inf | inf | 0 | 2 | |3|E|E|E|3|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | inf | inf | 0 | |4|4|E|E|E|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distância caminho
Como não há loop, as diagonais são definidas como N. E a distância do próprio vértice é 0.
Para aplicar o algoritmo Floyd-Warshall, vamos selecionar um vértice médio k. Então, para cada vértice i, vamos
verifique se podemos ir de i para k e depois k para j, onde j é outro vértice e minimizar o custo de ir de i para j. Se
a distância atual[i][j] é maior que distância[i][k] + distância[k][j], vamos colocar distância[i][j] igual a
a soma dessas duas distâncias. E o path[i][j] será definido como path[k][j], pois é melhor ir de i para k,
e então k para j. Todos os vértices serão selecionados como k. Teremos 3 loops aninhados: para k indo de 1 a 4, i indo de
1 a 4 e j indo de 1 a 4. Vamos verificar:
Então, o que estamos basicamente verificando é, para cada par de vértices, obtemos uma distância menor ao passar por outro
vértice? O número total de operações para o nosso gráfico será 4 * 4 * 4 = 64. Isso significa que faremos esta verificação
64 vezes. Vamos dar uma olhada em algumas delas:
Quando k = 1, i = 2 e j = 3, distância[i][j] é -2, que não é maior que distância[i][k] + distância[k][j] = -2 + 0 = -2.
Portanto, permanecerá inalterado. Novamente, quando k = 1, i = 4 e j = 2, distância [i] [j] = infinito, que é maior que
distância[i][k] + distância[k][j] = 1 + 3 = 4. Então colocamos distância[i][j] = 4, e colocamos caminho[i][j] = caminho[k][j] = 1. O que
isto significa que, para ir do vértice-4 ao vértice-2, o caminho 4->1->2 é mais curto que o caminho existente. É assim que nós
preencha ambas as matrizes. O cálculo para cada etapa é mostrado aqui. Após fazer as alterações necessárias, nossas matrizes
ficará assim:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| |1|2|3|4| | |1| 2 |3|4|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
|1|0|3|1|3| |1|E|1|2|3|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | 1 | 0 | -2 | 0 | |2|4|E|2|3|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
|3|3|6|0|2| |3|4|1|N|3|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
|4|1|4|2|0| |4|4|1|2|E|
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distância caminho
Esta é a nossa matriz de distância mais curta. Por exemplo, a distância mais curta de 1 a 4 é 3 e a distância mais curta
entre 4 e 3 é 2. Nosso pseudocódigo será:
Imprimindo o caminho:
Para imprimir o caminho, verificaremos a matriz Path . Para imprimir o caminho de u a v, começaremos em path[u][v]. Definiremos
continue mudando v = path[u][v] até encontrarmos path[u][v] = u e empilhar todos os valores de path[u][v] em uma pilha. Depois
encontrando u, imprimiremos u e começaremos a retirar itens da pilha e imprimi-los. Isso funciona porque a matriz de caminho
armazena o valor do vértice que compartilha o caminho mais curto para v de qualquer outro nó. O pseudocódigo será:
s = Pilha()
[Link](destino) enquanto
Path[fonte][destino] não é igual a fonte [Link](Path[fonte][destino]) destino := Path[fonte]
[destino] fim enquanto
Para descobrir se há um ciclo de aresta negativo, precisamos verificar a diagonal principal da matriz de distância . Se qualquer valor na diagonal
for negativo, isso significa que há um ciclo negativo no gráfico.
Complexidade:
Na matemática combinatória, os números catalães formam uma sequência de números naturais que ocorrem em vários problemas de
contagem, frequentemente envolvendo objetos definidos recursivamente. Os números de Catalan em inteiros não negativos n são um conjunto de
números que surgem em problemas de enumeração de árvores do tipo, 'De quantas maneiras um n-gono regular pode ser dividido em n-2
triângulos se diferentes orientações forem contadas separadamente?'
1. O número de maneiras de empilhar moedas em uma fileira inferior que consiste em n moedas consecutivas em um plano, de modo que
nenhuma moeda possa ser colocada nos dois lados das moedas inferiores e cada moeda adicional deve estar acima de duas outras
moedas, é o enésimo número catalão.
2. O número de maneiras de agrupar uma sequência de n pares de parênteses, de modo que cada parêntese aberto tenha um
correspondente aos parênteses fechados, é o enésimo número catalão.
3. O número de maneiras de cortar um polígono convexo de n+2 lados em um plano em triângulos conectando vértices com linhas retas e não
interseccionais é o n-ésimo número catalão. Esta é a aplicação na qual Euler estava interessado.
Usando numeração baseada em zero, o enésimo número catalão é dado diretamente em termos de coeficientes binomiais pela seguinte
equação.
paralelo para j = 1 a n
C[i][j] = 0 para k =
1 para n
C[i][j] = C[i][j] + A[i][k]*B[k][j]
retornar C
p-merge-sort(A,p,r,B,s) n = r-p+1 se
n==1
sincronizar p-merge(T,1,q_prime,q_prime+1,n,B,s)
p-merge(T,p1,r1,p2,r2,A,p3) n1 = r1-p1+1 n2
= r2-p2+1 se n1<n2
// verifique se n1>=n2
permutar p1 e p2 permutar r1 e
r2 permutar n1 e n2 se n1==0 //
ambos vazios?
retornar
senão
q1 = andar((p1+r1)/2) q2 = busca-
dicotômica(T[q1],T,p2,r2) q3 = p3 + (q1-p1) + (q2-p2)
retornar sup
Este algoritmo é um processo de duas etapas. Primeiro, criamos uma matriz auxiliar lps[] e então usamos essa matriz para pesquisar o padrão.
Pré-processamento :
1. Pré-processamos o padrão e criamos um array auxiliar lps[] que é usado para pular caracteres enquanto
correspondência.
2. Aqui lps[] indica o prefixo próprio mais longo que também é sufixo. Um prefixo próprio é um prefixo no qual a string inteira não está incluída. Por
“ “
exemplo, os prefixos da string ABC são “AB”. Os sufixos da string ”, “A”, “AB” e “ABC”. Os prefixos próprios são ”, “A” e
“
são ”, “C”, “BC” e “ABC”.
Procurando
1. Continuamos combinando os caracteres txt[i] e pat[j] e continuamos incrementando i e j enquanto pat[j] e txt[i] continuam
correspondência.
2. Quando vemos uma incompatibilidade, sabemos que os caracteres pat[0..j-1] correspondem a txt[i-j+1…i-1]. Também sabemos que
lps[j-1] é a contagem de caracteres de pat[0…j-1] que são prefixo e sufixo próprios. Disto podemos concluir que não precisamos corresponder
esses caracteres lps[j-1] com txt[ij…i-1] porque sabemos que esses caracteres corresponderão de qualquer maneira.
Implementação em Java
[Link]([Link]([Link](), [Link]()));
}
lps[0] = 0; int
j = 0; para(int
i =1;i<[Link];i++){ se(str[j] == str[i])
{ lps[i] = j+1; j++;
i++; }
senão{ se(j!=0){ j
= lps[j-1]; }
}
}
retornar lps;
}
senão{ se(j!=0){ j
= lps[j-1]; }senão{ i+
+;
}
}
}
if(j==[Link]) retorna
verdadeiro;
retorna falso;
}
1. Insira
2. Remove
3. Substituir
Por exemplo
Para resolver este problema, usaremos uma matriz 2D dp[n+1][m+1] onde n é o comprimento da primeira string e m é o
comprimento da segunda string. Para nosso exemplo, se str1 for azcef e str2 for abcdef, então nossa matriz será dp[6][7]e
nossa resposta final será armazenada em dp[5][6].
Para dp[1][1] temos que verificar o que podemos fazer para converter a em a. Será 0. Para dp[1][2] temos que verificar o que podemos fazer
fazemos para converter a em ab. Será 1 porque temos que inserir b. Então, após a primeira iteração, nossa matriz ficará assim
Para iteração 2
Para dp[2][1] temos que verificar que para converter az para a precisamos remover z, portanto dp[2][1] será 1. Similarmente para
dp[2][2] precisamos substituir z por b, portanto dp[2][2] será 1. Então, após a 2ª iteração, nosso array dp[] ficará assim.
Implementação em Java
dp[i][j] = j; senão
se(j==0) dp[i][j]
= i; senão
se([Link](i-1) == [Link](j-1)) dp[i][j] = dp[i-1][j-1];
senão{ dp[i][j] = 1 +
} retornar dp[[Link]()][[Link]()];
}
Complexidade de tempo
O(n^2)
Definição 1: Um problema de otimização ÿ consiste em um conjunto de instâncias ÿÿ. Para cada instância ÿÿÿÿ há um conjunto ÿÿ de
soluções e uma função objetivo fÿ : ÿÿ ÿ ÿÿ0 que atribui um valor real positivo a cada solução.
Dizemos que OPT(ÿ) é o valor de uma solução ótima, A(ÿ) é a solução de um Algoritmo A para o problema ÿ e wA(ÿ)=fÿ(A(ÿ)) seu valor.
Definição 2: Um algoritmo online A para um problema de minimização ÿ tem uma razão competitiva de r ÿ 1 se houver uma constante
ÿÿÿ com
wA(ÿ) ÿ r ÿ OPT(&sigma)
para todas as instâncias ÿÿÿÿ então A é chamado de algoritmo online estritamente r-competitivo .
Prova: No início de cada fase (exceto na primeira), o FWF tem uma falta de cache e limpa o cache. Isso significa que temos k páginas vazias.
Em cada fase, há um máximo de k páginas diferentes solicitadas, então não haverá despejo durante a fase. Então, o FWF é um algoritmo
de marcação.
Vamos supor que LRU não seja um algoritmo de marcação. Então há uma instância ÿ onde LRU marcou uma página x na fase i despejada.
Seja ÿt a solicitação na fase i onde x é despejado. Como x é marcado, tem que haver uma solicitação anterior ÿt* para x na mesma fase, então
t* < t. Depois de t* x é a página mais nova do cache, então para ser despejado em t a sequência ÿt*+1,...,ÿt tem que solicitar pelo menos k de x
páginas diferentes. Isso implica que a fase i solicitou pelo menos k+1 páginas diferentes, o que é contraditório à definição da fase. Então
LRU tem que ser um algoritmo de marcação.
Prova: Seja ÿ uma instância para o problema de paginação e l o número de fases para ÿ. Se l = 1, então todo algoritmo de marcação é ótimo e
o algoritmo offline ótimo não pode ser melhor.
Assumimos que l ÿ 2. O custo de cada algoritmo de marcação, por exemplo ÿ, é limitado acima por l ÿ k porque em cada fase um algoritmo de
marcação não pode remover mais de k páginas sem remover uma página marcada.
Agora tentamos mostrar que o algoritmo offline ótimo despeja pelo menos k+l-2 páginas para ÿ, k na primeira fase e pelo menos uma para
cada fase seguinte, exceto a última. Para prova, vamos definir l-2 subsequências disjuntas de ÿ.
A subsequência i ÿ {1,...,l-2} começa na segunda posição da fase i+1 e termina na primeira posição da fase i+2.
Seja x a primeira página da fase i+1. No início da subsequência i há uma página x e no máximo k-1 páginas diferentes no cache do
algoritmo offline ótimo. Na subsequência i há k requisições de página diferentes de x, então o algoritmo offline ótimo tem que despejar pelo
menos uma página para cada subsequência. Como no início da fase 1 o cache ainda está vazio, o algoritmo offline ótimo causa k remoções
durante a primeira fase. Isso mostra que
Não existe uma constante r para a qual um algoritmo online A é r-competitivo, chamamos A de não competitivo.
Prova: Seja l ÿ 2 uma constante, k ÿ 2 o tamanho do cache. As diferentes páginas do cache são numeradas 1,...,k+1. Observamos a
seguinte sequência:
A primeira página 1 é solicitada l vezes que a página 2 e assim por diante. No final, há (l-1) solicitações alternadas para a página k e k+1.
LFU e LIFO preenchem seu cache com páginas 1-k. Quando a página k+1 é solicitada, a página k é despejada e vice-versa. Isso significa
que cada solicitação da subsequência (k,k+1)l-1 despeja uma página. Além disso, há k-1 faltas de cache para o primeiro uso das páginas 1-
(k-1). Então LFU e LIFO despejam exatamente k-1+2(l-1) páginas.
Agora devemos mostrar que para cada constante ÿÿÿ e cada constante r ÿ 1 existe um l tal que
que é igual a
Para satisfazer essa desigualdade, você só precisa escolher l suficientemente grande. Então LFU e LIFO não são competitivos.
Proposição 1.7: Não existe algoritmo online determinístico r-competitivo para paginação com r < k.
Fontes
Material Básico
Leitura Adicional
Código fonte
Em vez de começar com uma definição formal, o objetivo é abordar esses tópicos por meio de uma série de exemplos, introduzindo
definições ao longo do caminho. A seção de comentários Teoria consistirá de todas as definições, teoremas e proposições para dar a você
todas as informações para procurar aspectos específicos mais rapidamente.
As fontes da seção de comentários consistem no material base usado para este tópico e informações adicionais para leitura posterior. Além disso,
você encontrará os códigos-fonte completos para os exemplos lá. Por favor, preste atenção que para tornar o código-fonte para os exemplos mais
legível e mais curto, ele se abstém de coisas como tratamento de erros, etc. Ele também passa alguns recursos de linguagem específicos
que obscureceriam a clareza do exemplo, como uso extensivo de bibliotecas avançadas, etc.
Paginação
O problema de paginação surge da limitação de espaço finito. Vamos supor que nosso cache C tenha k páginas. Agora queremos processar uma
sequência de m solicitações de página que devem ter sido colocadas no cache antes de serem processadas. Claro que se m<=k então colocamos
todos os elementos no cache e funcionará, mas geralmente é m>>k.
Dizemos que uma solicitação é um cache hit, quando a página já está no cache, caso contrário, é chamado de cache miss. Nesse caso,
devemos trazer a página solicitada para o cache e despejar outra, assumindo que o cache esteja cheio. O objetivo é um cronograma de
despejo que minimize o número de despejos.
Abordagem Offline
Para a primeira abordagem, veja o tópico Applications of Greedy Technique. Seu terceiro Example Offline Caching considera as cinco
primeiras estratégias acima e fornece um bom ponto de entrada para o seguinte.
FWF() : Estratégia("FWF") { }
// após a primeira página vazia todas as outras devem estar vazias else
if(cache[i] == emptyPage) return i;
retornar 0;
}
O código-fonte completo está disponível aqui. Se reutilizarmos o exemplo do tópico, obteremos a seguinte saída:
Estratégia: FWF
X X x
Facebook b X
e dfff b e
c c X X x
Embora o LFD seja ótimo, o FWF tem menos falhas de cache. Mas o objetivo principal era minimizar o número de
despejos e para FWF cinco erros significam 15 despejos, o que a torna a pior escolha para este exemplo.
Abordagem Online
Agora queremos abordar o problema online de paginação. Mas primeiro precisamos entender como fazê-lo.
Obviamente, um algoritmo online não pode ser melhor do que o algoritmo offline ideal. Mas quão pior ele é? Nós
precisa de definições formais para responder a essa pergunta:
Definição 1.1: Um problema de otimização ÿ consiste em um conjunto de instâncias ÿÿ. Para cada instância ÿÿÿÿ existe um
conjunto ÿÿ de soluções e uma função objetivo fÿ : ÿÿ ÿ ÿÿ0 que atribui um valor real positivo a cada solução.
Dizemos que OPT(ÿ) é o valor de uma solução ótima, A(ÿ) é a solução de um Algoritmo A para o problema ÿ e
wA(ÿ)=fÿ(A(ÿ)) seu valor.
Definição 1.2: Um algoritmo online A para um problema de minimização ÿ tem uma razão competitiva de r ÿ 1 se houver um
constante ÿÿÿ com
wA(ÿ) ÿ r ÿ OPT(ÿ)
para todas as instâncias ÿÿÿÿ então A é chamado de algoritmo online estritamente r-competitivo .
Então a questão é quão competitivo é nosso algoritmo online comparado a um algoritmo offline ótimo. Em seu famoso livro Allan
Borodin e Ran El-Yaniv usaram outro cenário para descrever a situação de paginação online:
Há um adversário maligno que conhece seu algoritmo e o algoritmo offline ideal. Em cada etapa, ele tenta solicitar uma página que seja
pior para você e, simultaneamente, melhor para o algoritmo offline. O fator competitivo do seu algoritmo é o fator de quão mal seu algoritmo
se saiu contra o algoritmo offline ideal do adversário. Se você quiser tentar ser o adversário, pode tentar o Adversary Game (tente vencer
as estratégias de paginação).
Algoritmos de Marcação
Em vez de analisar cada algoritmo separadamente, vamos analisar uma família especial de algoritmos on-line para o problema de
paginação, chamados algoritmos de marcação.
Seja ÿ=(ÿ1,...,ÿp) uma instância para nosso problema e k nosso tamanho de cache, então ÿ pode ser dividido em fases:
A fase 1 é a subsequência máxima de ÿ desde o início até que o máximo de k páginas diferentes sejam solicitadas
A fase i ÿ 2 é a subsequência máxima de ÿ do final da fase i-1 até que o máximo de k páginas diferentes sejam solicitadas
Um algoritmo de marcação (implícita ou explicitamente) mantém se uma página está marcada ou não. No início de cada fase, todas as páginas
estão desmarcadas. Se uma página for solicitada durante uma fase, ela será marcada. Um algoritmo é um algoritmo de marcação se ele
nunca remover uma página marcada do cache. Isso significa que as páginas que são usadas durante uma fase não serão removidas.
Prova: No início de cada fase (exceto na primeira), o FWF tem uma falta de cache e limpa o cache. Isso significa que temos k páginas
vazias. Em cada fase, há um máximo de k páginas diferentes solicitadas, então não haverá despejo durante a fase. Então, o FWF é
um algoritmo de marcação.
Vamos supor que LRU não seja um algoritmo de marcação. Então há uma instância ÿ onde LRU marcou uma página x na fase i
despejada. Seja ÿt a solicitação na fase i onde x é despejado. Como x é marcado, tem que haver uma solicitação anterior ÿt* para x na mesma
fase, então t* < t. Depois de t* x é a página mais nova do cache, então para ser despejado em t a sequência ÿt*+1,...,ÿt tem que solicitar pelo
menos k de x páginas diferentes. Isso implica que a fase i solicitou pelo menos k+1 páginas diferentes, o que é contraditório à definição
da fase. Então LRU tem que ser um algoritmo de marcação.
Prova: Seja ÿ uma instância para o problema de paginação e l o número de fases para ÿ. Se l = 1, então todo algoritmo de marcação é ótimo e
o algoritmo offline ótimo não pode ser melhor.
Assumimos que l ÿ 2. O custo de cada algoritmo de marcação, por exemplo, ÿ é limitado acima por l ÿ k porque em cada fase um algoritmo de
marcação não pode remover mais de k páginas sem remover uma página marcada.
Agora tentamos mostrar que o algoritmo offline ótimo despeja pelo menos k+l-2 páginas para ÿ, k na primeira fase e pelo menos uma para
cada fase seguinte, exceto a última. Para prova, vamos definir l-2 subsequências disjuntas de ÿ.
A subsequência i ÿ {1,...,l-2} começa na segunda posição da fase i+1 e termina na primeira posição da fase i+2.
Seja x a primeira página da fase i+1. No início da subsequência i há uma página x e no máximo k-1 páginas diferentes no cache do algoritmo
offline ótimo. Na subsequência i há k requisições de página diferentes de x, então o algoritmo offline ótimo tem que despejar pelo menos uma
página para cada subsequência. Como no início da fase 1 o cache ainda está vazio, o algoritmo offline ótimo causa k remoções durante a
primeira fase. Isso mostra que
Exercício: Mostre que FIFO não é um algoritmo de marcação, mas estritamente k-competitivo.
Não existe uma constante r para a qual um algoritmo online A é r-competitivo, chamamos A de não competitivo
Prova: Seja l ÿ 2 uma constante, k ÿ 2 o tamanho do cache. As diferentes páginas do cache são numeradas 1,...,k+1. Observamos a
seguinte sequência:
A primeira página 1 é solicitada l vezes que a página 2 e assim por diante. No final, há (l-1) solicitações alternadas para a página k e k+1.
LFU e LIFO preenchem seu cache com páginas 1-k. Quando a página k+1 é solicitada, a página k é despejada e vice-versa. Isso significa
que cada solicitação da subsequência (k,k+1)l-1 despeja uma página. Além disso, há k-1 faltas de cache para o primeiro uso das páginas 1-(k-1).
Então LFU e LIFO despejam exatamente k-1+2(l-1) páginas.
Agora devemos mostrar que para cada constante ÿÿÿ e cada constante r ÿ 1 existe um l tal que
que é igual a
Para satisfazer essa desigualdade, você só precisa escolher l suficientemente grande. Então LFU e LIFO não são competitivos.
Proposição 1.7: Não existe algoritmo online determinístico r-competitivo para paginação com r < k.
A prova para esta última proposição é bastante longa e baseada na declaração de que LFD é um algoritmo offline ótimo. O leitor
interessado pode procurá-la no livro de Borodin e El-Yaniv (veja as fontes abaixo).
A questão é se poderíamos fazer melhor. Para isso, temos que deixar a abordagem determinística para trás e começar a randomizar nosso
algoritmo. Claramente, é muito mais difícil para o adversário punir seu algoritmo se ele for randomizado.
algoritmo de classificação é estável se preserva a ordem relativa de elementos iguais após a classificação.
Estabilidade
Um algoritmo de classificação está em vigor se ele classifica usando apenas memória auxiliar O(1) (sem contar a matriz que precisa
No lugar
ser classificada).
Um algoritmo de classificação tem uma complexidade de tempo no melhor caso de O(T(n)) se seu tempo de execução for pelo
Melhor complexidade de caso
menos T(n) para todas as entradas possíveis.
Complexidade Um algoritmo de classificação tem uma complexidade média de tempo de caso de O(T(n)) se seu tempo de execução, calculado
média do caso sobre todas as entradas possíveis, for T(n).
Um algoritmo de classificação tem uma complexidade de tempo de pior caso de O(T(n)) se seu tempo de execução for no máximo
Pior caso de complexidade
T(n).
Portanto, um algoritmo de classificação é considerado estável se dois objetos com chaves iguais aparecem na mesma ordem na saída classificada em que aparecem na
A classificação instável pode gerar a mesma saída que a classificação estável, mas nem sempre.
Mesclar classificação
Classificação de radix
Tim classificar
Classificação de pilha
Classificação rápida
Parâmetro Descrição
Estável Sim
No lugar Sim
O BubbleSort compara cada par sucessivo de elementos em uma lista não ordenada e inverte os elementos se eles não estiverem em ordem.
O exemplo a seguir ilustra a classificação por bolhas na lista {6,5,3,1,8,7,2,4} (os pares que foram comparados em cada etapa são encapsulados
em '**'):
{6,5,3,1,8,7,2,4}
{**5,6** ,3,1,8,7,2,4} -- 5 < 6 -> trocar
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> trocar
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> trocar
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> sem troca
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> trocar
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> trocar
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> trocar
Após uma iteração pela lista, temos {5,3,1,6,7,2,4,8}. Note que o maior valor não classificado no array (8 neste caso) sempre alcançará sua
posição final. Assim, para ter certeza de que a lista está classificada, devemos iterar n-1 vezes para listas de comprimento n.
Gráfico:
void bubbleSort(vetor<int>números) {
}
}
}
}
Implementação C
longo c, d, t;
/ * Trocando */
para
= lista[d];
lista[d] = lista[d+1]; lista[d+1]
= t;
}
}
}
}
longo c, d, t;
/ * Trocando */
para
= * (lista + d ); * (lista
+ d ) = * (lista + d + 1 ); * (lista + d + 1) = t;
}
}
}
}
}
}
}
SortBubble(entrada);
retorna entrada;
}
}
lista_de_entrada = [10,1,2,11]
para i em intervalo(len(lista_de_entrada)):
para j em intervalo(i):
se int(lista_de_entrada[j]) > int(lista_de_entrada[j+1]):
lista_de_entrada[j],lista_de_entrada[j+1] = lista_de_entrada[j+1],lista_de_entrada[j]
imprimir lista_de_entrada
} imprimirNúmeros(matriz);
}
}
int temp;
temp = matriz[i];
matriz[i] = matriz[j]; matriz[j]
= temp;
}
}
}
} } enquanto (trocado);
}
var a = [3, 203, 34, 746, 200, 984, 198, 764, 9];
bubbleSort(a);
[Link](a); //registros [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]
Merge Sort é um algoritmo de divisão e conquista. Ele divide a lista de entrada de comprimento n pela metade sucessivamente até que haja n
listas de tamanho 1. Então, pares de listas são mesclados com o menor primeiro elemento entre o par de listas sendo adicionado em cada etapa.
Por meio de mesclagens sucessivas e por meio da comparação dos primeiros elementos, a lista ordenada é construída.
Um exemplo:
A recorrência acima pode ser resolvida usando o método Recurrence Tree ou o método Master. Ela se enquadra no caso II do Método Master
e a solução da recorrência é ÿ(nLogn). A complexidade de tempo do Merge Sort é ÿ(nLogn) em todos os 3 casos (pior, médio e melhor), pois o
merge sort sempre divide o array em duas metades e leva tempo linear para mesclar as duas metades.
Estável: Sim
importar "fmt"
} m := (len(a)) / 2
f := mesclarSort(a[:m]) s :=
mesclarSort(a[m:])
retornar mesclar(f, s)
}
eu++
}
}
retornar um
}
func main() { a :=
[]int{75, 12, 34, 45, 0, 123, 32, 56, 32, 99, 123, 11, 86, 33} [Link](a)
[Link](mergeSort(a))
}
i=0;
j=0;
for(k=l; k<=h; k++) { //processo de combinação de dois arrays ordenados
se(arr1[i]<=arr2[j]) arr[k]=arr1[i+
+]; senão arr[k]=arr2[j++];
retornar 0;
}
int médio;
se(baixo<alto)
{ médio=(baixo+alto)/2;
// Dividir e Conquistar
merge_sort(arr,baixo,médio);
merge_sort(arr,médio+1,alto);
// Combine
merge(arr,baixo,médio,alto);
}
retornar 0;
}
C# Mesclar classificação
151
Notas de algoritmos do [Link] para profissionais
Machine Translated by Google
eu = 0;
j = 0;
var k = l;
entrada[k] = esquerda[i];
i++;
}
outro {
entrada[k] = direita[j]; j++;
} k++;
}
entrada[k] = esquerda[i];
i++;
k++;
}
}
}
se (l < r) {
int m = l + (r - l) / 2;
SortMerge(entrada, l, m);
SortMerge(entrada, m + 1, r);
Mesclar(entrada, l, m, r);
}
}
classe pública MergeSort < T estende Comparável < T >> implementa InPlaceSort < T > {
@Override
privado void merge(T[] a, T[] b, int baixo, int alto, int médio) { int i = baixo; int j =
médio + 1;
// Selecionamos o menor elemento dos dois. E então o colocamos em b for (int k = low; k <=
high; k++) {
}
} senão se (j > alto && i <= médio) { b[k] = a[i+
+]; } senão se (i >
médio && j <= alto) { b[k] = a[j++];
}
}
}}}
ordenado(A)
mid = len(A) / 2
retornar mesclar(mergeSort(A[:mid]), mesclarSort(A[mid:]))
se __nome__ == "__principal__":
# Gere 20 números aleatórios e classifique-os
A = [randint(1, 100) para i em xrange(20)] imprimir
mergeSort(A)
público MergeSortBU() { }
privado estático vazio mesclar(Comparable[] arrayToSort, Comparable[] aux, int lo,int mid, int hi) {
}
}
público estático vazio classificar(Comparable[] arrayToSort, Comparable[] aux, int lo, int hi) {
int N = [Link]; for
(int sz = 1; sz < N; sz = sz + sz) { for (int low = 0; low < N;
low = low + sz + sz) { [Link]("Tamanho:"+ sz );
mesclar(arrayToSort, aux, low, low + sz
-1 ,[Link](low + sz + sz - 1, N - 1)); imprimir(arrayToSort);
}
}
}
[Link](buffer);
}
bucket[i - minValue].Adicionar(i);
}
se ([Link] > 0)
{
para cada (int t em b) {
entrada[k] = t; k+
+;
}
}
}
}
SortBucket( entrada de
referência); retorna entrada;
}
}
Classificação rápida é um algoritmo de classificação que escolhe um elemento ("o pivô") e reordena o array formando duas partições
de modo que todos os elementos menores que o pivô venham antes dele e todos os elementos maiores venham depois. O algoritmo é
então aplicado recursivamente às partições até que a lista seja classificada.
Este esquema escolhe um pivô que é tipicamente o último elemento no array. O algoritmo mantém o índice para colocar o pivô na variável i e cada vez que ele encontra
um elemento menor ou igual ao pivô, este índice é incrementado e aquele elemento seria colocado antes do pivô.
eu := eu + 1
troque A[i] com A[alto] retorne i
Ele usa dois índices que começam nas extremidades do array que está sendo particionado, então se movem em direção um ao outro, até que
detectem uma inversão: um par de elementos, um maior ou igual ao pivô, um menor ou igual, que estão na ordem errada em relação um ao
outro. Os elementos invertidos são então trocados. Quando os índices se encontram, o algoritmo para e retorna o índice final. O esquema de Hoare é
mais eficiente que o esquema de partição de Lomuto porque ele faz três vezes menos trocas em média, e ele cria partições eficientes mesmo quando
todos os valores são iguais.
Partição:
eu := eu + 1
fazer:
j := j - 1
enquanto A[j] > pivot do
se i >= j então
retorne j
imprimir quicksort([3,6,8,10,1,2,1])
se(baixo<alto) {
retornar i;
}
Passos
1. Construa uma matriz de trabalho C que tenha tamanho igual ao intervalo da matriz de entrada A.
2. Itere por A, atribuindo C[x] com base no número de vezes que x apareceu em A.
3. Transforme C em uma matriz onde C[x] se refere ao número de valores ÿ x iterando pela matriz,
atribuindo a cada C[x] a soma de seu valor anterior e todos os valores em C que vêm antes dele.
4. Itere para trás através de A, colocando cada valor em uma nova matriz classificada B no índice registrado em C. Isso é feito para um dado A[x]
atribuindo B[C[A[x]]] a A[x], e decrementando C[A[x]] caso haja valores duplicados na matriz original não classificada.
Pseudocódigo:
para x na entrada:
count[key(x)] += 1 total = 0
para i no
intervalo(k): oldCount =
count[i] count[i] = total total +=
oldCount
para x na entrada:
saída[contagem[chave(x)]] = x
contagem[chave(x)] += 1
retorno saída
se (maior != i) {
Heapify(entrada, n, maior);
}
}
Heapify(entrada, n, i);
SortHeap(entrada, [Link]);
retornar entrada;
}
}
Uma classificação ímpar-par ou brick sort é um algoritmo de classificação simples, que é desenvolvido para uso em processadores paralelos com
interconexão local. Ele funciona comparando todos os pares indexados ímpares/pares de elementos adjacentes na lista e, se um par estiver na ordem
errada, os elementos são trocados. A próxima etapa repete isso para pares indexados pares/ímpares. Então ele alterna entre etapas ímpares/
pares e pares/ímpares até que a lista seja classificada.
se n>2 então
1. aplicar merge(n/2) ímpar-par recursivamente à subsequência par a0, a2, ..., subsequência ímpar a1, a3, , ..., an-2 e para o
um-1
2. comparação [i : i+1] para todos os elementos i {1, 3, 5, 7, ..., n-3} senão comparação [0 : 1]
Implementação:
enquanto ( !classificar )
{
ordenar =
verdadeiro ; para (var i = 1 ; i < n - 1 ; i += 2 ) {
}
}
SortOddEven(entrada, [Link]);
retornar entrada;
}
}
defp min([primeiro|[segundo|cauda]]) do
min([menor(primeiro, segundo)|cauda]) fim
Seleçã[Link]([100,4,10,6,9,3])
|> [Link]
O algoritmo divide a lista de entrada em duas partes: a sublista de itens já classificados, que é construída da esquerda para a direita na frente (esquerda) da
lista, e a sublista de itens restantes a serem classificados que ocupam o restante da lista.
Inicialmente, a sublista ordenada está vazia e a sublista não ordenada é a lista de entrada inteira. O algoritmo prossegue encontrando o menor (ou
maior, dependendo da ordem de ordenação) elemento na sublista não ordenada, trocando-o (trocando-o) com o elemento não ordenado mais à esquerda
(colocando-o em ordem ordenada) e movendo os limites da sublista um elemento para a direita.
função select(lista[1..n], k)
para i de 1 a k
entrada[minId] = entrada[i];
entrada[i] = temp;
}
}
SortSelection(entrada, [Link]);
retornar entrada;
}
}
Binary Search é um algoritmo de busca de Dividir e Conquistar. Ele usa tempo O(log n) para encontrar a localização de um elemento em um
espaço de busca onde n é o tamanho do espaço de busca.
A Pesquisa Binária funciona dividindo pela metade o espaço de pesquisa a cada iteração após comparar o valor alvo com o valor médio do
espaço de pesquisa.
Para usar a Busca Binária, o espaço de busca deve ser ordenado (classificado) de alguma forma. Entradas duplicadas (aquelas que são
comparadas como iguais de acordo com a função de comparação) não podem ser distinguidas, embora não violem a propriedade Busca
Binária.
Convencionalmente, usamos menor que (<) como a função de comparação. Se a < b, retornará true. Se a não for menor que b e b não for menor
que a, a e b são iguais.
Exemplo de pergunta
Você é um economista, mas um bem ruim. Você recebeu a tarefa de encontrar o preço de equilíbrio (ou seja, o preço onde oferta = demanda)
para o arroz.
Lembre-se de que quanto mais alto for o preço definido, maior será a oferta e menor será a demanda
Como sua empresa é muito eficiente em calcular as forças de mercado, você pode obter instantaneamente a oferta e a demanda em unidades de
arroz quando o preço do arroz é definido em um determinado preço p.
Seu chefe quer o preço de equilíbrio o mais rápido possível, mas diz que o preço de equilíbrio pode ser um inteiro positivo que é no máximo 10^17
e que há garantia de haver exatamente 1 solução inteira positiva no intervalo. Então, comece seu trabalho antes que você o perca!
Você tem permissão para chamar as funções getSupply(k) e getDemand(k), que farão exatamente o que é declarado no problema.
Exemplo de explicação
Aqui nosso espaço de busca é de 1 a 10^17. Portanto, uma busca linear é inviável.
No entanto, observe que, à medida que k sobe, getSupply(k) aumenta e getDemand(k) diminui. Assim, para qualquer x > y,
getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y). Portanto, esse espaço de busca é monotônico e podemos usar a
Busca Binária.
Este algoritmo roda em tempo ~O(log 10^17) . Isso pode ser generalizado para tempo ~O(log S) onde S é o tamanho do espaço de busca, já que a cada
iteração do loop while , nós dividimos o espaço de busca pela metade (de [low:high] para [low:mid] ou [mid:high]).
se (x == a[médio]) { retornar
(médio); } senão se
(x <
a[médio]) { binsearch(a, x,
baixo, médio - 1); } senão { binsearch(a, x,
médio + 1,
alto);
}
}
n=[Link]();
int
m=[Link](); int t=0,p=0;
int h=1; int i,j; //função de cálculo do
valor hash for
(i=0;i<m-1;i+
+) h = (h*d)
%q; for (i=0;i<m;i++){ p = (d*p + [Link](i))%q;
t = (d*t + [Link](i))%q; }
// procurar o padrão
for(i=0;i<end-m;i++){ if(p==t){ //
se o valor do
hash corresponder, combine-os caractere por caractere for(j=0;j<m;j++) if([Link](j+i)!
=[Link](j))
break; if(j==m && i>=start)
} se(i<fim-m){ t
=(d*(t - [Link](i)*h) + [Link](i+m))%q; se(t<0) t=t+q;
}
}
}
Ao calcular o valor de hash, nós o dividimos por um número primo para evitar colisões. Depois de dividir por um número primo, as chances de
colisão serão menores, mas ainda há uma chance de que o valor de hash seja o mesmo para duas strings, então, quando obtemos uma
correspondência, temos que verificar caractere por caractere para garantir que obtivemos uma correspondência adequada.
Isso serve para recalcular o valor de hash do padrão, primeiro removendo o caractere mais à esquerda e depois adicionando o novo caractere
do texto.
1. Pior Caso
2. Caso médio
3. Melhor cenário
#incluir <stdio.h>
int i;
para (i=0; i<n; i++) {
se (arr[i] == x) retornar i;
retornar -1;
}
int principal()
{
int arr[] = {1, 10, 30, 15}; int x = 30; int
n = sizeof(arr)/
sizeof(arr[0]); printf("%d está presente no índice
%d", x, search(arr, n, x));
obterchar();
retornar 0;
}
Na análise do pior caso, calculamos o limite superior no tempo de execução de um algoritmo. Devemos saber o caso que faz com que o
número máximo de operações seja executado. Para a Busca Linear, o pior caso acontece quando o elemento a ser pesquisado (x
no código acima) não está presente no array. Quando x não está presente, as funções search() o comparam com todos os
elementos de arr[] um por um. Portanto, a complexidade de tempo do pior caso da busca linear seria ÿ(n)
Na análise de caso médio, pegamos todas as entradas possíveis e calculamos o tempo de computação para todas as entradas. Some
todos os valores calculados e divida a soma pelo número total de entradas. Devemos saber (ou prever) a distribuição dos casos. Para o
problema de busca linear, vamos supor que todos os casos sejam uniformemente distribuídos (incluindo o caso de x não estar presente
na matriz). Então, somamos todos os casos e dividimos a soma por (n+1). A seguir está o valor da complexidade do tempo do caso
médio.
Na análise do melhor caso, calculamos o limite inferior no tempo de execução de um algoritmo. Devemos saber o caso que faz com
que o número mínimo de operações seja executado. No problema de busca linear, o melhor caso ocorre quando x está presente no
primeiro local. O número de operações no melhor caso é constante (não dependente de n). Portanto, a complexidade de tempo no melhor
caso seria ÿ(1). Na maioria das vezes, fazemos a análise do pior caso para analisar algoritmos. Na pior análise, garantimos um limite
superior no tempo de execução de um algoritmo, o que é uma boa informação. A análise do caso médio não é fácil de fazer na maioria
dos casos práticos e raramente é feita. Na análise do caso médio, devemos saber (ou prever) a distribuição matemática de todas
as entradas possíveis. A análise do melhor caso é falsa. Garantir um limite inferior em um algoritmo não fornece nenhuma informação,
pois no pior caso, um algoritmo pode levar anos para ser executado.
Para alguns algoritmos, todos os casos são assintoticamente iguais, ou seja, não há pior e melhor caso. Por exemplo, Merge Sort.
Merge Sort faz operações ÿ(nLogn) em todos os casos. A maioria dos outros algoritmos de classificação tem pior e melhor caso. Por
exemplo, na implementação típica do Quick Sort (onde o pivô é escolhido como um elemento de canto), o pior ocorre quando o array
de entrada já está classificado e o melhor ocorre quando os elementos do pivô sempre dividem o array em duas metades. Para a
classificação por inserção, o pior caso ocorre quando o array é classificado inversamente e o melhor caso
baixo = 0;
alto = N -1;
enquanto(baixo < alto) {
alto = médio;
} if(array[low] == x) //
encontrado, índice é baixo else //
não
encontrado
Não tente retornar cedo comparando array[mid] com x para igualdade. A comparação extra só pode deixar o código mais lento. Note
que você precisa adicionar um a low para evitar ficar preso pela divisão inteira sempre arredondando para baixo.
Curiosamente, a versão acima da busca binária permite que você encontre a menor ocorrência de x no array. Se o array contiver
duplicatas de x, o algoritmo pode ser modificado levemente para retornar a maior ocorrência de x simplesmente adicionando ao
condicional if:
Observe que, em vez de usar mid = (low + high) / 2, também pode ser uma boa ideia tentar mid = low + ((high - low) / 2) para implementações como Java para
A busca linear é um algoritmo simples. Ele faz um loop pelos itens até que a consulta seja encontrada, o que o torna um algoritmo
linear - a complexidade é O(n), onde n é o número de itens a serem percorridos.
Por que O(n)? No pior cenário, você tem que passar por todos os n itens.
Pode ser comparado a procurar um livro em uma pilha de livros: você folheia todos eles até encontrar aquele que deseja.
+-------+---+---+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Texto | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Padrão | b | c | g | l |
+---------+---+---+---+---+
Esse padrão existe no texto. Então nossa busca por substring deve retornar 3, o índice da posição da qual esse padrão começa. Então
como nosso procedimento de busca por substring por força bruta funciona?
O que normalmente fazemos é: começamos do índice 0 do texto e do índice 0 do nosso *padrão e comparamos Texto[0] com Padrão[0]. Como
eles não são uma correspondência, vamos para o próximo índice do nosso texto e comparamos Texto[1] com Padrão[0]. Como isso é uma
correspondência, incrementamos o índice do nosso padrão e o índice do Texto também. Comparamos Texto[2] com Padrão[1]. Eles também
são uma correspondência. Seguindo o mesmo procedimento declarado antes, agora comparamos Texto[3] com Padrão[2]. Como eles não
correspondem, começamos da próxima posição onde começamos a encontrar a correspondência. Esse é o índice 2 do Texto. Comparamos
Texto[2] com Padrão[0]. Eles não correspondem. Então, incrementando o índice do Texto, comparamos Texto[3] com Padrão[0]. Eles
correspondem. Novamente Texto[4] e Padrão[1] correspondem, Texto[5] e Padrão[2] correspondem e Texto[6] e Padrão[3] correspondem.
Como chegamos ao fim do nosso Pattern, agora retornamos o índice do qual nossa correspondência começou, que é 3. Se nosso pattern
fosse: bcgll, isso significa que se o pattern não existisse em nosso text, nossa busca deveria retornar exception ou -1 ou qualquer outro valor
predefinido. Podemos ver claramente que, no pior caso, esse algoritmo levaria tempo O(mn) onde m é o comprimento do Text e n é o comprimento
do Pattern. Como reduzimos essa complexidade de tempo? É aqui que o KMP Substring Search Algorithm entra em cena.
O algoritmo de busca de strings Knuth-Morris-Pratt ou o Algoritmo KMP busca ocorrências de um "Padrão" dentro de um "Texto"
principal empregando a observação de que quando ocorre uma incompatibilidade, a própria palavra incorpora informações
suficientes para determinar onde a próxima correspondência poderia começar, ignorando assim o reexame de caracteres previamente
correspondidos. O algoritmo foi concebido em 1970 por Donuld Knuth e Vaughan Pratt e independentemente por James H. Morris. O
trio publicou-o em conjunto em 1977.
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+-- +--+--+--+--+--+--+--+--+--+
| Índice |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+-- +--+--+--+--+--+--+--+--+--+
| Texto |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+-- +--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Primeiro, nosso Text e Pattern correspondem até o índice 2. Text[3] e Pattern[3] não correspondem. Então, nosso objetivo é não voltar atrás
neste Text, ou seja, em caso de incompatibilidade, não queremos que nossa correspondência comece novamente da posição com a qual
começamos a correspondência. Para conseguir isso, procuraremos um sufixo em nosso Pattern logo antes de nossa incompatibilidade
ocorrer (substring abc), que também é um prefixo da substring de nosso Pattern. Para nosso exemplo, como todos os caracteres são
únicos, não há sufixo, que é o prefixo de nossa substring correspondente. Então, o que isso significa é que nossa próxima comparação
começará do índice 0. Espere um pouco, você entenderá por que fizemos isso. Em seguida, comparamos Text[3] com Pattern[0] e não
corresponde. Depois disso, para Text do índice 4 ao índice 9 e para Pattern do índice 0 ao índice 5, encontramos uma correspondência. Encontramos
uma incompatibilidade em Text[10] e Pattern[6]. Então pegamos a substring de Pattern logo antes do ponto onde ocorre a incompatibilidade
(substring abcdabc), verificamos se há um sufixo, que também é um prefixo desta substring. Podemos ver aqui que ab é o sufixo e o prefixo desta
substring. O que isso significa é que, como fizemos a correspondência até Text[10], os caracteres logo antes da incompatibilidade são ab.
O que podemos inferir disso é que, como ab também é um prefixo da substring que pegamos, não precisamos verificar ab novamente e a próxima
verificação pode começar em Text[10] e Pattern[2]. Não precisamos olhar para todo o Text, podemos começar diretamente de onde ocorreu
nossa incompatibilidade. Agora verificamos Text[10] e Pattern[2], já que é uma incompatibilidade, e a substring antes da incompatibilidade
(abc) não contém um sufixo que também é um prefixo, verificamos Text[10] e Pattern[0], eles não correspondem. Depois disso, para Text do
índice 11 ao índice 17 e para Pattern do índice 0 ao índice 6. Encontramos uma incompatibilidade em Text[18] e Pattern[7]. Então, novamente,
verificamos a substring antes da incompatibilidade (substring abcdabc) e descobrimos que abc é o sufixo e o prefixo. Então, como
fizemos a correspondência até Pattern[7], abc deve estar antes de Text[18]. Isso significa que não precisamos comparar até Text[17] e nossa
comparação começará em Text[18] e Pattern[3]. Assim, encontraremos uma correspondência e retornaremos 15 , que é nosso índice inicial
da correspondência. É assim que nossa Pesquisa de Substring KMP funciona usando informações de sufixo e prefixo.
Agora, como calculamos eficientemente se sufixo é o mesmo que prefixo e em que ponto iniciar a verificação se há uma incompatibilidade
de caractere entre Texto e Padrão. Vamos dar uma olhada em um exemplo:
+---------+---+---+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Padrão | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Geraremos um array contendo as informações necessárias. Vamos chamar o array de S. O tamanho do array será o mesmo que o comprimento do
padrão. Como a primeira letra do Padrão não pode ser o sufixo de nenhum prefixo, colocaremos S[0] = 0. Pegamos i = 1 e j = 0 primeiro. Em cada
etapa, comparamos Pattern[i] e Pattern[j] e incrementamos i. Se houver uma correspondência, colocamos S[i] = j + 1 e incrementamos j, se
houver uma incompatibilidade, verificamos a posição do valor anterior de j (se disponível) e definimos j = S[j-1] (se j não for igual a 0), continuamos
fazendo isso até que S[j] não corresponda a S[i] ou j não se torne 0. Para o último, colocamos S[i] = 0. Para nosso exemplo:
eu
eu
+---------+---+---+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Padrão | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Pattern[j] e Pattern[i] não correspondem, então incrementamos i e como j é 0, não verificamos o valor anterior e colocamos Pattern[i] = 0. Se
continuarmos incrementando i, para i = 4, obteremos uma correspondência, então colocamos S[i] = S[4] = j + 1 = 0 + 1 = 1 e
eu
eu
+---------+---+---+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Padrão | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S |0|0|0|0|1| | | |
+---------+---+---+---+---+---+---+---+---+
Como Pattern[1] e Pattern[5] são uma correspondência, colocamos S[i] = S[5] = j + 1 = 1 + 1 = 2. Se continuarmos, encontraremos
uma incompatibilidade para j = 3 e i = 7. Como j não é igual a 0, colocamos j = S[j-1]. E compararemos se os caracteres em i e j são iguais ou
não, já que são iguais, colocaremos S[i] = j + 1. Nosso array completo ficará assim:
+---------+---+---+---+---+---+---+---+---+
| S |0|0|0|0|1|2|3|1|
+---------+---+---+---+---+---+---+---+---+
Este é o nosso array necessário. Aqui, um valor diferente de zero de S[i] significa que há um sufixo de comprimento S[i] igual ao prefixo naquela
substring (substring de 0 a i) e a próxima comparação começará da posição S[i] + 1 do Pattern. Nosso algoritmo para gerar o array ficaria
assim:
Procedimento GenerateSuffixArray(Pattern): i := 1 j := 0 n :=
Pattern[j]
S[i] := j + 1 j := j + 1
i := i + 1 senão
S[i] := 0 i := i +
1 fim se fim se
fim
enquanto
A complexidade de tempo para construir esta matriz é O(n) e a complexidade de espaço também é O(n). Para ter certeza de que você
entendeu completamente o algoritmo, tente gerar uma matriz para o padrão aabaabaa e verifique se o resultado corresponde a este um.
+---------+---+---+---+---+---+---+---+---+---+--- +---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+--- +---+---+
| Texto | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+--- +---+---+
+---------+---+---+---+---+---+---+
| Índice | 0 | 1 | 2 | 3 | 4 | 5 |
| Padrão | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S |0|0|0|1|2|0|
+---------+---+---+---+---+---+---+
Temos um Text, um Pattern e um array S pré-calculado usando nossa lógica definida antes. Comparamos Text[0] e Pattern[0] e eles são
iguais. Text[1] e Pattern[1] são iguais. Text[2] e Pattern[2] não são iguais. Verificamos o valor na posição imediatamente antes da
incompatibilidade. Como S[1] é 0, não há sufixo que seja igual ao prefixo em nossa substring e nossa comparação começa na posição S[1], que é
0. Então Pattern[0] não é igual a Text[2], então seguimos em frente. Text[3] é igual a Pattern[0] e há uma correspondência até Text[8] e
Pattern[5]. Voltamos um passo no array S e encontramos 2. Então isso significa que há um prefixo de comprimento 2 que também é o sufixo
desta substring (abcab) que é ab. Isso também significa que há um ab antes de Text[8]. Então podemos ignorar com segurança Pattern[0] e
Pattern[1] e começar nossa próxima comparação de Pattern[2] e Text[8]. Se continuarmos, encontraremos o Pattern no Text. Nosso procedimento
será parecido com:
j := 0
enquanto i é menor que m
se j é igual a n
Retorna (ji) senão
se i < m e Pattern[j] não for igual a t Text[i] se j não for igual a 0 j = S[j-1] senão
i := i + 1 fim se
fim se
fim enquanto
Retornar -1
A complexidade de tempo desse algoritmo, além do Cálculo de Matriz de Sufixos, é O(m). Como GenerateSuffixArray leva O(n), a complexidade de
tempo total do Algoritmo KMP é: O(m+n).
PS: Se você quiser encontrar múltiplas ocorrências de Pattern no Texto, em vez de retornar o valor, imprima-o/armazene-o e defina j := S[j-1].
Mantenha também um sinalizador para rastrear se você encontrou alguma ocorrência ou não e trate-a adequadamente.
Uma substring de uma string é outra string que ocorre em. Por exemplo, ver é uma substring de stackoverflow. Não deve ser confundido com
subsequência porque cover é uma subsequência da mesma string. Em outras palavras, qualquer subconjunto de letras consecutivas em
uma string é uma substring da string fornecida.
No algoritmo Rabin-Karp, geraremos um hash do nosso padrão que estamos procurando e verificaremos se o hash rolante do nosso texto
corresponde ao padrão ou não. Se não corresponder, podemos garantir que o padrão não existe no texto.
Digamos que temos um texto: yeminsajid e queremos descobrir se o padrão nsa existe no texto. Para calcular o
hash e rolling hash, precisaremos usar um número primo. Pode ser qualquer número primo. Vamos pegar primo = 11 para
neste exemplo. Determinaremos o valor hash usando esta fórmula:
(1ª letra) X (primo) + (2ª letra) X (primo)¹ + (3ª letra) X (primo)² X + ......
Vamos denotar:
Agora encontramos o rolling-hash do nosso texto. Se o rolling hash corresponder ao valor do hash do nosso padrão, verificaremos se
as strings correspondem ou não. Como nosso padrão tem 3 letras, pegaremos as primeiras 3 letras yem do nosso texto e calcularemos
valor hash. Obtemos:
Este valor não corresponde ao valor hash do nosso padrão. Então a string não existe aqui. Agora precisamos considerar
o próximo passo. Para calcular o valor hash da nossa próxima string emi. Podemos calcular isso usando nossa fórmula. Mas isso
seria bastante trivial e nos custaria mais. Em vez disso, usamos outra técnica.
Subtraímos o valor da Primeira Letra da String Anterior do nosso valor hash atual. Neste caso, y. Nós
obtenha, 1653 - 25 = 1628.
Dividimos a diferença com nosso primo, que é 11 para este exemplo. Obtemos, 1628 / 11 = 148.
Adicionamos a nova letra X (primo)ÿ¹, onde m é o comprimento do padrão, com o quociente, que é i = 9. Nós
obtenha, 148 + 9 X 11² = 1237.
O novo valor hash não é igual ao valor hash dos nossos padrões. Seguindo em frente, para n obtemos:
É uma correspondência! Agora comparamos nosso padrão com a string atual. Como ambas as strings correspondem, a substring existe nesta string. E
retornamos a posição inicial da nossa substring.
O pseudocódigo será:
Cálculo de hash:
Retornar hash
Recálculo de Hash:
Correspondência de sequência:
Rabin-Karp:
Este algoritmo é usado para detectar plágio. Dado o material de origem, o algoritmo pode pesquisar rapidamente em um artigo por instâncias de
frases do material de origem, ignorando detalhes como caso e pontuação. Devido à abundância das sequências procuradas, algoritmos de busca de
sequência única são impraticáveis aqui. Novamente, o algoritmo Knuth-Morris-Pratt ou o algoritmo Boyer-Moore String Search é um
algoritmo de busca de sequência única de padrão mais rápido do que Rabin-Karp. No entanto, é um algoritmo de escolha para busca de
padrões múltiplos. Se quisermos encontrar qualquer um dos grandes números, digamos k, padrões de comprimento fixo em um texto, podemos criar
uma variante simples do algoritmo Rabin-Karp.
Para texto de comprimento n e padrões p de comprimento combinado m, seu tempo de execução médio e melhor caso é O(n+m) no espaço
O(p), mas seu tempo de pior caso é O(nm).
Complexidade de tempo: A parte de pesquisa (método strstr) tem a complexidade O(n), onde n é o comprimento do palheiro, mas como a
agulha também é pré-analisada para construir a tabela de prefixos, O(m) é necessário para construir a tabela de prefixos, onde m é o comprimento
da agulha.
Observação: a implementação a seguir retorna a posição inicial da correspondência no palheiro (se houver uma correspondência), caso contrário,
retorna -1, para casos extremos, como se agulha/palheiro for uma string vazia ou agulha não for encontrada no palheiro.
prefix_set.add(agulha[:delimitador])
j = 1 while(j<delimitador+1): se agulha[j:delimitador+1] em
prefix_set:
j += 1
delimitador += 1
retornar prefix_table
retornar -1
m += 1
outro:
se eu != 0:
i = prefix_table[i-1] senão:
m += 1
retornar -1
se __nome__ == '__principal__':
agulha = 'abcaby' palheiro
= 'abxabcabcaby' print strstr(palheiro,
agulha)
Exemplos:
Entrada:
saída:
Entrada:
saída:
Implementação da Linguagem C:
#incluir<string.h>
#incluir<stdlib.h>
se (pat[j] == txt[i]) {
j++; i+
+;
}
se (j == M) {
eu = i+1;
}
se (pat[i] == pat[len]) {
len++;
lps[i] = len; i++;
se (comprimento != 0)
{
// Isso é complicado. Considere o exemplo // AAACAAAA e i =
7. len = lps[len-1];
} senão // se (len == 0) {
lps[i] = 0; i++;
}
}
}
}
Saída:
Referência:
[Link]
Busca em largura (BFS) é um algoritmo para percorrer ou pesquisar estruturas de dados de árvore ou gráfico. Ele começa na raiz da
árvore (ou algum nó arbitrário de um gráfico, às vezes chamado de "chave de pesquisa") e explora os nós vizinhos primeiro, antes
de passar para os vizinhos do próximo nível. O BFS foi inventado no final dos anos 1950 por Edward Forrest Moore, que o usou para
encontrar o caminho mais curto para sair de um labirinto e foi descoberto independentemente por CY Lee como um algoritmo de
roteamento de fios em 1961.
Vejamos um exemplo:
Vamos supor que este gráfico representa a conexão entre várias cidades, onde cada nó denota uma cidade e uma aresta entre
dois nós denota que há uma estrada ligando-os. Queremos ir do nó 1 ao nó 10. Então o nó 1 é nossa fonte, que é o nível 0. Marcamos
o nó 1 como visitado. Podemos ir para o nó 2, nó 3 e nó 4 daqui. Então eles serão nós de nível (0+1) = nível 1. Agora vamos
marcá-los como visitados e trabalhar com eles.
Os nós coloridos são visitados. Os nós com os quais estamos trabalhando atualmente serão marcados em rosa. Não visitaremos o mesmo nó
duas vezes. Do nó 2, nó 3 e nó 4, podemos ir para o nó 6, nó 7 e nó 8. Vamos marcá-los como visitados. O nível desses nós será nível (1+1) =
nível 2.
Se você não notou, o nível de nós simplesmente denota a distância do caminho mais curto da fonte. Por exemplo:
encontramos o nó 8 no nível 2. Portanto, a distância da fonte ao nó 8 é 2.
Ainda não chegamos ao nosso nó alvo, que é o nó 10. Então vamos visitar os próximos nós. Podemos ir diretamente do nó 6, nó 7 e nó 8.
Podemos ver que encontramos o nó 10 no nível 3. Portanto, o caminho mais curto da origem ao nó 10 é 3. Pesquisamos o
gráfico nível por nível e encontramos o caminho mais curto. Agora vamos apagar as arestas que não usamos:
Após remover as arestas que não usamos, obtemos uma árvore chamada BFS tree. Esta árvore mostra o caminho mais curto da fonte para
todos os outros nós.
Então nossa tarefa será ir da fonte para os nós de nível 1. Então, dos nós de nível 1 para os nós de nível 2 e assim por diante até chegarmos
ao nosso destino. Podemos usar a fila para armazenar os nós que vamos processar. Ou seja, para cada nó com o qual vamos trabalhar,
vamos empurrar todos os outros nós que podem ser atravessados diretamente e ainda não atravessados na fila.
frente
++-----
|1|
++-----
O nível do nó 1 será 0. level[1] = 0. Agora iniciamos nosso BFS. Primeiro, retiramos um nó da nossa fila. Obtemos o nó 1. Podemos ir para
o nó 4, nó 3 e nó 2 a partir deste. Chegamos a esses nós a partir do nó 1. Então level[4] = level[3] = level[2] = level[1] + 1 = 1. Agora
os marcamos como visitados e os colocamos na fila.
frente
+-----+ +-----+ +-----+
|2| |3| |4|
+-----+ +-----+ +-----+
Agora, nós estouramos o nó 4 e trabalhamos com ele. Podemos ir para o nó 7 a partir do nó 4. level[7] = level[4] + 1 = 2. Nós marcamos o nó 7
como visitado e colocá-lo na fila.
frente
+-----+ +-----+ +-----+
|7| |2| |3|
+-----+ +-----+ +-----+
frente
+-----+ +-----+ +-----+
|6| |7| |2|
+-----+ +-----+ +-----+
Este processo continuará até que cheguemos ao nosso destino ou a fila fique vazia. O array de níveis nos fornecerá
com a distância do caminho mais curto da fonte. Podemos inicializar a matriz de nível com valor infinito , que marcará
que os nós ainda não foram visitados. Nosso pseudocódigo será:
Ao iterar através do array de níveis , podemos descobrir a distância de cada nó da fonte. Por exemplo: o
a distância do nó 10 da fonte será armazenada no nível[10].
Às vezes, podemos precisar imprimir não apenas a distância mais curta, mas também o caminho pelo qual podemos ir até nosso
nó destinado da fonte. Para isso, precisamos manter um array pai . parent[source] será NULL. Para cada
atualização no array de nível , simplesmente adicionaremos parent[v] := u em nosso pseudo código dentro do loop for. Após terminar o BFS,
para encontrar o caminho, percorreremos a matriz pai até chegarmos à origem , que será denotada pelo valor NULL.
O pseudocódigo será:
Complexidade:
Visitamos cada nó uma vez e cada aresta uma vez. Então a complexidade será O(V + E) onde V é o número de nós e E é o número de arestas.
Haverá uma coisa adicional chamada direction array. Isso simplesmente armazenará todas as combinações possíveis de direções para as
quais podemos ir. Digamos que, para movimentos horizontais e verticais, nossos direction arrays serão:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| sim | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Aqui dx representa movimento no eixo x e dy representa movimento no eixo y. Novamente, esta parte é opcional. Você também pode escrever
todas as combinações possíveis separadamente. Mas é mais fácil lidar com isso usando o array direction. Pode haver mais e até mesmo
combinações diferentes para movimentos diagonais ou movimentos de cavalo.
Se alguma célula estiver bloqueada, para cada movimento possível, verificaremos se a célula está bloqueada ou não.
Também verificaremos se saímos dos limites, ou seja, se cruzamos os limites da matriz.
O número de linhas e colunas será fornecido.
fim para
visitado[fonte.x][fonte.y] := verdadeiro nível[fonte.x]
[fonte.y] := 0 Q = fila()
[Link](source) m :=
[Link] enquanto
Q não estiver vazio top := [Link]
para i de 1 a m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i] se temp estiver
dentro da linha e coluna e top não for
igual a blocksign visited[temp.x][temp.y] := true level[temp.x][temp.y] := level[top.x][top.y] + 1 [Link](temp)
fim se
de ponta a
ponta enquanto
Nível de retorno
Como discutimos anteriormente, o BFS só funciona para gráficos não ponderados. Para gráficos ponderados, precisaremos do algoritmo
de Dijkstra. Para ciclos de arestas negativas, precisamos do algoritmo de Bellman-Ford. Novamente, esse algoritmo é um algoritmo
de caminho mais curto de fonte única. Se precisarmos descobrir a distância de cada nó para todos os outros nós, precisaremos do
algoritmo de Floyd-Warshall.
BFS é um algoritmo de travessia de grafos. Então, começando de um nó de origem aleatório, se no término do algoritmo, todos os
nós forem visitados, então o grafo é conectado, caso contrário, não é conectado.
retornar
verdadeiro; } senão
retornar falso; }
#incluir<stdio.h>
#include<stdlib.h> #define
MAXVÉRTICES 100
isConnected(char
int v;
struct nó *próximo;
};
int principal()
{
int n,e;//n é o número de vértices, e é o número de arestas. int i,j; char **graph;//
matriz de
adjacência
{ fprintf(stderr, "Por favor, insira um inteiro positivo válido de 1 a %d",MAXVERTICES); return -1; }
int u,v;
scanf("%d%d",&u,&v);
gráfico[u-1][v-1] = 1;
gráfico[v-1][u-1] = 1;
}
if(isConnected(graph,n)) printf("O
gráfico está conectado");
else printf("O gráfico NÃO está conectado\n");
}
se(Qfront == NULL) {
} outro
{
Nodeptr novoNode = malloc(tamanhode(Nó)); novoNode-
>v = vértice; novoNode-
>próximo = NULL;
Qrear->próximo = novoNó;
Qrear = novoNó;
}
}
int deque() {
se(Qfront == NULL) {
} outro
{
int v = Qfront->v;
Nodeptr temp= Qfront; se(Qfront
== Qrear) {
Qfront = Qfront->próximo;
Qrear = NULO;
} outro
Qfront = Qfront->próximo;
livre(temp);
retornar v;
}
}
int eu;
int i, vértice;
visitado[v] = 'Y';
enfileirar(v);
enquanto((vértice = deque()) != -1) {
enqueue(i);
visitado[i] = 'S';
}
}
}
Para encontrar todos os componentes conectados de um grafo não direcionado, precisamos apenas adicionar 2 linhas de código à função BFS. A ideia é
chamar a função BFS até que todos os vértices sejam visitados.
int i;
para(i = 0;i < noOfVertices;++i) {
se(visitado[i] == 'N')
BFS(gráfico,i,noOfVertices);
}
}
Busca em profundidade é uma maneira sistemática de encontrar todos os vértices alcançáveis de um vértice de origem. Assim como a busca em largura, o
DFS percorre um componente conectado de um dado grafo e define uma árvore de abrangência. A ideia básica da busca em profundidade é explorar
metodicamente cada aresta. Começamos de novo de um vértice diferente, conforme necessário. Assim que descobrimos um vértice, o DFS começa a explorar
a partir dele (ao contrário do BFS, que coloca um vértice em uma fila para que ele explore a partir dele mais tarde).
O nó que visitamos, mas não visitamos todos os seus nós filhos, será colorido em cinza.
Podemos ver uma palavra-chave importante. Que é backedge. Você pode ver. 5-1 é chamado de backedge. Isso ocorre porque ainda não
terminamos com o nó-1, então ir de outro nó para o nó-1 significa que há um ciclo no gráfico. No DFS, se pudermos ir de um nó cinza
para outro, podemos ter certeza de que o gráfico tem um ciclo. Esta é uma das maneiras de detectar o ciclo em um gráfico. Dependendo
do nó de origem e da ordem dos nós que visitamos, podemos descobrir qualquer aresta em um ciclo como backedge. Por exemplo: se
fôssemos para 5 a partir de 1 primeiro, teríamos descoberto 2-1 como backedge.
A aresta que pegamos para ir do nó cinza para o nó branco é chamada de aresta da árvore. Se mantivermos apenas as arestas da árvore
e removermos outras, teremos a árvore DFS.
Em grafos não direcionados, se pudermos visitar um nó já visitado, isso deve ser um backedge. Mas para grafos direcionados, devemos
verificar as cores. Se e somente se pudermos ir de um nó cinza para outro nó cinza, isso é chamado de backedge.
No DFS, também podemos manter registros de data e hora para cada nó, que podem ser usados de várias maneiras (por exemplo: classificação topológica).
Aqui d[] significa tempo de descoberta e f[] significa tempo de término. Nosso pseudocódigo ficará assim:
fim para o
tempo := 0
para cada nó u em V[G]
se cor[u] == branco
DFS-Visit(u) fim se
fim para
DFS-Visit(v) fim se
fim para
cor[u] :=
preto tempo := tempo + 1
f[u] := tempo
Complexidade:
Cada nó e aresta são visitados uma vez. Então a complexidade do DFS é O(V+E), onde V denota o número de nós e E denota o número de arestas.
Encontrando o caminho.
Classificação topológica.
Booleano
SByte
Decimal
Objeto
[Link](este);
Corda
A computação do código hash depende do tipo de plataforma (Win32 ou Win64), do recurso de uso de hash de string aleatório, do modo
Debug/ Release. No caso da plataforma Win64:
Tipo de valor
O primeiro campo não estático é look for e obtém seu hashcode. Se o tipo não tiver campos não estáticos, o hashcode do tipo retorna. O hashcode de
um membro estático não pode ser obtido porque se esse membro for do mesmo tipo que o tipo original, o cálculo termina em um loop infinito.
Anulável<T>
Variedade
Referências
A função hash h() é uma função arbitrária que mapeia dados x ÿ X de tamanho arbitrário para valor y ÿ Y de tamanho fixo: y = h(x). Boas funções
hash têm as seguintes restrições:
funções hash são determinísticas. h(x) deve sempre retornar o mesmo valor para um dado x
No caso geral, o tamanho da função hash é menor que o tamanho dos dados de entrada: |y| < |x|. As funções hash não são reversíveis ou, em
outras palavras, podem ser colisões: ÿ x1, x2 ÿ X, x1 ÿ x2: h(x1) = h(x2). X pode ser um conjunto finito ou infinito e Y é um conjunto finito.
Funções hash são usadas em muitas partes da ciência da computação, por exemplo, em engenharia de software, criptografia, bancos de dados, redes,
aprendizado de máquina e assim por diante. Existem muitos tipos diferentes de funções hash, com diferentes propriedades específicas de domínio.
Frequentemente hash é um valor inteiro. Existem métodos especiais em linguagens de programação para cálculo de hash. Por exemplo, em C#, o
método GetHashCode() para todos os tipos retorna o valor Int32 (número inteiro de 32 bits). Em Java, cada classe fornece o método hashCode() que retorna
int. Cada tipo de dado tem implementações próprias ou definidas pelo usuário.
Métodos de hash
Existem várias abordagens para determinar a função hash. Sem perda de generalidade, deixe x ÿ X = {z ÿ ÿ: z ÿ 0} serem números inteiros
positivos. Frequentemente m é primo (não muito próximo de uma potência exata de 2).
Tabela de hash
Funções de hash usadas em tabelas de hash para calcular índice em uma matriz de slots. A tabela de hash é uma estrutura de dados para
implementando dicionários (estrutura chave-valor). Boas tabelas hash implementadas têm tempo O(1) para o próximo
operações: inserir, pesquisar e excluir dados por chave. Mais de uma chave pode fazer hash no mesmo slot. Existem dois
maneiras de resolver colisões:
1. Encadeamento: a lista vinculada é usada para armazenar elementos com o mesmo valor de hash no slot
Os próximos métodos são usados para calcular as sequências de sondagem necessárias para endereçamento aberto
Método Fórmula
Onde i ÿ {0, 1, ..., m-1}, h'(x), h1(x), h2(x) são funções hash auxiliares, c1, c2 são funções auxiliares positivas
constantes.
Exemplos
Seja x ÿ U{1, 1000}, h = x mod m. A próxima tabela mostra os valores de hash em caso de not prime e prime. Negrito
o texto indica os mesmos valores de hash.
103 3 2
738 38 31
292 92 90
61 61 61
87 87 87
995 95 86
549 49 44
991 91 82
757 57 50
920 20 11
626 26 20
557 57 52
831 31 23
619 19 13
Ligações
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introdução aos Algoritmos.
Pseudocódigo
todas as permutações P
atual = 0
para i de 0 a N-2
atual = atual + custo[P[i]][P[i+1]] <- Adicione o custo de ir de um vértice para o próximo
saída mínima
Complexidade de tempo
Existem N! permutações a serem percorridas e o custo de cada caminho é calculado em O(N), portanto esse algoritmo leva O(N * N!) tempo para gerar a
resposta exata.
(1,2,3,4,6,0,5,7)
e o caminho
(1,2,3,5,0,6,7,4)
O custo de ir do vértice 1 para o vértice 2 para o vértice 3 permanece o mesmo, então por que ele deve ser recalculado? Este resultado pode ser salvo
para uso posterior.
Deixe dp[bitmask][vertex] representar o custo mínimo de viajar por todos os vértices cujo bit correspondente em bitmask é definido como 1 terminando
no vértice. Por exemplo:
dp[12][2]
12 = 1100
^^
vértices: 3 2 1 0
Como 12 representa 1100 em binário, dp[12][2] representa passar pelos vértices 2 e 3 no gráfico com o caminho terminando no vértice 2.
Esta linha pode ser um pouco confusa, então vamos analisá-la lentamente:
Aqui, bitmask | (1 << i) define o bit iésimo de bitmask para 1, o que representa que o vértice iésimo foi visitado. O
i depois da vírgula representa a nova posição naquela chamada de função, que representa o novo "último" vértice.
cost[pos][i] é adicionar o custo de viajar do vértice pos ao vértice i.
Assim, esta linha é para atualizar o valor do custo para o valor mínimo possível de viajar para cada outro vértice que
ainda não foi visitado.
Complexidade de tempo
A função TSP(bitmask,pos) tem 2^N valores para bitmask e N valores para pos. Cada função leva O(N) tempo para
execute (o loop for ). Portanto, essa implementação leva tempo O(N^2 * 2^N) para gerar a resposta exata.
Dado:
1. Valores(matriz v)
2. Pesos(matriz w)
3. Número de itens distintos(n)
4. Capacidade (W)
K[i][w] = 0 elif
wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) senão:
K[i][w] = K[i-1][w]
retornar K[n][W] val =
[60, 100, 120] wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
Complexidade de tempo do código acima: O(nW) , onde n é o número de itens e W é a capacidade da mochila.
int i;
int[,] k = novo int[n + 1, w + 1]; para (i = 0; i
<= n; i++) {
int b;
para (b = 0; b <= w; b++) {
se (i==0 || b==0) {
k[i, b] = 0;
}
outro {
k[i, b] = k[i - 1, b];
}
}
int n = [Link];
return Mochila(nItens, pesos, valores, n);
}
}
1. Métodos diretos: As características comuns dos métodos diretos são que eles transformam a equação original em equações
equivalentes que podem ser resolvidas mais facilmente, o que significa que podemos resolver diretamente uma equação.
2. Método Iterativo: Métodos Iterativos ou Indiretos, começam com um palpite da solução e então refinam repetidamente a solução até que
um certo critério de convergência seja alcançado. Métodos iterativos são geralmente menos eficientes do que métodos diretos porque
um grande número de operações são necessárias. Exemplo- Método de Iteração de Jacobi, Método de Iteração de Gauss-Seidal.
Implementação em C-
int i, j;
enquanto(!rootFound)
{ para(i=0; i<n; i++){ Nx[i]=b[i]; // cálculo
raizEncontrado=1; // verificação
para(i=0; i<n; i++){ se(!( (Nx[i]-
x[i])/x[i] > -0,000001 && (Nx[i]-x[i])/x[i] < 0,000001 )){
raizEncontrado=0;
quebrar;
}
}
}
}
retornar ;
}
int i, j;
para(i=0; i<n; i++){ // inicialização
Nx[i]=x[i];
}
enquanto(!rootFound)
{ para(i=0; i<n; i++){ Nx[i]=b[i]; // cálculo
raizEncontrado=1; // verificação
para(i=0; i<n; i++){ se(!( (Nx[i]-
x[i])/x[i] > -0,000001 && (Nx[i]-x[i])/x[i] < 0,000001 )){
raizEncontrado=0;
quebrar;
}
}
}
}
retornar ;
}
} printf("\n\n");
retornar ;
}
int main(){ //
inicialização da equação // número de
variáveis int n=3;
int eu;
}
Método Jacobis(n, x, b, a); imprimir(n, x);
x[i]=0;
}
Método GaussSeidal(n, x, b, a); imprimir(n, x);
retornar 0;
}
1. Método Direto: Este método fornece o valor exato de todas as raízes diretamente em um número finito de etapas.
2. Método indireto ou iterativo: os métodos iterativos são mais adequados para programas de computador para resolver um
equação. Baseia-se no conceito de aproximação sucessiva. No Método Iterativo, há duas maneiras de resolver uma equação:
Método de Bracketing: Pegamos dois pontos iniciais onde a raiz está entre eles. Exemplo-Método de Bissecção,
Método de Posição Falsa.
Método de Extremidade Aberta: Tomamos um ou dois valores iniciais onde a raiz pode estar em qualquer lugar. Exemplo-
Método de Newton-Raphson, Método de Aproximação Sucessiva, Método Secante.
Implementação em C:
/// Aqui defina diferentes funções para trabalhar com #define f(x) ( ((x)*(x)*(x))
- (x) - 2 ) #define f2(x) ( (3*(x)*(x)) - 1 ) #define g(x) ( cbrt( (x) +
2))
/ ** *
Recebe dois valores iniciais e encurta a distância em ambos os lados. **/ double BisectionMethod()
{ double root=0;
uma=c;
retornar raiz;
}
/ ** *
Recebe dois valores iniciais e encurta a distância por um lado. **/ double FalsePosition(){ double root=0;
}
}
retornar raiz;
}
/ ** *
Usa um valor inicial e gradualmente aproxima esse valor do real. **/ double NewtonRaphson(){ double root=0;
x1=x2;
retornar raiz;
}
/ ** *
Usa um valor inicial e gradualmente aproxima esse valor do real. **/ double FixedPoint(){ double root=0; double x=1;
x=g(x);
retornar raiz;
}
/ ** *
usa dois valores iniciais e ambos os valores se aproximam da raiz. **/ double Secant(){ double
root=0;
x2 = ((x0*f(x1))-(x1*f(x0))) / (f(x1)-f(x0));
x0=x1;
x1=x2;
retornar raiz;
}
int principal(){
raiz dupla ;
root = BisectionMethod();
printf("Usando o Método Bisection a raiz é: %lf \n\n", root);
root = FalsePosition();
printf("Usando o método False Position, a raiz é: %lf \n\n", root);
root = NewtonRaphson();
printf("Usando o método Newton-Raphson a raiz é: %lf \n\n", root);
root = FixedPoint();
printf("Usando o Método de Ponto Fixo a raiz é: %lf \n\n", root);
root = Secant();
printf("Usando o Método Secant a raiz é: %lf \n\n", root);
retornar 0;
}
Subsequência:
Uma subsequência é uma sequência que pode ser derivada de outra sequência pela exclusão de alguns elementos sem
alterando a ordem dos elementos restantes. Digamos que temos uma string ABC. Se apagarmos zero ou um ou mais de
um caractere desta string obtemos a subsequência desta string. Portanto, as subsequências da string ABC serão
{"A", "B", "C", "AB", "AC", "BC", "ABC", " "}. Mesmo se removermos todos os caracteres, a string vazia também será uma
subsequência. Para descobrir a subsequência, para cada caractere em uma string, temos duas opções - ou pegamos o
personagem, ou não. Então, se o comprimento da string é n, há 2n subsequências dessa string.
Como o nome sugere, de todas as subsequências comuns entre duas strings, a maior subsequência comum (LCS)
é aquele com o comprimento máximo. Por exemplo: As subsequências comuns entre "HELLOM" e "HMLD"
são "H", "HL", "HM" etc. Aqui "HLL" é a maior subsequência comum que tem comprimento 3.
Podemos gerar todas as subsequências de duas strings usando backtracking. Então podemos compará-las para descobrir a
subsequências comuns. Depois, precisaremos descobrir aquela com o comprimento máximo. Já vimos que,
há 2n subsequências de uma sequência de comprimento n. Levaria anos para resolver o problema se nosso n cruzasse 20-25.
Vamos abordar nosso método com um exemplo. Suponha que temos duas strings abcdaf e acbcf. Vamos denotar
estes com s1 e s2. Então a maior subsequência comum dessas duas strings será "abcf", que tem comprimento 4.
Novamente, lembro a você, subsequências não precisam ser contínuas na string. Para construir "abcf", ignoramos "da" em s1
e "c" em s2. Como descobrimos isso usando Programação Dinâmica?
Começaremos com uma tabela (uma matriz 2D) tendo todos os caracteres de s1 em uma linha e todos os caracteres de s2 em uma coluna.
Aqui a tabela é indexada em 0 e colocamos os caracteres de 1 em diante. Percorreremos a tabela da esquerda para a direita
para cada linha. Nossa tabela ficará assim:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|e| | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b| | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4| | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e| | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Aqui, cada linha e coluna representam o comprimento da maior subsequência comum entre duas strings se
pegue os caracteres dessa linha e coluna e adicione ao prefixo antes dela. Por exemplo: Table[2][3] representa o
comprimento da maior subsequência comum entre "ac" e "abc".
A coluna 0-ésima representa a subsequência vazia de s1. Da mesma forma, a linha 0-ésima representa a subsequência vazia
subsequência de s2. Se pegarmos uma subsequência vazia de uma string e tentarmos combiná-la com outra string, não importa
quanto tempo o comprimento da segunda substring é, a subsequência comum terá comprimento 0. Então podemos preencher o 0-
ª linhas e 0ª colunas com 0's. Obtemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| |0|0|0|0|0|0|0|
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Vamos começar. Quando estamos preenchendo a Tabela[1][1], estamos nos perguntando, se tivéssemos uma string a e outra string a e
nada mais, qual será a maior subsequência comum aqui? O comprimento do LCS aqui será 1. Agora vamos
veja a Tabela[1][2]. Temos a string ab e a string a. O comprimento do LCS será 1. Como você pode ver, o resto do
os valores também serão 1 para a primeira linha, pois considera apenas a string a com abcd, abcda, abcdaf. Portanto, nossa tabela ficará
como:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| |0|0|0|0|0|0|0|
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | 0 | 1 | 1 |1| 1 |1| 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Para a linha 2, que agora incluirá c. Para a Tabela[2][1] temos ac de um lado e a do outro lado. Então o comprimento de
o LCS é 1. De onde tiramos esse 1? Do topo, que denota o LCS entre duas substrings. Então o que
estamos dizendo que, se s1[2] e s2[1] não forem iguais, então o comprimento do LCS será o máximo do comprimento de
221
Notas de algoritmos do [Link] para profissionais
Machine Translated by Google
LCS no topo, ou à esquerda. Tirar o comprimento do LCS no topo denota que não pegamos a corrente
personagem de s2. Da mesma forma, tomar o comprimento do LCS à esquerda denota que não tomamos a corrente
personagem de s1 para criar o LCS. Obtemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| |0|0|0|0|0|0|0|
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | 0 | 1 | 1 |1| 1 |1| 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|c|0|1| | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Seguindo em frente, para a Tabela[2][2] temos as strings ab e ac. Como c e b não são iguais, colocamos o máximo do topo ou
deixado aqui. Neste caso, é novamente 1. Depois disso, para a Tabela[2][3] temos as strings abc e ac. Desta vez, os valores atuais de
ambas as linhas e colunas são iguais. Agora o comprimento do LCS será igual ao comprimento máximo do LCS até agora + 1.
Como obtemos o comprimento máximo do LCS até agora? Verificamos o valor diagonal, que representa a melhor correspondência
entre ab e a. Deste estado, para os valores atuais, adicionamos mais um caractere a s1 e s2 que
aconteceu de ser o mesmo. Então o comprimento do LCS irá, é claro, aumentar. Colocaremos 1 + 1 = 2 na Tabela[2][3]. Obtemos,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| |0|0|0|0|0|0|0|
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | 0 | 1 | 1 |1| 1 |1| 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|c|0|1| 1 |2| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4|c|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e|0| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Definimos ambos os casos. Usando essas duas fórmulas, podemos preencher a tabela inteira. Após preencher o
tabela, ficará assim:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chÿ | | um | b | c | d | um | e |
+-----+-----+-----+-----+-----+-----+-----+-----+
0| |0|0|0|0|0|0|0|
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | um | 0 | 1 | 1 |1| 1 |1| 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2|c|0|1| 1 |2|2|2|2|
+-----+-----+-----+-----+-----+-----+-----+-----+
3|b|0|1|2|2|2|2|
+-----+-----+-----+-----+-----+-----+-----+-----+
4|c|0|1|2|3|3|3|3|
+-----+-----+-----+-----+-----+-----+-----+-----+
5|e|0|1|2|3|3|3|4|
+-----+-----+-----+-----+-----+-----+-----+-----+
A complexidade de tempo para este algoritmo é: O(mn), onde m e n denotam o comprimento de cada string.
Como descobrimos a maior subsequência comum? Começaremos pelo canto inferior direito. Verificaremos
de onde o valor está vindo. Se o valor está vindo da diagonal, isto é, se Table[i-1][j-1] for igual a
Tabela[i][j] - 1, empurramos s2[i] ou s1[j] (ambos são iguais) e movemos diagonalmente. Se o valor estiver vindo de cima,
isso significa que, se Table[i-1][j] for igual a Table[i][j], movemos para o topo. Se o valor estiver vindo da esquerda, isso significa que, se
Table[i][j-1] é igual a Table[i][j], movemos para a esquerda. Quando alcançamos a coluna mais à esquerda ou mais acima, nossa busca
termina. Então, retiramos os valores da pilha e os imprimimos. O pseudocódigo:
Tabela[i][j]
i := i-1 senão
j := j-1 endif
endwhile
enquanto S
Ponto a ser observado: se Table[i-1][j] e Table[i][j-1] forem iguais a Table[i][j] e Table[i-1][j-1] não for igual a Table[i][j] -
1, pode haver dois LCS para esse momento. Este pseudocódigo não considera essa situação. Você terá que resolver isso
recursivamente para encontrar vários LCSs.
A maior subsequência crescente o problema é encontrar subsequência da sequência de entrada fornecida na qual os elementos da
subsequência são classificados da ordem mais baixa para a mais alta. Todas as subsequências não são contíguas ou únicas.
Algoritmos como Longest Crescente Subsequência, Longest Comum Subsequência são usados em sistemas de controle de versão
como Git e etc.
3. Calcule o LIS da sequência resultante (fazendo uma classificação de paciência), obtendo a sequência de correspondência mais longa
de linhas, uma correspondência entre as linhas de dois documentos.
4. Repita o algoritmo em cada intervalo de linhas entre as já correspondidas.
Agora, vamos considerar um exemplo mais simples do problema LCS. Aqui, a entrada é apenas uma sequência de inteiros distintos
a1,a2,...,an., e queremos encontrar a maior subsequência crescente nela. Por exemplo, se a entrada for 7,3,8,4,2,6 , então a maior
subsequência crescente é 3,4,6.
A abordagem mais fácil é classificar os elementos de entrada em ordem crescente e aplicar o algoritmo LCS às sequências originais e
classificadas. No entanto, se você olhar para o array resultante, notará que muitos valores são os mesmos e o array parece muito repetitivo.
Isso sugere que o problema LIS (longest increasing subsequence) pode ser feito com algoritmo de programação dinâmica usando
apenas array unidimensional.
Pseudocódigo:
O programa a seguir usa A para calcular uma solução ótima. A primeira parte calcula um valor m tal que A(m) é o comprimento de uma
subsequência crescente ótima de entrada. A segunda parte calcula uma subsequência crescente ótima, mas por conveniência,
imprimimos na ordem inversa. Este programa roda em tempo O(n), então o algoritmo inteiro roda em tempo O(n^2).
Parte 1:
mÿ1
para i : 2..n se A(i)
m ÿ eu
fim se
fim para
Parte 2:
coloque
um tempo A(m) > 1 eu ÿ mÿ1
acabar
com isso enquanto
Solução recursiva:
Abordagem 1:
LIS(A[1..n]): se (n =
0) então retorne 0 m = LIS(A[1..(n ÿ
1)])
B é uma subsequência de A[1..(n ÿ 1)] com apenas elementos menores que a[n] (* seja h o tamanho de B, h
ÿ n-1 *) m = max(m, 1 + LIS(B[1..h]))
Saída m
Abordagem 2:
LIS(A[1..n], x): se (n = 0)
então retorne 0 m = LIS(A[1..(n ÿ 1)],
x) se (A[n] < x) então m = max(m, 1 +
LIS(A[1..(n ÿ 1)], A[n]))
Saída m
PRINCIPAL(A[1..n]):
retorna LIS(A[1..n], ÿ)
Abordagem 3:
LIS(A[1..n]): se (n =
0) retornar 0 m = 1
PRINCIPAL(A[1..n]):
retorna LIS(A[1..i])
Algoritmo Iterativo:
LIS(A[1..n]): Matriz
L[1..n]
(* L[i] = valor da terminação LIS (A[1..i]) *) para i = 1 para n faça
L[i] = 1 para j = 1 para i ÿ 1
faça
MAIN(A[1..n]): L =
LIS(A[1..n]) retorna o
valor máximo em L
Vamos pegar {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} como entrada. Então, a Subsequência Crescente Mais Longa para a
entrada dada é {0, 2, 6, 9, 11, 15}.
Duas strings com o mesmo conjunto de caracteres são chamadas de anagramas. Usei javascript aqui.
Criaremos um hash de str1 e aumentaremos a contagem em +1. Faremos um loop na 2ª string e verificaremos se todos os caracteres estão lá no
hash e diminuiremos o valor da chave hash. Verificaremos se todos os valores da chave hash são zero, será um anagrama.
hashMap = { s : 1,
t : 1, a :
1, c : 1,
k : 1, o :
2, v : 1,
e : 1, r :
1, f : 1, l :
1, w : 1
Você pode ver que a hashKey 'o' contém o valor 2 porque o é 2 vezes na string.
Agora faça um loop em str2 e verifique se cada caractere está presente no hashMap. Se sim, diminua o valor da chave hashMap, caso contrário,
retorne false (o que indica que não é um anagrama).
hashMap =
{ s : 0,
t : 0, a :
0, c : 0,
k : 0,
o : 0,
v : 0,
e : 0, r :
0, f : 0,
l : 0,
em : 0
}
Agora, faça um loop no objeto hashMap e verifique se todos os valores são zero na chave do hashMap.
// Verifica se o caractere str2 é a chave no mapa de hash e diminui o valor em um (-1); var valueExist
= createStr2HashMap(str2);
// Verifique se todos os valores das chaves hashMap são zero, então será um anagrama.
return isStringsAnagram(valueExist);
}
});
}
se(hashMap[i] !== 0)
{ éAnagrama = falso;
quebrar; }
senão { éAnagrama = verdadeiro;
}
}
retornar éAnagrama;
}
}
})();
printf(" "); +
+contagem;
}
enquanto(k != 2*i-1) {
}
outro {
++contagem1;
printf("%d ", (i+k-2*contagem1));
} ++k;
} contagem1 = contagem = k = 0;
printf("\n");
}
Saída
1232
34543
4567654567
898765
Entrada:
14 15 16 17 18 21 19
10 20 11 54 36 64 55
44 23 80 39 91 92 93
94 95 42
Saída:
imprimir valor no índice 14 15 16
17 18 21 36 39 42 95 94 93 92 91 64 19 10 20 11 54 80 23 44 55
ou imprimir índice 00
01 02 03 04 05 15 25 35 34 33 32 31 30 20 10 11 12 13 14 24 23 22 21
se(menorValor % 2 == 0) { retorne
menorValor/2; } senão { retorne
(menorValor+1)/2;
}
}
squarePrint(6,4);
Primeiro, vamos ver como a exponenciação de matrizes pode ajudar a representar relações recursivas.
Pré-requisitos:
Dadas duas matrizes, saiba como encontrar o produto delas. Além disso, dada a matriz produto de duas matrizes, e
uma delas, saiba como encontrar a outra matriz.
Dada uma matriz de tamanho d X d, saiba como encontrar sua enésima potência em O(d3log(n)).
Padrões:
Primeiro precisamos de uma relação recursiva e queremos encontrar uma matriz M que possa nos levar ao estado desejado a partir de uma
conjunto de estados já conhecidos. Vamos supor que conhecemos os k estados de uma dada relação de recorrência e queremos
encontre o (k+1)ésimo estado. Seja M uma matriz k X k , e construímos uma matriz A:[k X 1] a partir dos estados conhecidos do
relação de recorrência, agora queremos obter uma matriz B:[k X 1] que representará o conjunto dos próximos estados, ou seja, MXA = B
como mostrado abaixo:
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
MX | f(n-2) | = | f(n-1) |
| ...... | ...... |
| f(nk) | |f(n-k+1)|
Então, se pudermos projetar M adequadamente, nosso trabalho estará feito! A matriz será então usada para representar a recorrência
relação.
Tipo 1:
Vamos começar com o mais simples, f(n) = f(n-1) + f(n-2)
Obtemos, f(n+1) = f(n) + f(n-1).
Vamos supor que conhecemos f(n) e f(n-1); Queremos descobrir f(n+1).
A partir da situação exposta acima, a matriz A e a matriz B podem ser formadas conforme mostrado abaixo:
Matriz A Matriz B
[Nota: A matriz A será sempre projetada de tal forma que, todo estado do qual f(n+1) depende, estará presente]
Agora, precisamos projetar uma matriz 2X2 M tal que ela satisfaça MXA = B, conforme declarado acima.
O primeiro elemento de B é f(n+1) que na verdade é f(n) + f(n-1). Para obter isso, da matriz A, precisamos de 1 X f(n) e 1
X f(n-1). Portanto, a primeira linha de M será [1 1].
[Nota: ----- significa que não estamos preocupados com esse valor.]
Da mesma forma, o 2º item de B é f(n), que pode ser obtido simplesmente tomando 1 X f(n) de A, então a 2ª linha de M é [1 0].
|1 1 | X | f(n) | = | f(n+1) |
|1 0| | f(n-1) | | f(n) |
Tipo 2:
Vamos tornar isso um pouco mais complexo: encontre f(n) = a X f(n-1) + b X f(n-2), onde a e b são constantes.
Isso nos diz que f(n+1) = a X f(n) + b X f(n-1).
Até aqui, deve estar claro que a dimensão das matrizes será igual ao número de dependências, ou seja,
neste exemplo em particular, novamente 2. Então, para A e B, podemos construir duas matrizes de tamanho 2 X 1:
Agora para f(n+1) = a X f(n) + b X f(n-1), precisamos de [a, b] na primeira linha da matriz objetivo M. E para a 2ª
item em B, ou seja, f(n) já temos isso na matriz A, então apenas pegamos isso, o que leva, a 2ª linha da matriz M
para [1 0]. Desta vez obtemos:
| b | X | f(n) | = | f(n+1) |
um | 1 0 | | f(n-1) | | f(n) |
Tipo 3:
Se você sobreviveu até esse estágio, você ficou muito mais velho, agora vamos encarar uma relação um pouco complexa: encontre f(n) =
a X f(n-1) + c X f(n-3)?
Opa! Alguns minutos atrás, tudo o que víamos eram estados contíguos, mas aqui, o estado f(n-2) está faltando. Agora?
Na verdade isso não é mais um problema, podemos converter a relação da seguinte forma: f(n) = a X f(n-1) + 0 X f(n-2) +
c X f(n-3), deduzindo f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2). Agora, vemos que, na verdade, esta é uma forma
descrito no Tipo 2. Então aqui a matriz objetiva M será 3 X 3, e os elementos são:
| um 0 c | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 1 0 | | f(n-2) | | f(n-1) |
Eles são calculados da mesma forma que o tipo 2. Se você achar difícil, tente fazer isso em papel e caneta.
Tipo 4:
A vida está ficando complexa como o inferno, e o Sr. Problema agora pede que você encontre f(n) = f(n-1) + f(n-2) + c onde c é qualquer
constante.
Agora, isso é algo novo e tudo o que vimos no passado, após a multiplicação, cada estado em A se transforma em seu próximo
estado em B.
Então, normalmente não conseguimos fazer isso da maneira anterior, mas que tal adicionarmos c como um estado:
| f(n) | | f(n+1) |
MX | f(n-1) | = | f(n) |
| c || | c
Agora, não é muito difícil projetar M. Veja como é feito, mas não se esqueça de verificar:
Tipo 5:
Vamos colocar tudo junto: encontre f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e. Vamos deixar isso como um exercício para
você. Primeiro tente descobrir os estados e a matriz M. E verifique se ela corresponde à sua solução. Encontre também a matriz A e
B.
| um 0 cd 1 |
|10000|
|01000|
|00100|
|00001|
Tipo 6:
Resumidamente:
Aqui, podemos dividir as funções na base de ímpar e par e manter 2 matrizes diferentes para ambas e calcular
separadamente.
Tipo 7:
Sentindo-se pouco confiante demais? Bom para você. Às vezes, podemos precisar manter mais de uma recorrência, onde
eles estão interessados. Por exemplo, deixe uma recorrência re;atopm ser:
Aqui, a recorrência g(n) depende de f(n) e pode ser calculada na mesma matriz, mas de forma aumentada.
dimensões. A partir delas, vamos primeiro projetar as matrizes A e B.
Matriz A | Matriz B
g(n) | | g(n-1) | | | g(n+1) |
f(n+1) | | f(n) | | g(n) |
| f(n+2) |
| f(n+1) |
Aqui, g(n+1) = 2g(n-1) + f(n+1) e f(n+2) = 2f(n+1) + 2f(n). Agora, usando os processos declarados acima, nós
pode encontrar a matriz objetiva M como sendo:
|2210|
|1000|
|0022|
|0010|
Então, essas são as categorias básicas de relações de recorrência que são usadas para resolver por meio dessa técnica simples.
Este é um algoritmo polinomial para obter a cobertura mínima de vértices de um grafo não direcionado conectado. A complexidade de tempo deste
algoritmo é O(n2)
X <- [Link]()
para v em X faça
Lista<Vértice> adjacenteVertices1 <- [Link](v)
[Link](v)
[Link](vértice)
retornar C
podemos usar a classificação por bucket para classificar os vértices de acordo com seu grau porque o valor máximo de graus é (n-1),
onde n é o número de vértices, então a complexidade de tempo da classificação será O(n)
Em geral, DTW é um método que calcula uma correspondência ótima entre duas sequências fornecidas com certas
restrições. Mas vamos nos ater aos pontos mais simples aqui. Digamos que temos duas sequências de voz Sample e Test, e
queremos verificar se essas duas sequências correspondem ou não. Aqui, a sequência de voz se refere ao sinal digital convertido de
sua voz. Pode ser a amplitude ou frequência da sua voz que denota as palavras que você diz. Vamos supor:
Amostra = {1, 2, 3, 5, 5, 5, 6}
Teste = {1, 1, 2, 2, 3, 5}
Primeiro, definimos a distância entre dois pontos, d(x, y) onde x e y representam os dois pontos. Seja,
Vamos criar uma matriz 2D Table usando essas duas sequências. Calcularemos as distâncias entre cada ponto de
Faça uma amostra com todos os pontos do teste e encontre a correspondência ideal entre eles.
+------+------+------+------+------+------+------+ ------+
| | 0| 1| 1| 2| 2|3| 5|
+------+------+------+------+------+------+------+ ------+
| 0| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 1| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 2| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 3| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5| | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 6| | | | | | | |
+------+------+------+------+------+------+------+ ------+
Aqui, a Tabela[i][j] representa a distância ótima entre duas sequências se considerarmos a sequência até
Amostra[i] e Teste[j], considerando todas as distâncias ótimas que observamos antes.
Para a primeira linha, se não pegarmos nenhum valor de Sample, a distância entre este e Test será infinita. Então colocamos
infinito na primeira linha. O mesmo vale para a primeira coluna. Se não pegarmos nenhum valor de Test, a distância entre este
um e Sample também será infinito. E a distância entre 0 e 0 será simplesmente 0. Obtemos,
+------+------+------+------+------+------+------+ ------+
| | 0| 1| 1| 2| 2|3| 5|
+------+------+------+------+------+------+------+ ------+
| 0| 0 | informações | informações | informações | informações | informações | informações |
+------+------+------+------+------+------+------+ ------+
| 1 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 2 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 3 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 5 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
| 6 | informações | | | | | | |
+------+------+------+------+------+------+------+ ------+
Agora, para cada etapa, consideraremos a distância entre cada ponto em questão e adicionaremos o mínimo
distância que encontramos até agora. Isso nos dará a distância ótima de duas sequências até essa posição. Nossa fórmula
vai ser,
Para o primeiro, d(1, 1) = 0, Table[0][0] representa o mínimo. Então o valor de Table[1][1] será 0 + 0 = 0. Para
o segundo, d(1, 2) = 0. Table[1][1] representa o mínimo. O valor será: Table[1][2] = 0 + 0 = 0. Se
continue assim, após terminar a tabela ficará assim:
+------+------+------+------+------+------+------+ ------+
| | 0| 1| 1| 2| 2|3| 5|
+------+------+------+------+------+------+------+ ------+
| 0| 0 | informações | informações | informações | informações | informações | informações |
+------+------+------+------+------+------+------+ ------+
| 1 | informações | 0| 0| 1| 2|4|8|
+------+------+------+------+------+------+------+ ------+
| 2 | informações | 1| 1| 0|0| 1|4|
+------+------+------+------+------+------+------+ ------+
| 3 | informações | 3| 3| 1| 1|0| 2|
+------+------+------+------+------+------+------+ ------+
| 5 | informações | 7| 7|4|4| 2|0|
+------+------+------+------+------+------+------+ ------+
| 5 | informações | 11 | 11 | 7| 7|4|0|
+------+------+------+------+------+------+------+ ------+
| 5 | inf | 15 | 15 | 10 | 10 | 6 | 0 |
+------+------+------+------+------+------+------+ ------+
| 6 | inf | 20 | 20 | 14 | 14 | 9 | 1|
+------+------+------+------+------+------+------+ ------+
O valor na Tabela[7][6] representa a distância máxima entre essas duas sequências dadas. Aqui 1 representa
a distância máxima entre Amostra e Teste é 1.
Agora, se voltarmos do último ponto até o ponto inicial (0, 0) , obteremos uma longa linha que
move horizontalmente, verticalmente e diagonalmente. Nosso procedimento de backtracking será:
Continuaremos até chegarmos a (0, 0). Cada movimento tem seu próprio significado:
Um movimento horizontal representa exclusão. Isso significa que nossa sequência de teste acelerou durante esse intervalo.
Um movimento vertical representa inserção. Isso significa que nossa sequência de teste desacelerou durante esse intervalo.
Um movimento diagonal representa correspondência. Durante esse período, Teste e Amostra foram os mesmos.
fim para
para i de 1 a m
Tabela[0][i] := fim infinito para
Tabela[0][0] := 0 para i de
1 a n para j de 1 a m
Também podemos adicionar uma restrição de localidade. Ou seja, exigimos que se Sample[i] for correspondido com Test[j], então |i - j|
não seja maior que w, um parâmetro de janela.
Complexidade:
*
A complexidade do cálculo de DTW é O(m) . As n) onde m e n representam o comprimento de cada sequência. Mais rápido
técnicas para cálculo de DTW incluem PrunedDTW, SparseDTW e FastDTW.
Aplicações:
A forma Real e Complexa da DFT (Discrete Fourier Transforms) pode ser usada para executar análise de frequência ou síntese para
quaisquer sinais discretos e periódicos. A FFT (Fast Fourier Transform) é uma implementação da DFT que pode ser executada
rapidamente em CPUs modernas.
O método mais simples e talvez mais conhecido para calcular a FFT é o algoritmo Radix-2 Decimation in Time.
A FFT Radix-2 funciona decompondo um sinal de domínio de tempo de N pontos em N sinais de domínio de tempo, cada um composto
de um único ponto
A decomposição do sinal, ou 'decimação no tempo' é obtida pela reversão de bits dos índices para a matriz de dados do domínio do
tempo. Assim, para um sinal de dezesseis pontos, a amostra 1 (Binário 0001) é trocada pela amostra 8 (1000), a amostra 2 (0010) é
trocada pela 4 (0100) e assim por diante. A troca de amostras usando a técnica de reversão de bits pode ser obtida simplesmente
em software, mas limita o uso da FFT Radix 2 a sinais de comprimento N = 2^M.
O valor de um sinal de 1 ponto no domínio do tempo é igual ao seu valor no domínio da frequência, portanto, essa matriz de pontos
de domínio de tempo único decompostos não requer transformação para se tornar uma matriz de pontos de domínio da frequência.
Os N pontos únicos; no entanto, precisam ser reconstruídos em um espectro de frequência de N pontos. A reconstrução ótima
do espectro de frequência completo é realizada usando cálculos de borboleta. Cada estágio de reconstrução na FFT Radix-2 realiza
um número de borboletas de dois pontos, usando um conjunto semelhante de funções de ponderação exponencial, Wn^R.
A FFT remove cálculos redundantes na Transformada Discreta de Fourier explorando a periodicidade de Wn^R.
A reconstrução espectral é concluída em estágios log2(N) de cálculos de borboleta, fornecendo X[K]; os dados de domínio de
frequência real e imaginário em forma retangular. Para converter para magnitude e fase (coordenadas polares), é necessário
encontrar o valor absoluto, ÿ(Re2 + Im2), e o argumento, tan-1(Im/Re).
O diagrama de fluxo borboleta completo para uma FFT Radix 2 de oito pontos é mostrado abaixo. Observe que os sinais de entrada
foram reordenados anteriormente de acordo com o procedimento de dizimação no tempo descrito anteriormente.
A FFT normalmente opera em entradas complexas e produz uma saída complexa. Para sinais reais, a parte imaginária pode ser definida
como zero e a parte real definida como o sinal de entrada, x[n], no entanto, muitas otimizações são possíveis envolvendo a transformação
de dados somente reais. Os valores de Wn^R usados durante a reconstrução podem ser determinados usando a equação de ponderação
exponencial.
O valor de R (o poder de ponderação exponencial) é determinado pelo estágio atual na reconstrução espectral e pelo cálculo atual dentro
de uma borboleta específica.
Exemplo de código AC/C++ para calcular o FFT Radix 2 pode ser encontrado abaixo. Esta é uma implementação simples que funciona
para qualquer tamanho N onde N é uma potência de 2. É aproximadamente 3x mais lento do que a implementação FFTw mais rápida, mas
ainda é uma base muito boa para otimização futura ou para aprender sobre como este algoritmo funciona.
#incluir <math.h>
*M = (int)ceil(log10((double)N) * log10_2_INV);// M é o número de estágios a serem executados. 2^M = N int NN = (int)pow(2.0, *M);
retornar verdadeiro;
}
// Variáveis Inteiras
int HiIndex; // HiIndex é o índice da matriz DFT para o valor superior de cada
cálculo borboleta
int sem sinal iaddr; int ii; int // bitmask para reversão de bits
MM1 = M // Campo de bits inteiro para reversão de bits (Decimação no Tempo)
- 1;
DFT->Re = pX->Re; // Atualiza a matriz complexa com sinal de domínio de tempo classificado por endereço
x[n]
DFT->Im = pX->Im; // NB: O imaginário é sempre zero
}
DoisPi_NP = DoisPi_N*P;
//[Link] = cos(TwoPi_NP*j)
[Link] = cos(DoisPi_N*P*j); // Calcular Wn (Real e Imaginário)
[Link] = -sin(DoisPi_N*P*j);
}
para (HiIndex = j; HiIndex < N; HiIndex += BSep) // Loop para HiIndex Etapa BSep
borboletas por estágio
{
pHi = pDFT + HiIndex; pLo // Apontar para um valor mais alto
= pHi + BWidth; para // Aponte para o valor mais baixo (Observe que o VC++ ajusta
espaçamento entre elementos)
//CAdd (pHi, &TEMP, pHi); pHi- // Encontre novo Hivalue (adição complexa)
>Re = (pHi->Re + [Link]);
pHi->Im = (pHi->Im + [Link]);
}
outro
{
[Link] = pLo->Re;
[Link] = pLo->Im;
//CAdd (pHi, &TEMP, pHi); pHi- // Encontre novo Hivalue (adição complexa)
>Re = (pHi->Re + [Link]);
pHi->Im = (pHi->Im + [Link]);
}
}
}
}
Devido à forte dualidade da Transformada de Fourier, ajustar a saída de uma transformada direta pode produzir a FFT inversa. Dados no domínio
de frequência podem ser convertidos para o domínio de tempo pelo seguinte método:
1. Encontre o conjugado complexo dos dados do domínio da frequência invertendo o componente imaginário para todos
instâncias de K.
Nota: tanto os dados de domínio de frequência quanto os de domínio de tempo são variáveis complexas. Normalmente, o componente
imaginário do sinal de domínio de tempo após uma FFT inversa é zero ou ignorado como erro de arredondamento. Aumentar a precisão das
variáveis de float de 32 bits para double de 64 bits ou double longo de 128 bits reduz significativamente os erros de arredondamento
produzidos por várias operações FFT consecutivas.
#incluir <math.h>
x = 0;
DFT = 0;
throw "rad2InverseFFT(): N deve ser uma potência de 2 para FFT inversa de base 2";
}
int eu;
complexo* x;
para ( i = 0, x = pX; i < N; i++, x++){
x->Re *= NN; x- // Divida o domínio do tempo por N para uma escala de amplitude correta
>Im *= -1; // Alterar o sinal do ImX
}
}
Apêndice A: Pseudocódigo
Seção A.1: Ações variáveis
Digitado
int a = 1
int a := 1
deixe int a = 1
int a <- 1
Nenhum tipo
a=1
a := 1
deixe a = 1
um <- 1
Desde que o nome da função, a instrução de retorno e os parâmetros sejam claros, está tudo bem.
definição incr n
retornar n + 1
ou
deixe incr(n) = n + 1
ou
são todos bem claros, então você pode usá-los. Tente não ser ambíguo com uma afetação variável
Créditos
Muito obrigado a todas as pessoas da documentação do Stack Overflow que ajudaram a fornecer este conteúdo,
mais alterações podem ser enviadas para web@[Link] para que novos conteúdos sejam publicados ou atualizados