DAA - Guia rápido

Um algoritmo é um conjunto de etapas de operações para resolver um problema de execução de cálculos, processamento de dados e tarefas de raciocínio automatizadas. Um algoritmo é um método eficiente que pode ser expresso em uma quantidade finita de tempo e espaço.

Um algoritmo é a melhor maneira de representar a solução de um problema específico de uma forma muito simples e eficiente. Se tivermos um algoritmo para um problema específico, podemos implementá-lo em qualquer linguagem de programação, o que significa que oalgorithm is independent from any programming languages.

Projeto de Algoritmo

Os aspectos importantes do projeto de algoritmo incluem a criação de um algoritmo eficiente para resolver um problema de maneira eficiente usando o mínimo de tempo e espaço.

Para resolver um problema, diferentes abordagens podem ser seguidas. Alguns deles podem ser eficientes com relação ao consumo de tempo, enquanto outras abordagens podem ser eficientes em termos de memória. No entanto, é preciso ter em mente que o consumo de tempo e o uso de memória não podem ser otimizados simultaneamente. Se exigirmos que um algoritmo seja executado em menos tempo, teremos que investir em mais memória e se exigirmos que um algoritmo seja executado com menos memória, precisaremos ter mais tempo.

Etapas de desenvolvimento de problema

As etapas a seguir estão envolvidas na solução de problemas computacionais.

• Definição de problema
• Desenvolvimento de um modelo
• Especificação de um Algoritmo
• Projetando um Algoritmo
• Verificar a exatidão de um algoritmo
• Análise de um Algoritmo
• Implementação de um Algoritmo
• Teste de programa
• Documentation

Características dos Algoritmos

As principais características dos algoritmos são as seguintes -

• Algoritmos devem ter um nome único

• Os algoritmos devem ter definido explicitamente um conjunto de entradas e saídas

• Algoritmos são bem ordenados com operações inequívocas

• Algoritmos param em um período finito de tempo. Algoritmos não devem ser executados para o infinito, ou seja, um algoritmo deve terminar em algum ponto

Pseudo-código

O pseudocódigo fornece uma descrição de alto nível de um algoritmo sem a ambigüidade associada ao texto simples, mas também sem a necessidade de conhecer a sintaxe de uma linguagem de programação específica.

O tempo de execução pode ser estimado de uma maneira mais geral usando o Pseudocódigo para representar o algoritmo como um conjunto de operações fundamentais que podem então ser contadas.

Diferença entre Algoritmo e Pseudocódigo

Um algoritmo é uma definição formal com algumas características específicas que descreve um processo, que pode ser executado por uma máquina de computador Turing-completa para realizar uma tarefa específica. Geralmente, a palavra "algoritmo" pode ser usada para descrever qualquer tarefa de alto nível em ciência da computação.

Por outro lado, pseudocódigo é uma descrição legível por humanos informal e (frequentemente rudimentar) de um algoritmo que deixa muitos detalhes granulares dele. A escrita de um pseudocódigo não possui restrição de estilos e seu único objetivo é descrever as etapas de alto nível do algoritmo de uma maneira muito realista em linguagem natural.

Por exemplo, a seguir está um algoritmo para Insertion Sort.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

Aqui está um pseudocódigo que descreve como o processo abstrato de alto nível mencionado acima no algoritmo Insertion-Sort poderia ser descrito de uma forma mais realista.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

Neste tutorial, os algoritmos serão apresentados na forma de pseudocódigo, que é semelhante em muitos aspectos a C, C ++, Java, Python e outras linguagens de programação.

Na análise teórica de algoritmos, é comum estimar sua complexidade no sentido assintótico, ou seja, estimar a função de complexidade para uma entrada arbitrariamente grande. O termo"analysis of algorithms" foi cunhado por Donald Knuth.

A análise de algoritmo é uma parte importante da teoria da complexidade computacional, que fornece estimativa teórica para os recursos necessários de um algoritmo para resolver um problema computacional específico. A maioria dos algoritmos é projetada para funcionar com entradas de comprimento arbitrário. A análise de algoritmos é a determinação da quantidade de recursos de tempo e espaço necessários para executá-lo.

Normalmente, a eficiência ou o tempo de execução de um algoritmo é declarado como uma função relacionando o comprimento de entrada ao número de etapas, conhecido como time complexity, ou volume de memória, conhecido como space complexity.

A necessidade de análise

Neste capítulo, discutiremos a necessidade de análise de algoritmos e como escolher um algoritmo melhor para um problema específico, visto que um problema computacional pode ser resolvido por algoritmos diferentes.

Ao considerar um algoritmo para um problema específico, podemos começar a desenvolver o reconhecimento de padrões de modo que tipos semelhantes de problemas possam ser resolvidos com a ajuda desse algoritmo.

Os algoritmos geralmente são bem diferentes uns dos outros, embora o objetivo desses algoritmos seja o mesmo. Por exemplo, sabemos que um conjunto de números pode ser classificado usando diferentes algoritmos. O número de comparações realizadas por um algoritmo pode variar com outros para a mesma entrada. Portanto, a complexidade de tempo desses algoritmos pode ser diferente. Ao mesmo tempo, precisamos calcular o espaço de memória necessário para cada algoritmo.

A análise do algoritmo é o processo de analisar a capacidade de resolução de problemas do algoritmo em termos de tempo e tamanho necessários (o tamanho da memória para armazenamento durante a implementação). No entanto, a principal preocupação da análise de algoritmos é o tempo ou desempenho necessários. Geralmente, realizamos os seguintes tipos de análise -

• Worst-case - O número máximo de etapas realizadas em qualquer instância de tamanho a.

• Best-case - O número mínimo de etapas realizadas em qualquer instância de tamanho a.

• Average case - Um número médio de etapas realizadas em qualquer instância de tamanho a.

• Amortized - Uma sequência de operações aplicadas à entrada de tamanho a média ao longo do tempo.

Para resolver um problema, precisamos considerar o tempo e também a complexidade do espaço, pois o programa pode ser executado em um sistema onde a memória é limitada, mas o espaço adequado está disponível ou pode ser vice-versa. Neste contexto, se compararmosbubble sort e merge sort. A classificação por bolha não requer memória adicional, mas a classificação por mesclagem requer espaço adicional. Embora a complexidade de tempo da classificação por bolha seja maior em comparação com a classificação por mesclagem, podemos precisar aplicar a classificação por bolha se o programa precisar ser executado em um ambiente onde a memória é muito limitada.

Para medir o consumo de recursos de um algoritmo, diferentes estratégias são usadas, conforme discutido neste capítulo.

Análise Assintótica

O comportamento assintótico de uma função f(n) refere-se ao crescimento de f(n) Como n fica grande.

Normalmente ignoramos pequenos valores de n, uma vez que geralmente estamos interessados ​​em estimar a lentidão do programa com grandes entradas.

Uma boa regra prática é que quanto mais lenta a taxa de crescimento assintótico, melhor será o algoritmo. Embora nem sempre seja verdade.

Por exemplo, um algoritmo linear $f(n) = d * n + k$ é sempre assintoticamente melhor do que um quadrático, $f(n) = c.n^2 + q$.

Resolvendo Equações de Recorrência

Uma recorrência é uma equação ou desigualdade que descreve uma função em termos de seu valor em entradas menores. As recorrências são geralmente usadas no paradigma de dividir e conquistar.

Vamos considerar T(n) ser o tempo de execução em um problema de tamanho n.

Se o tamanho do problema for pequeno o suficiente, diga n < c Onde c é uma constante, a solução simples leva um tempo constante, que é escrito como θ(1). Se a divisão do problema resultar em uma série de subproblemas com tamanho$\frac{n}{b}$.

Para resolver o problema, o tempo necessário é a.T(n/b). Se considerarmos que o tempo necessário para a divisão éD(n) e o tempo necessário para combinar os resultados dos subproblemas é C(n), a relação de recorrência pode ser representada como -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

Uma relação de recorrência pode ser resolvida usando os seguintes métodos -

• Substitution Method - Neste método, adivinhamos um limite e, usando a indução matemática, provamos que nossa suposição estava correta.

• Recursion Tree Method - Neste método, uma árvore de recorrência é formada onde cada nó representa o custo.

• Master’s Theorem - Esta é outra técnica importante para encontrar a complexidade de uma relação de recorrência.

Análise Amortizada

A análise amortizada é geralmente usada para certos algoritmos em que uma sequência de operações semelhantes é executada.

• A análise amortizada fornece um limite sobre o custo real de toda a sequência, em vez de limitar o custo da sequência de operações separadamente.

• A análise amortizada difere da análise de caso médio; probabilidade não está envolvida na análise amortizada. A análise amortizada garante o desempenho médio de cada operação no pior caso.

Não é apenas uma ferramenta de análise, é uma forma de pensar o design, uma vez que design e análise estão intimamente relacionados.

Método Agregado

O método agregado fornece uma visão global de um problema. Neste método, sen as operações levam o tempo do pior caso T(n)no total. Então, o custo amortizado de cada operação éT(n)/n. Embora operações diferentes possam levar um tempo diferente, neste método os custos variáveis ​​são negligenciados.

Método de Contabilidade

Nesse método, diferentes encargos são atribuídos a diferentes operações de acordo com seu custo real. Se o custo amortizado de uma operação exceder seu custo real, a diferença é atribuída ao objeto como crédito. Este crédito ajuda a pagar por operações posteriores cujo custo amortizado seja inferior ao custo real.

Se o custo real e o custo amortizado de i^th operação são $c_{i}$ e $\hat{c_{l}}$, então

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

Método Potencial

Este método representa o trabalho pré-pago como energia potencial, ao invés de considerar o trabalho pré-pago como crédito. Essa energia pode ser liberada para pagar por operações futuras.

Se realizarmos n operações começando com uma estrutura de dados inicial D₀. Vamos considerar,c_i como o custo real e D_i como estrutura de dados de i^thOperação. A função potencial Ф mapeia para um número real Ф (D_i), o potencial associado de D_i. O custo amortizado$\hat{c_{l}}$ pode ser definido por

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

Portanto, o custo amortizado total é

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

Mesa Dinâmica

Se o espaço alocado para a mesa não for suficiente, devemos copiar a mesa para uma mesa de tamanho maior. Da mesma forma, se um grande número de membros for apagado da tabela, é uma boa ideia realocar a tabela com um tamanho menor.

Usando a análise amortizada, podemos mostrar que o custo amortizado de inserção e exclusão é constante e o espaço não utilizado em uma tabela dinâmica nunca excede uma fração constante do espaço total.

No próximo capítulo deste tutorial, discutiremos brevemente as Notações Assintóticas.

Na concepção de Algoritmo, a análise da complexidade de um algoritmo é um aspecto essencial. Principalmente, a complexidade algorítmica se preocupa com seu desempenho, quão rápido ou lento ele funciona.

A complexidade de um algoritmo descreve a eficiência do algoritmo em termos da quantidade de memória necessária para processar os dados e o tempo de processamento.

A complexidade de um algoritmo é analisada em duas perspectivas: Time e Space.

Complexidade de tempo

É uma função que descreve a quantidade de tempo necessária para executar um algoritmo em termos do tamanho da entrada. "Tempo" pode significar o número de acessos à memória realizados, o número de comparações entre inteiros, o número de vezes que algum loop interno é executado ou alguma outra unidade natural relacionada à quantidade de tempo real que o algoritmo levará.

Complexidade do Espaço

É uma função que descreve a quantidade de memória que um algoritmo leva em termos do tamanho da entrada para o algoritmo. Freqüentemente falamos de memória "extra" necessária, sem contar a memória necessária para armazenar a própria entrada. Novamente, usamos unidades naturais (mas de comprimento fixo) para medir isso.

A complexidade do espaço às vezes é ignorada porque o espaço usado é mínimo e / ou óbvio, mas às vezes torna-se uma questão tão importante quanto o tempo.

Notações Assintóticas

O tempo de execução de um algoritmo depende do conjunto de instruções, velocidade do processador, velocidade de E / S do disco, etc. Portanto, estimamos a eficiência de um algoritmo assintoticamente.

A função de tempo de um algoritmo é representada por T(n), Onde n é o tamanho de entrada.

Diferentes tipos de notações assintóticas são usados ​​para representar a complexidade de um algoritmo. As seguintes notações assintóticas são usadas para calcular a complexidade do tempo de execução de um algoritmo.

• O - Grande Oh

• Ω - Grande ômega

• θ - Big theta

• o - pequeno oh

• ω - pequeno omega

O: Limite superior assintótico

'O' (Big Oh) é a notação mais comumente usada. Uma funçãof(n) pode ser representado é a ordem de g(n) isso é O(g(n)), se houver um valor de número inteiro positivo n Como n₀ e uma constante positiva c tal que -

$f(n)\leqslant c.g(n)$ para $n > n_{0}$ em todo caso

Portanto, função g(n) é um limite superior para a função f(n), Como g(n) cresce mais rápido que f(n).

Exemplo

Vamos considerar uma determinada função, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considerando $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ para todos os valores de $n > 2$

Portanto, a complexidade de f(n) pode ser representado como $O(g(n))$, ie $O(n^3)$

Ω: Limite inferior assintótico

Nós dizemos isso $f(n) = \Omega (g(n))$ quando existe constante c este $f(n)\geqslant c.g(n)$ para todos os valores suficientemente grandes de n. Aquiné um número inteiro positivo. Significa funçãog é um limite inferior para a função f; depois de um certo valor den, f nunca irá abaixo g.

Exemplo

Vamos considerar uma determinada função, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

Considerando $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ para todos os valores de $n > 0$.

Portanto, a complexidade de f(n) pode ser representado como $\Omega (g(n))$, ie $\Omega (n^3)$

θ: Limite Tight Assintótico

Nós dizemos isso $f(n) = \theta(g(n))$ quando existem constantes c₁ e c₂ este $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ para todos os valores suficientemente grandes de n. Aquin é um número inteiro positivo.

Isso significa função g é um limite estreito para a função f.

Exemplo

Vamos considerar uma determinada função, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considerando $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ para todos os grandes valores de n.

Portanto, a complexidade de f(n) pode ser representado como $\theta (g(n))$, ie $\theta (n^3)$.

O - Notação

O limite superior assintótico fornecido por O-notationpode ou não ser assintoticamente apertado. O limite$2.n^2 = O(n^2)$ é assintoticamente rígido, mas o limite $2.n = O(n^2)$ não é.

Nós usamos o-notation para denotar um limite superior que não é assintoticamente restrito.

Nós definimos formalmente o(g(n)) (pouco-oh de g de n) como o conjunto f(n) = o(g(n)) para qualquer constante positiva $c > 0$ e existe um valor $n_{0} > 0$, de tal modo que $0 \leqslant f(n) \leqslant c.g(n)$.

Intuitivamente, no o-notation, a função f(n) torna-se insignificante em relação a g(n) Como naproxima-se do infinito; isso é,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

Exemplo

Vamos considerar a mesma função, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considerando $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

Portanto, a complexidade de f(n) pode ser representado como $o(g(n))$, ie $o(n^4)$.

ω - Notação

Nós usamos ω-notationpara denotar um limite inferior que não é assintoticamente rígido. Formalmente, no entanto, definimosω(g(n)) (pequeno-ômega de g de n) como o conjunto f(n) = ω(g(n)) para qualquer constante positiva C > 0 e existe um valor $n_{0} > 0$, de modo que $ 0 \ leqslant cg (n) <f (n) $.

Por exemplo, $\frac{n^2}{2} = \omega (n)$, mas $\frac{n^2}{2} \neq \omega (n^2)$. A relação$f(n) = \omega (g(n))$ implica que existe o seguinte limite

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

Isso é, f(n) torna-se arbitrariamente grande em relação a g(n) Como n se aproxima do infinito.

Exemplo

Vamos considerar a mesma função, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considerando $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

Portanto, a complexidade de f(n) pode ser representado como $o(g(n))$, ie $\omega (n^2)$.

Análise Apriori e Apostiari

A análise a priori significa que a análise é realizada antes de executá-la em um sistema específico. Esta análise é uma fase em que uma função é definida a partir de algum modelo teórico. Portanto, determinamos a complexidade de tempo e espaço de um algoritmo apenas olhando para o algoritmo, em vez de executá-lo em um sistema específico com uma memória, processador e compilador diferentes.

A análise apostária de um algoritmo significa que realizamos a análise de um algoritmo somente depois de executá-lo em um sistema. Depende diretamente do sistema e das mudanças de sistema para sistema.

Em uma indústria, não podemos realizar a análise Apostiari, pois o software é geralmente feito para um usuário anônimo, que o executa em um sistema diferente dos existentes na indústria.

A priori, é a razão pela qual usamos notações assintóticas para determinar a complexidade do tempo e do espaço à medida que mudam de computador para computador; entretanto, assintoticamente, eles são os mesmos.

Neste capítulo, discutiremos a complexidade dos problemas computacionais com relação à quantidade de espaço que um algoritmo requer.

A complexidade do espaço compartilha muitas das características da complexidade do tempo e serve como uma forma adicional de classificar os problemas de acordo com suas dificuldades computacionais.

O que é a complexidade do espaço?

A complexidade do espaço é uma função que descreve a quantidade de memória (espaço) que um algoritmo leva em termos da quantidade de entrada para o algoritmo.

Costumamos falar de extra memorynecessário, sem contar a memória necessária para armazenar a própria entrada. Novamente, usamos unidades naturais (mas de comprimento fixo) para medir isso.

Podemos usar bytes, mas é mais fácil usar, digamos, o número de inteiros usados, o número de estruturas de tamanho fixo, etc.

No final, a função que criarmos será independente do número real de bytes necessários para representar a unidade.

A complexidade do espaço às vezes é ignorada porque o espaço usado é mínimo e / ou óbvio, no entanto, às vezes se torna uma questão tão importante quanto a complexidade do tempo

Definição

Deixei M seja um determinista Turing machine (TM)que pára em todas as entradas. A complexidade do espaço deM é a função $f \colon N \rightarrow N$, Onde f(n) é o número máximo de células da fita e M verifica qualquer entrada de comprimento M. Se a complexidade do espaço deM é f(n), Nós podemos dizer que M corre no espaço f(n).

Estimamos a complexidade espacial da máquina de Turing usando notação assintótica.

Deixei $f \colon N \rightarrow R^+$ser uma função. As classes de complexidade do espaço podem ser definidas da seguinte forma -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE é a classe de linguagens que são decidíveis no espaço polinomial em uma máquina de Turing determinística.

Em outras palavras, PSPACE = U_k SPACE (n^k)

Teorema de Savitch

Um dos primeiros teoremas relacionado à complexidade do espaço é o teorema de Savitch. De acordo com este teorema, uma máquina determinística pode simular máquinas não determinísticas usando uma pequena quantidade de espaço.

Para a complexidade do tempo, essa simulação parece exigir um aumento exponencial no tempo. Para a complexidade do espaço, este teorema mostra que qualquer máquina de Turing não determinística que usaf(n) espaço pode ser convertido em uma TM determinística que usa f²(n) espaço.

Portanto, o teorema de Savitch afirma que, para qualquer função, $f \colon N \rightarrow R^+$, Onde $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

Relacionamento entre classes de complexidade

O diagrama a seguir descreve a relação entre diferentes classes de complexidade.

Até agora, não discutimos as classes P e NP neste tutorial. Estes serão discutidos mais tarde.

Muitos algoritmos são recursivos por natureza para resolver um determinado problema de forma recursiva, lidando com subproblemas.

Dentro divide and conquer approach, um problema é dividido em problemas menores, então os problemas menores são resolvidos independentemente e, finalmente, as soluções de problemas menores são combinadas em uma solução para o grande problema.

Geralmente, os algoritmos de divisão e conquista têm três partes -

• Divide the problem em uma série de subproblemas que são instâncias menores do mesmo problema.

• Conquer the sub-problemsresolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como casos básicos.

• Combine the solutions para os subproblemas na solução para o problema original.

Prós e contras da abordagem dividir e conquistar

A abordagem de divisão e conquista suporta paralelismo, pois os subproblemas são independentes. Portanto, um algoritmo, que é projetado usando essa técnica, pode ser executado no sistema multiprocessador ou em diferentes máquinas simultaneamente.

Nesta abordagem, a maioria dos algoritmos são projetados usando recursão, portanto, o gerenciamento de memória é muito alto. Para a pilha de função recursiva é usada, onde o estado da função precisa ser armazenado.

Aplicação da Abordagem Dividir e Conquistar

A seguir estão alguns problemas, que são resolvidos usando a abordagem de dividir para conquistar.

• Encontrar o máximo e o mínimo de uma sequência de números
• Multiplicação da matriz de Strassen
• Mesclar classificação
• Busca binária

Vamos considerar um problema simples que pode ser resolvido pela técnica de dividir para conquistar.

Declaração do Problema

O problema Max-Min na análise de algoritmos é encontrar o valor máximo e mínimo em uma matriz.

Solução

Para encontrar os números máximo e mínimo em uma determinada matriz numbers[] do tamanho n, o seguinte algoritmo pode ser usado. Primeiro estamos representando onaive method e então apresentaremos divide and conquer approach.

Método Naïve

O método ingênuo é um método básico para resolver qualquer problema. Neste método, o número máximo e mínimo podem ser encontrados separadamente. Para encontrar os números máximo e mínimo, o seguinte algoritmo simples pode ser usado.

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

Análise

O número de comparação no método ingênuo é 2n - 2.

O número de comparações pode ser reduzido usando a abordagem de dividir para conquistar. A seguir está a técnica.

Abordagem de divisão e conquista

Nessa abordagem, a matriz é dividida em duas metades. Então, usando a abordagem recursiva, os números máximo e mínimo em cada metade são encontrados. Posteriormente, retorne o máximo de dois máximos de cada metade e o mínimo de dois mínimos de cada metade.

Neste problema, o número de elementos em uma matriz é $y - x + 1$, Onde y é maior que ou igual a x.

$\mathbf{\mathit{Max - Min(x, y)}}$ irá devolver os valores máximo e mínimo de uma matriz $\mathbf{\mathit{numbers[x...y]}}$.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

Análise

Deixei T(n) seja o número de comparações feitas por $\mathbf{\mathit{Max - Min(x, y)}}$, onde o número de elementos $n = y - x + 1$.

E se T(n) representa os números, então a relação de recorrência pode ser representada como

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

Vamos supor que n está na forma de poder de 2. Conseqüentemente,n = 2^k Onde k é a altura da árvore de recursão.

Então,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

Em comparação com o método Naïve, na abordagem dividir para conquistar, o número de comparações é menor. No entanto, usando a notação assintótica, ambas as abordagens são representadas porO(n).

Neste capítulo, discutiremos a classificação por mesclagem e analisaremos sua complexidade.

Declaração do Problema

O problema de ordenar uma lista de números se presta imediatamente a uma estratégia de dividir e conquistar: dividir a lista em duas metades, ordenar recursivamente cada metade e depois mesclar as duas sublistas ordenadas.

Solução

Neste algoritmo, os números são armazenados em uma matriz numbers[]. Aqui,p e q representa o índice inicial e final de uma submatriz.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Análise

Vamos considerar o tempo de execução de Merge-Sort como T(n). Conseqüentemente,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$onde c e d são constantes

Portanto, usando esta relação de recorrência,

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

Como, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

Portanto, $T(n) = O(n\:log\:n)$

Exemplo

No exemplo a seguir, mostramos o algoritmo Merge-Sort passo a passo. Primeiro, cada matriz de iteração é dividida em duas submatrizes, até que a submatriz contenha apenas um elemento. Quando essas submatrizes não podem ser mais divididas, as operações de mesclagem são realizadas.

Neste capítulo, discutiremos outro algoritmo baseado no método de divisão e conquista.

Declaração do Problema

A pesquisa binária pode ser realizada em uma matriz classificada. Nesta abordagem, o índice de um elementoxé determinado se o elemento pertence à lista de elementos. Se a matriz não estiver classificada, a pesquisa linear será usada para determinar a posição.

Solução

Neste algoritmo, queremos descobrir se o elemento x pertence a um conjunto de números armazenados em uma matriz numbers[]. Ondel e r representam o índice esquerdo e direito de uma submatriz na qual a operação de pesquisa deve ser realizada.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Análise

A pesquisa linear é executada em O(n)Tempo. Enquanto a pesquisa binária produz o resultado emO(log n) Tempo

Deixei T(n) ser o número de comparações no pior caso em uma matriz de n elementos

Conseqüentemente,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

Usando esta relação de recorrência $T(n) = log\:n$.

Portanto, a pesquisa binária usa $O(log\:n)$ Tempo.

Exemplo

Neste exemplo, vamos pesquisar o elemento 63.

Neste capítulo, primeiro discutiremos o método geral de multiplicação de matrizes e depois discutiremos o algoritmo de multiplicação de matrizes de Strassen.

Declaração do Problema

Vamos considerar duas matrizes X e Y. Queremos calcular a matriz resultanteZ multiplicando X e Y.

Método Naïve

Primeiro, discutiremos o método ingênuo e sua complexidade. Aqui, estamos calculandoZ = X × Y. Usando o método Naïve, duas matrizes (X e Y) pode ser multiplicado se a ordem dessas matrizes for p × q e q × r. A seguir está o algoritmo.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Complexidade

Aqui, assumimos que as operações inteiras levam O(1)Tempo. Há trêsforloops neste algoritmo e um está aninhado no outro. Portanto, o algoritmo levaO(n³) hora de executar.

Algoritmo de multiplicação de matriz de Strassen

Nesse contexto, usando o algoritmo de multiplicação Matrix de Strassen, o consumo de tempo pode ser um pouco melhorado.

A multiplicação da matriz de Strassen pode ser realizada apenas em square matrices Onde n é um power of 2. A ordem de ambas as matrizes sãon × n.

Dividir X, Y e Z em quatro matrizes (n / 2) × (n / 2), conforme representado abaixo -

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ e $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

Usando o algoritmo de Strassen, calcule o seguinte -

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

Então,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

Análise

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$onde c e d são constantes

Usando esta relação de recorrência, obtemos $T(n) = O(n^{log7})$

Portanto, a complexidade do algoritmo de multiplicação da matriz de Strassen é $O(n^{log7})$.

Entre todas as abordagens algorítmicas, a abordagem mais simples e direta é o método Greedy. Nesta abordagem, a decisão é tomada com base nas informações atualmente disponíveis, sem se preocupar com o efeito da decisão atual no futuro.

Algoritmos gananciosos constroem uma solução parte por parte, escolhendo a próxima parte de forma que ela forneça um benefício imediato. Essa abordagem nunca reconsidera as escolhas feitas anteriormente. Essa abordagem é usada principalmente para resolver problemas de otimização. O método Greedy é fácil de implementar e bastante eficiente na maioria dos casos. Portanto, podemos dizer que o algoritmo Greedy é um paradigma algorítmico baseado em heurística que segue a escolha ótima local em cada etapa com a esperança de encontrar uma solução ótima global.

Em muitos problemas, ele não produz uma solução ótima, embora forneça uma solução aproximada (quase ótima) em um tempo razoável.

Componentes do Algoritmo Greedy

Algoritmos gananciosos têm os seguintes cinco componentes -

• A candidate set - Uma solução é criada a partir deste conjunto.

• A selection function - Usado para escolher o melhor candidato a ser adicionado à solução.

• A feasibility function - Usado para determinar se um candidato pode ser usado para contribuir para a solução.

• An objective function - Usado para atribuir um valor a uma solução ou solução parcial.

• A solution function - Usado para indicar se uma solução completa foi alcançada.

Areas de aplicação

Abordagem gananciosa é usada para resolver muitos problemas, como

• Encontrar o caminho mais curto entre dois vértices usando o algoritmo de Dijkstra.

• Encontrar a árvore geradora mínima em um gráfico usando o algoritmo de Prim / Kruskal, etc.

Onde a abordagem gananciosa falha

Em muitos problemas, o algoritmo Greedy falha em encontrar uma solução ótima, além disso, pode produzir a pior solução. Problemas como caixeiro viajante e mochila não podem ser resolvidos usando esta abordagem.

O algoritmo Greedy pode ser entendido muito bem com um problema conhecido denominado problema da mochila. Embora o mesmo problema pudesse ser resolvido empregando outras abordagens algorítmicas, a abordagem Greedy resolve o problema da mochila fracionária razoavelmente em um bom tempo. Vamos discutir o problema da mochila em detalhes.

Problema da mochila

Dado um conjunto de itens, cada um com um peso e um valor, determine um subconjunto de itens a serem incluídos em uma coleção de modo que o peso total seja menor ou igual a um determinado limite e o valor total seja o maior possível.

O problema da mochila está no problema de otimização combinatória. Ele aparece como um subproblema em muitos modelos matemáticos mais complexos de problemas do mundo real. Uma abordagem geral para problemas difíceis é identificar a restrição mais restritiva, ignorar as outras, resolver um problema de mochila e, de alguma forma, ajustar a solução para satisfazer as restrições ignoradas.

Formulários

Em muitos casos de alocação de recursos junto com alguma restrição, o problema pode ser derivado de uma forma semelhante ao problema da mochila. A seguir está um conjunto de exemplos.

• Encontrando a maneira menos desperdiçadora de cortar matérias-primas
• otimização de portfólio
• Problemas de corte de estoque

Cenário de Problema

Um ladrão está roubando uma loja e pode carregar um peso máximo de Wem sua mochila. Existem n itens disponíveis na loja e peso dei^th item é w_i e seu lucro é p_i. Quais itens o ladrão deve levar?

Neste contexto, os itens devem ser selecionados de forma que o ladrão carregue aqueles itens para os quais obterá lucro máximo. Portanto, o objetivo do ladrão é maximizar o lucro.

Com base na natureza dos itens, os problemas da mochila são categorizados como

• Mochila Fracionada
• Knapsack

Mochila Fracionada

Nesse caso, os itens podem ser quebrados em pedaços menores, portanto, o ladrão pode selecionar frações dos itens.

De acordo com a declaração do problema,

• tem n itens na loja

• Peso de i^th item $w_{i} > 0$

• Lucro para i^th item $p_{i} > 0$ e

• Capacidade da mochila é W

Nesta versão do problema da mochila, os itens podem ser quebrados em pedaços menores. Então, o ladrão pode levar apenas uma fraçãox_i do i^th item.

$$0 \leqslant x_{i} \leqslant 1$$

o i^th o item contribui com o peso $x_{i}.w_{i}$ ao peso total na mochila e lucro $x_{i}.p_{i}$ para o lucro total.

Portanto, o objetivo deste algoritmo é

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

sujeito a restrição,

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

É claro que uma solução ótima deve preencher a mochila exatamente, caso contrário, poderíamos adicionar uma fração de um dos itens restantes e aumentar o lucro geral.

Assim, uma solução ótima pode ser obtida por

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

Neste contexto, primeiro precisamos classificar esses itens de acordo com o valor de $\frac{p_{i}}{w_{i}}$, de modo a $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. Aqui,x é uma matriz para armazenar a fração de itens.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Análise

Se os itens fornecidos já estiverem classificados em uma ordem decrescente de $\mathbf{\frac{p_{i}}{w_{i}}}$, então o loop; todo leva um tempo em O(n); Portanto, o tempo total incluindo a classificação está emO(n logn).

Exemplo

Vamos considerar que a capacidade da mochila W = 60 e a lista de itens fornecidos são mostrados na tabela a seguir -

Item	UMA	B	C	D
Lucro	280	100	120	120
Peso	40	10	20	24
Razão $(\frac{p_{i}}{w_{i}})$	7	10	6	5

Como os itens fornecidos não são classificados com base em $\mathbf{\frac{p_{i}}{w_{i}}}$. Após a classificação, os itens são mostrados na tabela a seguir.

Item	B	UMA	C	D
Lucro	100	280	120	120
Peso	10	40	20	24
Razão $(\frac{p_{i}}{w_{i}})$	10	7	6	5

Solução

Depois de classificar todos os itens de acordo com $\frac{p_{i}}{w_{i}}$. Primeiro tudo deB é escolhido como peso de Bé menor do que a capacidade da mochila. Próximo itemA é escolhido, pois a capacidade disponível da mochila é maior que o peso do A. Agora,Cé escolhido como o próximo item. No entanto, o item inteiro não pode ser escolhido porque a capacidade restante da mochila é menor que o peso deC.

Portanto, fração de C (ou seja, (60 - 50) / 20) é escolhido.

Agora, a capacidade da mochila é igual aos itens selecionados. Portanto, nenhum outro item pode ser selecionado.

O peso total dos itens selecionados é 10 + 40 + 20 * (10/20) = 60

E o lucro total é 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Esta é a solução ideal. Não podemos obter mais lucro selecionando qualquer combinação diferente de itens.

Declaração do Problema

No problema de sequenciamento de tarefas, o objetivo é encontrar uma sequência de tarefas, que seja concluída dentro do prazo e que dê o máximo de lucro.

Solução

Vamos considerar um conjunto de ndeterminados trabalhos que estão associados a prazos e lucro é obtido, se um trabalho for concluído dentro do seu prazo. Esses trabalhos precisam ser ordenados de forma que haja lucro máximo.

Pode acontecer que todos os trabalhos fornecidos não sejam concluídos dentro dos seus prazos.

Suponha, prazo de i^th trabalho J_i é d_i e o lucro recebido por este trabalho é p_i. Portanto, a solução ótima desse algoritmo é uma solução viável com lucro máximo.

Portanto, $D(i) > 0$ para $1 \leqslant i \leqslant n$.

Inicialmente, esses trabalhos são ordenados de acordo com o lucro, ou seja, $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Análise

Neste algoritmo, estamos usando dois loops, um dentro do outro. Portanto, a complexidade deste algoritmo é$O(n^2)$.

Exemplo

Vamos considerar um conjunto de trabalhos fornecidos, conforme mostrado na tabela a seguir. Temos que encontrar uma sequência de trabalhos, que serão concluídos dentro do prazo e darão o máximo de lucro. Cada trabalho está associado a um prazo e lucro.

Trabalho	J1	J2	J3	J4	J5
Data limite	2	1	3	2	1
Lucro	60	100	20	40	20

Solução

Para resolver esse problema, os empregos fornecidos são classificados de acordo com seu lucro em ordem decrescente. Portanto, após a classificação, os trabalhos são ordenados conforme mostrado na tabela a seguir.

Trabalho	J2	J1	J4	J3	J5
Data limite	1	2	2	3	1
Lucro	100	60	40	20	20

Deste conjunto de trabalhos, primeiro selecionamos J₂, pois pode ser concluído dentro do seu prazo e contribui com o lucro máximo.

• Próximo, J₁ é selecionado porque dá mais lucro em comparação com J₄.

• No próximo relógio, J₄ não pode ser selecionado porque seu prazo acabou, portanto J₃ é selecionado à medida que é executado dentro de seu prazo.

• O emprego J₅ é descartado porque não pode ser executado dentro do prazo.

Assim, a solução é a sequência de jobs (J₂, J₁, J₃), que estão sendo executados dentro do prazo e dão lucro máximo.

O lucro total desta sequência é 100 + 60 + 20 = 180.

Mescle um conjunto de arquivos classificados de comprimentos diferentes em um único arquivo classificado. Precisamos encontrar uma solução ótima, onde o arquivo resultante será gerado em tempo mínimo.

Se o número de arquivos classificados for fornecido, há muitas maneiras de mesclá-los em um único arquivo classificado. Esta fusão pode ser realizada em pares. Portanto, este tipo de fusão é chamado de2-way merge patterns.

Como diferentes emparelhamentos requerem diferentes períodos de tempo, nesta estratégia queremos determinar uma maneira ideal de mesclar muitos arquivos. Em cada etapa, duas sequências mais curtas são mescladas.

Para fundir um p-record file e um q-record file requer possivelmente p + q gravar movimentos, sendo a escolha óbvia, mesclar os dois arquivos menores em cada etapa.

Os padrões de mesclagem bidirecional podem ser representados por árvores de mesclagem binárias. Vamos considerar um conjunto den arquivos classificados {f₁, f₂, f₃, …, f_n}. Inicialmente, cada elemento disso é considerado uma árvore binária de nó único. Para encontrar essa solução ideal, o seguinte algoritmo é usado.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

No final deste algoritmo, o peso do nó raiz representa o custo ótimo.

Exemplo

Vamos considerar os arquivos fornecidos, f ₁ , f ₂ , f ₃ , f ₄ ef ₅ com 20, 30, 10, 5 e 30 números de elementos respectivamente.

Se as operações de mesclagem forem realizadas de acordo com a sequência fornecida, então

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Portanto, o número total de operações é

50 + 60 + 65 + 95 = 270

Agora, surge a pergunta: existe alguma solução melhor?

Classificando os números de acordo com seu tamanho em ordem crescente, obtemos a seguinte sequência -

f₄, f₃, f₁, f₂, f₅

Portanto, as operações de mesclagem podem ser realizadas nesta sequência

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Portanto, o número total de operações é

15 + 35 + 65 + 95 = 210

Obviamente, isso é melhor do que o anterior.

Neste contexto, vamos agora resolver o problema usando este algoritmo.

Conjunto Inicial

Passo 1

Passo 2

Etapa 3

Passo 4

Portanto, a solução leva 15 + 35 + 60 + 95 = 205 número de comparações.

A programação dinâmica também é usada em problemas de otimização. Como o método de dividir para conquistar, a Programação Dinâmica resolve problemas combinando as soluções de subproblemas. Além disso, o algoritmo de Programação Dinâmica resolve cada subproblema apenas uma vez e depois salva sua resposta em uma tabela, evitando assim o trabalho de recalcular a resposta todas as vezes.

Duas propriedades principais de um problema sugerem que o problema determinado pode ser resolvido usando a Programação Dinâmica. Essas propriedades sãooverlapping sub-problems and optimal substructure.

Subproblemas sobrepostos

Semelhante à abordagem Dividir e Conquistar, a Programação Dinâmica também combina soluções para subproblemas. É usado principalmente onde a solução de um subproblema é necessária repetidamente. As soluções computadas são armazenadas em uma tabela, para que não tenham que ser recalculadas. Conseqüentemente, essa técnica é necessária quando existe subproblema sobreposto.

Por exemplo, a pesquisa binária não tem subproblemas de sobreposição. Considerando que o programa recursivo de números de Fibonacci tem muitos subproblemas sobrepostos.

Subestrutura Ótima

Um dado problema tem uma propriedade ótima de subestrutura, se a solução ótima do problema dado puder ser obtida usando soluções ótimas de seus subproblemas.

Por exemplo, o problema do caminho mais curto tem a seguinte propriedade de subestrutura ideal -

Se um nó x encontra-se no caminho mais curto de um nó de origem u para o nó de destino v, então o caminho mais curto de u para v é a combinação do caminho mais curto de u para x, e o caminho mais curto de x para v.

Os algoritmos padrão de caminho mais curto de todos os pares, como Floyd-Warshall e Bellman-Ford, são exemplos típicos de programação dinâmica.

Etapas da abordagem de programação dinâmica

O algoritmo de programação dinâmica é projetado usando as seguintes quatro etapas -

• Caracterize a estrutura de uma solução ótima.
• Defina recursivamente o valor de uma solução ótima.
• Calcule o valor de uma solução ideal, geralmente de baixo para cima.
• Construa uma solução ótima a partir das informações computadas.

Aplicações da abordagem de programação dinâmica

• Multiplicação em cadeia de matriz
• Subsequência Comum Mais Longa
• Problema do caixeiro viajante

Neste tutorial, discutimos anteriormente o problema da mochila fracionária usando a abordagem Greedy. Mostramos que a abordagem Greedy oferece uma solução ótima para a mochila fracionária. No entanto, este capítulo cobrirá 0-1 problema da mochila e sua análise.

Na mochila 0-1, os itens não podem ser quebrados, o que significa que o ladrão deve pegar o item inteiro ou deixá-lo. Esta é a razão por trás de chamá-lo como 0-1 Knapsack.

Portanto, no caso de 0-1 mochila, o valor de x_i pode ser qualquer um 0 ou 1, onde outras restrições permanecem as mesmas.

0-1 A mochila não pode ser resolvida pela abordagem gananciosa. A abordagem gananciosa não garante uma solução ideal. Em muitos casos, a abordagem Greedy pode fornecer uma solução ótima.

Os exemplos a seguir estabelecerão nossa declaração.

Exemplo 1

Vamos considerar que a capacidade da mochila é W = 25 e os itens são os mostrados na tabela a seguir.

Item	UMA	B	C	D
Lucro	24	18	18	10
Peso	24	10	10	7

Sem considerar o lucro por unidade de peso (p_i/w_i), se aplicarmos a abordagem Greedy para resolver este problema, primeiro item Aserá selecionado como contribuirá max _i lucro mãe entre todos os elementos.

Depois de selecionar o item A, nenhum outro item será selecionado. Portanto, para este determinado conjunto de itens, o lucro total é24. Considerando que a solução ideal pode ser alcançada selecionando itens,B e C, onde o lucro total é 18 + 18 = 36.

Exemplo-2

Em vez de selecionar os itens com base no benefício geral, neste exemplo, os itens são selecionados com base na proporção p _i / w _i . Vamos considerar que a capacidade da mochila é W = 60 e os itens são os mostrados na tabela a seguir.

Item	UMA	B	C
Preço	100	280	120
Peso	10	40	20
Razão	10	7	6

Usando a abordagem Greedy, primeiro item Aé selecionado. Então, o próximo itemBé escolhido. Portanto, o lucro total é100 + 280 = 380. No entanto, a solução ideal desta instância pode ser alcançada selecionando itens,B e C, onde o lucro total é 280 + 120 = 400.

Portanto, pode-se concluir que a abordagem Greedy pode não fornecer uma solução ótima.

Para resolver 0-1 Knapsack, abordagem de Programação Dinâmica é necessária.

Declaração do Problema

Um ladrão está roubando uma loja e pode transportar um máximo _i peso mal deWem sua mochila. temn itens e peso de i^th item é w_i e o lucro de selecionar este item é p_i. Quais itens o ladrão deve levar?

Abordagem de programação dinâmica

Deixei i ser o item de maior número em uma solução ideal S para Wdólares. EntãoS^' = S - {i} é uma solução ótima para W - w_i dólares e o valor da solução S é V_i mais o valor do subproblema.

Podemos expressar esse fato na seguinte fórmula: definir c[i, w] ser a solução para itens 1,2, … , ie o máximo _i peso mamãw.

O algoritmo usa as seguintes entradas

• O max _i peso mamãW

• O número de itens n

• As duas sequências v = <v₁, v₂, …, v_n> e w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

O conjunto de itens a serem levados pode ser deduzido da tabela, começando em c[n, w] e rastreando para trás de onde os valores ideais vieram.

Se c [i, w] = c [i-1, w] , então o itemi não faz parte da solução, e continuamos rastreando com c[i-1, w]. Caso contrário, itemi faz parte da solução, e continuamos rastreando com c[i-1, w-W].

Análise

Este algoritmo leva θ ( n , w ) vezes, pois a tabela c tem ( n + 1). ( W + 1) entradas, onde cada entrada requer θ (1) tempo para ser computada.

O maior problema comum de subsequência é encontrar a maior sequência que existe em ambas as strings fornecidas.

Subsequência

Vamos considerar uma sequência S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >.

Uma sequência Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > sobre S é chamada de subsequência de S, se e somente se ela pode ser derivada de S deleção de alguns elementos.

Subseqüência Comum

Suponha, X e Ysão duas sequências sobre um conjunto finito de elementos. Nós podemos dizer queZ é uma subsequência comum de X e Y, E se Z é uma subsequência de ambos X e Y.

Subsequência Comum Mais Longa

Se um conjunto de sequências é fornecido, o problema de subsequência comum mais longo é encontrar uma subsequência comum de todas as sequências de comprimento máximo.

O problema de subsequência comum mais longo é um problema clássico de ciência da computação, a base de programas de comparação de dados, como o utilitário diff, e tem aplicações em bioinformática. Também é amplamente usado por sistemas de controle de revisão, como SVN e Git, para reconciliar várias alterações feitas em uma coleção de arquivos controlada por revisão.

Método Naïve

Deixei X ser uma sequência de comprimento m e Y uma sequência de comprimento n. Verifique cada subsequência deX se é uma subsequência de Y, e retornar a maior subsequência comum encontrada.

tem 2^m subsequências de X. Testar sequências, seja ou não uma subsequência deY leva O(n)Tempo. Assim, o algoritmo ingênuo levariaO(n2^m) Tempo.

Programaçao dinamica

Sejam X = <x ₁ , x ₂ , x ₃ ,…, x _m > e Y = <y ₁ , y ₂ , y ₃ ,…, y _n > as sequências. Para calcular o comprimento de um elemento, o seguinte algoritmo é usado.

Neste procedimento, a tabela C[m, n] é calculado na ordem principal da linha e outra tabela B[m,n] é calculado para construir a solução ideal.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Este algoritmo irá imprimir a maior subsequência comum de X e Y.

Análise

Para preencher a tabela, o for loop itera m tempos e o interior for loop itera nvezes. Portanto, a complexidade do algoritmo é O (m, n) , ondem e n têm o comprimento de duas cordas.

Exemplo

Neste exemplo, temos duas strings X = BACDB e Y = BDCB para encontrar a maior subsequência comum.

Seguindo o algoritmo LCS-Length-Table-Formulation (como afirmado acima), calculamos a tabela C (mostrada no lado esquerdo) e a tabela B (mostrada no lado direito).

Na tabela B, em vez de 'D', 'L' e 'U', estamos usando a seta diagonal, seta para a esquerda e seta para cima, respectivamente. Após gerar a tabela B, o LCS é determinado pela função LCS-Print. O resultado é BCB.

UMA spanning tree é um subconjunto de um gráfico não direcionado que possui todos os vértices conectados por um número mínimo de arestas.

Se todos os vértices estiverem conectados em um gráfico, então existe pelo menos uma árvore estendida. Em um gráfico, pode haver mais de uma árvore de abrangência.

Propriedades

• Uma árvore geradora não tem nenhum ciclo.
• Qualquer vértice pode ser alcançado a partir de qualquer outro vértice.

Exemplo

No gráfico a seguir, as arestas destacadas formam uma árvore geradora.

Árvore de alcance mínimo

UMA Minimum Spanning Tree (MST)é um subconjunto de arestas de um gráfico não direcionado ponderado conectado que conecta todos os vértices junto com o peso de aresta total mínimo possível. Para derivar um MST, o algoritmo de Prim ou o algoritmo de Kruskal podem ser usados. Portanto, discutiremos o algoritmo de Prim neste capítulo.

Conforme discutimos, um gráfico pode ter mais de uma árvore de abrangência. Se houvern número de vértices, a árvore de abrangência deve ter n - 1número de arestas. Nesse contexto, se cada aresta do gráfico estiver associada a um peso e houver mais de uma árvore geradora, precisamos encontrar a árvore geradora mínima do gráfico.

Além disso, se houver quaisquer arestas ponderadas duplicadas, o gráfico pode ter múltiplas árvores geradoras mínimas.

No gráfico acima, mostramos uma árvore de abrangência, embora não seja a árvore de abrangência mínima. O custo dessa árvore de abrangência é (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Usaremos o algoritmo de Prim para encontrar a árvore geradora mínima.

Algoritmo de Prim

O algoritmo de Prim é uma abordagem gananciosa para encontrar a árvore geradora mínima. Neste algoritmo, para formar um MST, podemos partir de um vértice arbitrário.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

A função Extract-Min retorna o vértice com custo mínimo de aresta. Esta função funciona em min-heap.

Exemplo

Usando o algoritmo de Prim, podemos começar de qualquer vértice, vamos começar do vértice 1.

Vértice 3 está conectado ao vértice 1 com custo mínimo de borda, portanto, borda (1, 2) é adicionado à árvore de abrangência.

Próximo, borda (2, 3) é considerado porque este é o mínimo entre as arestas {(1, 2), (2, 3), (3, 4), (3, 7)}.

Na próxima etapa, obtemos vantagem (3, 4) e (2, 4)com custo mínimo. Beira(3, 4) é selecionado aleatoriamente.

De forma semelhante, bordas (4, 5), (5, 7), (7, 8), (6, 8) e (6, 9)são selecionados. Como todos os vértices são visitados, agora o algoritmo para.

O custo da árvore de abrangência é (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. Não há mais árvore de abrangência neste gráfico com custo menor que 23.

Algoritmo de Dijkstra

O algoritmo de Dijkstra resolve o problema dos caminhos mais curtos de fonte única em um grafo direcionado G = (V, E) , onde todas as arestas são não negativas (ou seja, w (u, v) ≥ 0 para cada aresta (u, v ) Є E ).

No algoritmo a seguir, usaremos uma função Extract-Min(), que extrai o nó com a menor chave.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Análise

A complexidade desse algoritmo é totalmente dependente da implementação da função Extract-Min. Se a função extract min for implementada usando pesquisa linear, a complexidade deste algoritmo éO(V² + E).

Neste algoritmo, se usarmos min-heap em que Extract-Min() função funciona para retornar o nó de Q com a menor chave, a complexidade desse algoritmo pode ser reduzida ainda mais.

Exemplo

Vamos considerar o vértice 1 e 9como vértice inicial e de destino, respectivamente. Inicialmente, todos os vértices exceto o vértice inicial são marcados por ∞ e o vértice inicial é marcado por0.

Vértice	Inicial	Etapa 1 V 1	Etapa 2 V 3	Etapa 3 V 2	Etapa 4 V 4	Etapa 5 V 5	Etapa 6 V 7	Etapa 7 V 8	Etapa 8 V 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Portanto, a distância mínima do vértice 9 do vértice 1 é 20. E o caminho é

1 → 3 → 7 → 8 → 6 → 9

Este caminho é determinado com base nas informações do predecessor.

Algoritmo Bellman Ford

Este algoritmo resolve o problema do caminho mais curto de fonte única de um gráfico direcionado G = (V, E)em que os pesos das bordas podem ser negativos. Além disso, este algoritmo pode ser aplicado para encontrar o caminho mais curto, caso não exista nenhum ciclo de ponderação negativa.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Análise

O primeiro for loop é usado para inicialização, que é executado em O(V)vezes. Nas próximasfor loop é executado |V - 1| passa pelas bordas, o que levaO(E) vezes.

Portanto, o algoritmo Bellman-Ford é executado em O(V, E) Tempo.

Exemplo

O exemplo a seguir mostra como o algoritmo Bellman-Ford funciona passo a passo. Este gráfico tem uma borda negativa, mas não tem nenhum ciclo negativo, portanto, o problema pode ser resolvido usando esta técnica.

No momento da inicialização, todos os vértices exceto a fonte são marcados por by e a fonte é marcada por 0.

Na primeira etapa, todos os vértices acessíveis da fonte são atualizados por custo mínimo. Portanto, vérticesa e h são atualizados.

Na próxima etapa, vértices a, b, f e e são atualizados.

Seguindo a mesma lógica, nesta etapa os vértices b, f, c e g são atualizados.

Aqui, vértices c e d são atualizados.

Portanto, a distância mínima entre o vértice s e vértice d é 20.

Com base nas informações do predecessor, o caminho é s → h → e → g → c → d

Um gráfico de vários estágios G = (V, E) é um gráfico direcionado onde os vértices são particionados em k (Onde k > 1) número de subconjuntos disjuntos S = {s₁,s₂,…,s_k}tal que o bordo (u, v) é em E, em seguida, u Є s _i e v Є s _{1 + 1} para alguns subconjuntos na partição e |s₁| = |s_k| = 1.

O vértice s Є s₁ é chamado de source e o vértice t Є s_k é chamado sink.

Ggeralmente é considerado um gráfico ponderado. Neste gráfico, o custo de uma aresta (i, j) é representado por c (i, j) . Portanto, o custo do caminho da origems afundar t é a soma dos custos de cada aresta neste caminho.

O problema do gráfico de múltiplos estágios é encontrar o caminho com custo mínimo da origem s afundar t.

Exemplo

Considere o exemplo a seguir para entender o conceito de gráfico de vários estágios.

De acordo com a fórmula, temos que calcular o custo (i, j) usando as seguintes etapas

Etapa 1: Custo (K-2, j)

Nesta etapa, três nós (nó 4, 5. 6) são selecionados como j. Portanto, temos três opções para escolher o custo mínimo nesta etapa.

Custo (3, 4) = min {c (4, 7) + Custo (7, 9), c (4, 8) + Custo (8, 9)} = 7

Custo (3, 5) = min {c (5, 7) + Custo (7, 9), c (5, 8) + Custo (8, 9)} = 5

Custo (3, 6) = min {c (6, 7) + Custo (7, 9), c (6, 8) + Custo (8, 9)} = 5

Etapa 2: Custo (K-3, j)

Dois nós são selecionados como j porque no estágio k - 3 = 2 há dois nós, 2 e 3. Portanto, o valor i = 2 ej = 2 e 3.

Custo (2, 2) = min {c (2, 4) + Custo (4, 8) + Custo (8, 9), c (2, 6) +

Custo (6, 8) + Custo (8, 9)} = 8

Custo (2, 3) = {c (3, 4) + Custo (4, 8) + Custo (8, 9), c (3, 5) + Custo (5, 8) + Custo (8, 9), c (3, 6) + Custo (6, 8) + Custo (8, 9)} = 10

Etapa 3: Custo (K-4, j)

Custo (1, 1) = {c (1, 2) + Custo (2, 6) + Custo (6, 8) + Custo (8, 9), c (1, 3) + Custo (3, 5) + Custo (5, 8) + Custo (8, 9))} = 12

c (1, 3) + Custo (3, 6) + Custo (6, 8 + Custo (8, 9))} = 13

Portanto, o caminho com o custo mínimo é 1→ 3→ 5→ 8→ 9.

Declaração do Problema

Um viajante precisa visitar todas as cidades de uma lista, onde as distâncias entre todas as cidades são conhecidas e cada cidade deve ser visitada apenas uma vez. Qual é o caminho mais curto possível para que ele visite cada cidade exatamente uma vez e retorne à cidade de origem?

Solução

O problema do caixeiro viajante é o problema computacional mais notório. Podemos usar a abordagem de força bruta para avaliar todas as viagens possíveis e selecionar a melhor. Paran número de vértices em um gráfico, há (n - 1)! número de possibilidades.

Em vez de força bruta usando abordagem de programação dinâmica, a solução pode ser obtida em menor tempo, embora não haja algoritmo de tempo polinomial.

Vamos considerar um gráfico G = (V, E), Onde V é um conjunto de cidades e Eé um conjunto de arestas ponderadas. Uma vantageme(u, v) representa os vértices u e vestão conectados. Distância entre vérticesu e v é d(u, v), que deve ser não negativo.

Suponha que tenhamos começado na cidade 1 e depois de visitar algumas cidades agora estamos na cidade j. Portanto, este é um passeio parcial. Certamente precisamos saberj, pois isso determinará quais cidades são mais convenientes para visitar a seguir. Também precisamos saber todas as cidades visitadas até agora, para que não repitamos nenhuma delas. Portanto, este é um subproblema apropriado.

Para um subconjunto de cidades S Є {1, 2, 3, ... , n} que inclui 1, e j Є S, deixei C(S, j) ser o comprimento do caminho mais curto visitando cada nó em S exatamente uma vez, começando em 1 e terminando em j.

Quando |S| > 1, nós definimosC(S, 1) = ∝ visto que o caminho não pode começar e terminar em 1.

Agora vamos expressar C(S, j)em termos de subproblemas menores. Precisamos começar em1 e termina em j. Devemos selecionar a próxima cidade de forma que

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Análise

Há no máximo $2^n.n$subproblemas e cada um leva um tempo linear para resolver. Portanto, o tempo total de execução é$O(2^n.n^2)$.

Exemplo

No exemplo a seguir, ilustraremos as etapas para resolver o problema do caixeiro viajante.

A partir do gráfico acima, a seguinte tabela é preparada.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

S = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

S = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

S = 3

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

O caminho de custo mínimo é 35.

Comece pelo custo {1, {2, 3, 4}, 1}, obtemos o valor mínimo para d [1, 2]. Quandos = 3, selecione o caminho de 1 a 2 (o custo é 10) e volte para trás. Quandos = 2, obtemos o valor mínimo para d [4, 2]. Selecione o caminho de 2 a 4 (o custo é 10) e volte para trás.

Quando s = 1, obtemos o valor mínimo para d [4, 3]. Selecionando o caminho 4 a 3 (o custo é 9), então iremos para, então iremos paras = Φdegrau. Conseguimos o valor mínimo parad [3, 1] (o custo é 6).

Uma árvore de pesquisa binária (BST) é uma árvore onde os valores-chave são armazenados nos nós internos. Os nós externos são nós nulos. As chaves são ordenadas lexicograficamente, ou seja, para cada nó interno, todas as chaves na subárvore esquerda são menores do que as chaves no nó e todas as chaves na subárvore direita são maiores.

Quando sabemos a frequência de busca de cada uma das chaves, é muito fácil calcular o custo esperado de acesso a cada nó da árvore. Uma árvore de pesquisa binária ideal é um BST, que tem um custo mínimo esperado de localização de cada nó

O tempo de busca de um elemento em um BST é O(n), enquanto em um tempo de pesquisa Balanced-BST é O(log n). Novamente, o tempo de pesquisa pode ser melhorado na árvore de pesquisa binária de custo ideal, colocando os dados usados ​​com mais frequência na raiz e mais perto do elemento raiz, enquanto coloca os dados usados ​​com menos frequência perto das folhas e nas folhas.

Aqui, o algoritmo de árvore de busca binária ideal é apresentado. Primeiro, construímos um BST a partir de um conjunto den número de chaves distintas < k₁, k₂, k₃, ... k_n >. Aqui assumimos, a probabilidade de acessar uma chaveK_i é p_i. Algumas chaves fictícias (d₀, d₁, d₂, ... d_n) são adicionados, pois algumas pesquisas podem ser realizadas para os valores que não estão presentes no conjunto de chaves K. Assumimos, para cada chave fictíciad_i probabilidade de acesso é q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Análise

O algoritmo requer O (n³) tempo, desde três aninhados forloops são usados. Cada um desses loops leva no máximon valores.

Exemplo

Considerando a árvore a seguir, o custo é de 2,80, embora esse não seja um resultado ideal.

Nó	Profundidade	Probabilidade	Contribuição
k 1	1	0,15	0,30
k 2	0	0,10	0,10
k 3	2	0,05	0,15
k 4	1	0,10	0,20
k 5	2	0,20	0,60
d 0	2	0,05	0,15
d 1	2	0,10	0,30
d 2	3	0,05	0,20
d 3	3	0,05	0,20
d 4	3	0,05	0,20
d 5	3	0,10	0,40
Total			2,80

Para obter uma solução ideal, usando o algoritmo discutido neste capítulo, as seguintes tabelas são geradas.

Nas tabelas a seguir, o índice da coluna é i e o índice de linha é j.

e	1	2	3	4	5	6
5	2,75	2,00	1,30	0,90	0,50	0,10
4	1,75	1,20	0,60	0,30	0,05
3	1,25	0,70	0,25	0,05
2	0,90	0,40	0,05
1	0,45	0,10
0	0,05

W	1	2	3	4	5	6
5	1,00	0,80	0,60	0,50	0,35	0,10
4	0,70	0,50	0,30	0,20	0,05
3	0,55	0,35	0,15	0,05
2	0,45	0,25	0,05
1	0,30	0,10
0	0,05

raiz	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

A partir dessas tabelas, a árvore ideal pode ser formada.

Existem vários tipos de heap, entretanto, neste capítulo, discutiremos o heap binário. UMAbinary heapé uma estrutura de dados, que se parece com uma árvore binária completa. A estrutura de dados heap obedece às propriedades de ordenação discutidas abaixo. Geralmente, um Heap é representado por uma matriz. Neste capítulo, estamos representando um heap porH.

Como os elementos de um heap são armazenados em uma matriz, considerando o índice inicial como 1, a posição do nó pai de i^th elemento pode ser encontrado em ⌊ i/2 ⌋. Filho esquerdo e filho direito dei^th o nó está na posição 2i e 2i + 1.

Um heap binário pode ser classificado ainda como um max-heap ou um min-heap com base na propriedade do pedido.

Max-Heap

Neste heap, o valor da chave de um nó é maior ou igual ao valor da chave do filho mais velho.

Conseqüentemente, H[Parent(i)] ≥ H[i]

Min-Heap

No heap médio, o valor-chave de um nó é menor ou igual ao valor-chave do filho mais baixo.

Conseqüentemente, H[Parent(i)] ≤ H[i]

Nesse contexto, as operações básicas são mostradas a seguir em relação ao Max-Heap. A inserção e exclusão de elementos em e de pilhas precisam ser reorganizados. Conseqüentemente,Heapify função precisa ser chamada.

Representação de Matriz

Uma árvore binária completa pode ser representada por um array, armazenando seus elementos usando travessia de ordem de nível.

Vamos considerar um heap (como mostrado abaixo) que será representado por um array H.

Considerando o índice inicial como 0, usando a passagem de ordem de nível, os elementos são mantidos em uma matriz da seguinte maneira.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

Nesse contexto, as operações no heap estão sendo representadas em relação ao Max-Heap.

Para encontrar o índice do pai de um elemento no índice i, o seguinte algoritmo Parent (numbers[], i) é usado.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

O índice do filho esquerdo de um elemento no índice i pode ser encontrado usando o seguinte algoritmo, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

O índice do filho certo de um elemento no índice i pode ser encontrado usando o seguinte algoritmo, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

Para inserir um elemento em um heap, o novo elemento é inicialmente anexado ao final do heap como o último elemento da matriz.

Depois de inserir este elemento, a propriedade heap pode ser violada, portanto, a propriedade heap é reparada comparando o elemento adicionado com seu pai e movendo o elemento adicionado um nível acima, trocando posições com o pai. Este processo é chamadopercolation up.

A comparação é repetida até que o pai seja maior ou igual ao elemento percolador.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Análise

Inicialmente, um elemento está sendo adicionado ao final da matriz. Se ele violar a propriedade heap, o elemento será trocado por seu pai. A altura da árvore élog n. Máximolog n número de operações precisa ser executado.

Portanto, a complexidade desta função é O(log n).

Exemplo

Vamos considerar um heap máximo, conforme mostrado abaixo, onde um novo elemento 5 precisa ser adicionado.

Inicialmente, 55 serão adicionados ao final desta matriz.

Após a inserção, ele viola a propriedade heap. Portanto, o elemento precisa ser trocado por seu pai. Após a troca, o heap se parece com o seguinte.

Novamente, o elemento viola a propriedade de heap. Portanto, ele é trocado por seu pai.

Agora, temos que parar.

O método Heapify reorganiza os elementos de uma matriz onde a subárvore esquerda e direita do i^th elemento obedece à propriedade heap.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

Quando a matriz fornecida não obedece à propriedade heap, o Heap é construído com base no seguinte algoritmo Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

O método de extração é usado para extrair o elemento raiz de um Heap. A seguir está o algoritmo.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Exemplo

Vamos considerar o mesmo exemplo discutido anteriormente. Agora queremos extrair um elemento. Este método retornará o elemento raiz do heap.

Após a exclusão do elemento raiz, o último elemento será movido para a posição raiz.

Agora, a função Heapify será chamada. Após Heapify, o seguinte heap é gerado.

Bubble Sort é um algoritmo de classificação elementar, que funciona trocando repetidamente os elementos adjacentes, se necessário. Quando nenhuma troca é necessária, o arquivo é classificado.

Esta é a técnica mais simples entre todos os algoritmos de classificação.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementação

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Análise

Aqui, o número de comparações são

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Claramente, o gráfico mostra o n² natureza do tipo de bolha.

Neste algoritmo, o número de comparação independe do conjunto de dados, ou seja, se os elementos de entrada fornecidos estão em ordem de classificação ou em ordem reversa ou aleatoriamente.

Requisito de Memória

A partir do algoritmo declarado acima, fica claro que a classificação por bolha não requer memória extra.

Exemplo

Unsorted list:

5 2 1 4 3 7 6

1 ^r iteração:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2 ^nd iteração:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

There is no change in 3^rd, 4^th, 5^th and 6^th iteration.

Finally,

the sorted list is

1 2 3 4 5 6 7

Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.

The numbers, which are needed to be sorted, are known as keys. Here is the algorithm of the insertion sort method.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analysis

Run time of this algorithm is very much dependent on the given input.

If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n²) time.

Example

Unsorted list:

2 13 5 18 14

1^st iteration:

Key = a[2] = 13

a[1] = 2 < 13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Key = a[3] = 5

a[2] = 13 > 5

Swap 5 and 13

2 5 13 18 14

Next, a[1] = 2 < 13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Key = a[4] = 18

a[3] = 13 < 18,

a[2] = 5 < 18,

a[1] = 2 < 18

Swap, no swap

2 5 13 18 14

4^th iteration:

Key = a[5] = 14

a[4] = 18 > 14

Swap 18 and 14

2 5 13 14 18

Next, a[3] = 13 < 14,

a[2] = 5 < 14,

a[1] = 2 < 14

So, no swap

2 5 13 14 18

Finally,

the sorted list is

2 5 13 14 18

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if A[j] < min x is executed exactly the same number of times in every case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

• Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.

• Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n - 1 exchanges and

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparisons.

These observations hold, no matter what the input data is.

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.

Implementation

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Example

Unsorted list:

5 2 1 4 3

1^st iteration:

Smallest = 5

2 < 5, smallest = 2

1 < 2, smallest = 1

4 > 1, smallest = 1

3 > 1, smallest = 1

Swap 5 and 1

1 2 5 4 3

2^nd iteration:

Smallest = 2

2 < 5, smallest = 2

2 < 4, smallest = 2

2 < 3, smallest = 2

No Swap

1 2 5 4 3

3^rd iteration:

Smallest = 5

4 < 5, smallest = 4

3 < 4, smallest = 3

Swap 5 and 3

1 2 3 4 5

4^th iteration:

Smallest = 4

4 < 5, smallest = 4

No Swap

1 2 3 4 5

Finally,

the sorted list is

1 2 3 4 5

It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations as it is not difficult to implement. It is a good general purpose sort and it consumes relatively fewer resources during execution.

Advantages

• It is in-place since it uses only a small auxiliary stack.

• It requires only n (log n) time to sort n items.

• It has an extremely short inner loop.

• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Disadvantages

• It is recursive. Especially, if recursion is not available, the implementation is extremely complicated.

• It requires quadratic (i.e., n2) time in the worst-case.

• It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Quick sort works by partitioning a given array A[p ... r] into two non-empty sub array A[p ... q] and A[q+1 ... r] such that every key in A[p ... q] is less than or equal to every key in A[q+1 ... r].

Then, the two sub-arrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Note that to sort the entire array, the initial call should be Quick-Sort (A, 1, length[A])

As a first step, Quick Sort chooses one of the items in the array to be sorted as pivot. Then, the array is partitioned on either side of the pivot. Elements that are less than or equal to pivot will move towards the left, while the elements that are greater than or equal to pivot will move towards the right.

Partitioning the Array

Partitioning procedure rearranges the sub-arrays in-place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analysis

The worst case complexity of Quick-Sort algorithm is O(n²). However using this technique, in average cases generally we get the output in O(n log n) time.

Radix sort is a small method that many people intuitively use when alphabetizing a large list of names. Specifically, the list of names is first sorted according to the first letter of each name, that is, the names are arranged in 26 classes.

Intuitively, one might want to sort numbers on their most significant digit. However, Radix sort works counter-intuitively by sorting on the least significant digits first. On the first pass, all the numbers are sorted on the least significant digit and combined in an array. Then on the second pass, the entire numbers are sorted again on the second least significant digits and combined in an array and so on.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Análise

Cada chave é vista de uma vez para cada dígito (ou letra, se as teclas forem alfabéticas) da chave mais longa. Portanto, se a chave mais longa tiverm dígitos e há n chaves, radix sort tem ordem O(m.n).

No entanto, se olharmos para esses dois valores, o tamanho das chaves será relativamente pequeno quando comparado ao número de chaves. Por exemplo, se temos chaves de seis dígitos, podemos ter um milhão de registros diferentes.

Aqui, vemos que o tamanho das chaves não é significativo e este algoritmo é de complexidade linear O(n).

Exemplo

O exemplo a seguir mostra como a classificação Radix opera em sete números de 3 dígitos.

Entrada	1 r passagem	2 nd passagem	3 rd passagem
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

No exemplo acima, a primeira coluna é a entrada. As colunas restantes mostram a lista após classificações sucessivas na posição de dígitos cada vez mais significativos. O código para classificação Radix assume que cada elemento em uma matrizA do n elementos tem d dígitos, onde dígito 1 é o dígito de ordem mais baixa e d é o dígito de ordem mais alta.

Para entender a classe P e NP, primeiro devemos conhecer o modelo computacional. Portanto, neste capítulo, discutiremos dois modelos computacionais importantes.

Computação Determinística e a Classe P

Máquina de Turing Determinística

Um desses modelos é a máquina de Turing determinística de uma fita. Essa máquina consiste em um controle de estado finito, um cabeçote de leitura e gravação e uma fita bidirecional com seqüência infinita.

A seguir está o diagrama esquemático de uma máquina de Turing determinística de uma fita.

Um programa para uma máquina de Turing determinística especifica as seguintes informações -

• Um conjunto finito de símbolos de fita (símbolos de entrada e um símbolo em branco)
• Um conjunto finito de estados
• Uma função de transição

Na análise algorítmica, se um problema pode ser resolvido em tempo polinomial por uma máquina de Turing de uma fita determinística, o problema pertence à classe P.

Computação Não Determinística e a Classe NP

Máquina de Turing Não Determinística

Para resolver o problema computacional, outro modelo é a Máquina de Turing Não Determinística (NDTM). A estrutura do NDTM é semelhante ao DTM, porém aqui temos um módulo adicional conhecido como módulo de adivinhação, que está associado a um cabeçote somente de gravação.

A seguir está o diagrama esquemático.

Se o problema pode ser resolvido em tempo polinomial por uma máquina de Turing não determinística, o problema pertence à classe NP.

Em um gráfico não direcionado, um cliqueé um subgráfico completo do gráfico fornecido. Sub-gráfico completo significa que todos os vértices deste sub-gráfico estão conectados a todos os outros vértices deste sub-gráfico.

O problema Max-Clique é o problema computacional de encontrar o clique máximo do grafo. Max clique é usado em muitos problemas do mundo real.

Vamos considerar um aplicativo de rede social, onde os vértices representam o perfil das pessoas e as arestas representam o conhecimento mútuo em um gráfico. Neste gráfico, um clique representa um subconjunto de pessoas que se conhecem.

Para encontrar um clique máximo, pode-se inspecionar sistematicamente todos os subconjuntos, mas esse tipo de busca de força bruta consome muito tempo para redes que compreendem mais do que algumas dezenas de vértices.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Análise

O problema da Max-Clique é um algoritmo não determinístico. Neste algoritmo, primeiro tentamos determinar um conjunto dek vértices distintos e então tentamos testar se esses vértices formam um gráfico completo.

Não existe um algoritmo determinístico de tempo polinomial para resolver este problema. Este problema é NP-Completo.

Exemplo

Dê uma olhada no gráfico a seguir. Aqui, o subgráfico contendo os vértices 2, 3, 4 e 6 forma um gráfico completo. Portanto, este subgráfico é umclique. Como este é o subgráfico máximo completo do gráfico fornecido, é um4-Clique.

Uma cobertura de vértice de um gráfico não direcionado G = (V, E) é um subconjunto de vértices V^' ⊆ V tal que se borda (u, v) é uma borda de G, qualquer então u dentro V ou v dentro V^' ou ambos.

Encontre uma cobertura de vértice de tamanho máximo em um dado gráfico não direcionado. Esta cobertura de vértice ideal é a versão de otimização de um problema NP-completo. No entanto, não é muito difícil encontrar uma cobertura de vértices próxima da ótima.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

Exemplo

O conjunto de arestas do gráfico fornecido é -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Agora, começamos selecionando uma aresta arbitrária (1,6). Eliminamos todas as arestas que incidem no vértice 1 ou 6 e adicionamos a aresta (1,6) para cobrir.

Na próxima etapa, escolhemos outra aresta (2,3) aleatoriamente

Agora selecionamos outra aresta (4,7).

Selecionamos outra aresta (8,5).

Portanto, a cobertura do vértice deste gráfico é {1,2,4,5}.

Análise

É fácil ver que o tempo de execução deste algoritmo é O(V + E), usando lista de adjacência para representar E^'.

Na Ciência da Computação, muitos problemas são resolvidos onde o objetivo é maximizar ou minimizar alguns valores, enquanto em outros problemas tentamos descobrir se há uma solução ou não. Portanto, os problemas podem ser categorizados da seguinte forma -

Problema de Otimização

Problemas de otimização são aqueles cujo objetivo é maximizar ou minimizar alguns valores. Por exemplo,

• Encontrar o número mínimo de cores necessárias para colorir um determinado gráfico.

• Encontrando o caminho mais curto entre dois vértices em um gráfico.

Problema de Decisão

Existem muitos problemas para os quais a resposta é Sim ou Não. Esses tipos de problemas são conhecidos como decision problems. Por exemplo,

• Se um determinado gráfico pode ser colorido por apenas 4 cores.

• Encontrar o ciclo hamiltoniano em um gráfico não é um problema de decisão, enquanto verificar um gráfico é hamiltoniano ou não é um problema de decisão.

O que é linguagem?

Todo problema de decisão pode ter apenas duas respostas, sim ou não. Portanto, um problema de decisão pode pertencer a um idioma se ele fornecer uma resposta 'sim' para uma entrada específica. Um idioma é a totalidade de entradas para as quais a resposta é sim. A maioria dos algoritmos discutidos nos capítulos anteriores sãopolynomial time algorithms.

Para tamanho de entrada n, se o pior caso de complexidade de tempo de um algoritmo for O(n^k), Onde k é uma constante, o algoritmo é um algoritmo de tempo polinomial.

Algoritmos como Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, etc. são executados em tempo polinomial. No entanto, existem muitos problemas, como vendedor ambulante, coloração de gráfico ideal, ciclos hamiltonianos, encontrar o caminho mais longo em um gráfico e satisfazer uma fórmula booleana, para a qual nenhum algoritmo de tempo polinomial é conhecido. Esses problemas pertencem a uma classe interessante de problemas, chamada deNP-Complete problemas, cujo estado é desconhecido.

Neste contexto, podemos categorizar os problemas da seguinte forma -

Classe P

A classe P consiste naqueles problemas que podem ser resolvidos em tempo polinomial, ou seja, esses problemas podem ser resolvidos em tempo O(n^k) na pior das hipóteses, onde k é constante.

Esses problemas são chamados tractable, enquanto outros são chamados intractable or superpolynomial.

Formalmente, um algoritmo é um algoritmo de tempo polinomial, se houver um polinômio p(n) de modo que o algoritmo possa resolver qualquer instância de tamanho n em um tempo O(p(n)).

Problema exigindo Ω(n⁵⁰) tempo para resolver são essencialmente intratáveis ​​para grandes n. Algoritmo de tempo polinomial mais conhecido executado no tempoO(n^k) para um valor bastante baixo de k.

As vantagens em considerar a classe de algoritmos de tempo polinomial é que todos os deterministic single processor model of computation podem ser simulados um no outro com no máximo um polinômio slow-d

NP-Class

A classe NP consiste nos problemas verificáveis ​​em tempo polinomial. NP é a classe de problemas de decisão para os quais é fácil verificar a exatidão de uma resposta reivindicada, com o auxílio de algumas informações extras. Portanto, não estamos pedindo uma maneira de encontrar uma solução, mas apenas para verificar se uma suposta solução é realmente correta.

Cada problema nesta classe pode ser resolvido em tempo exponencial usando pesquisa exaustiva.

P versus NP

Todo problema de decisão que pode ser resolvido por um algoritmo de tempo polinomial determinístico também pode ser resolvido por um algoritmo não determinístico de tempo polinomial.

Todos os problemas em P podem ser resolvidos com algoritmos de tempo polinomial, enquanto todos os problemas em NP - P são intratáveis.

Não se sabe se P = NP. No entanto, muitos problemas são conhecidos em NP com a propriedade de que se eles pertencem a P, então pode-se provar que P = NP.

E se P ≠ NP, há problemas em NP que não estão em P nem em NP-Completo.

O problema pertence a classe Pse for fácil encontrar uma solução para o problema. O problema pertence aNP, se for fácil verificar uma solução que pode ter sido muito tediosa de encontrar.

Stephen Cook apresentou quatro teoremas em seu artigo “The Complexity of Theorem Proving Procedures”. Esses teoremas são declarados abaixo. Nós entendemos que muitos termos desconhecidos estão sendo usados ​​neste capítulo, mas não temos nenhum escopo para discutir tudo em detalhes.

A seguir estão os quatro teoremas de Stephen Cook -

Teorema-1

Se um conjunto S de strings é aceito por alguma máquina de Turing não determinística dentro do tempo polinomial, então S é P-redutível a {tautologias DNF}.

Teorema-2

Os seguintes conjuntos são P-redutíveis uns aos outros em pares (e, portanto, cada um tem o mesmo grau de dificuldade polinomial): {tautologias}, {DNF tautologias}, D3, {pares de subgráficos}.

Teorema-3

• Para qualquer T_Q(k) do tipo Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ é ilimitado

• Existe um T_Q(k) do tipo Q de tal modo que $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

Teorema-4

Se o conjunto S de strings for aceito por uma máquina não determinística dentro do tempo T(n) = 2ⁿ, e se T_Q(k) é uma função honesta (ou seja, contagem em tempo real) do tipo Q, então há uma constante K, então S pode ser reconhecido por uma máquina determinística dentro do tempo T_Q(K8ⁿ).

• Primeiro, ele enfatizou a importância da redutibilidade do tempo polinomial. Isso significa que se tivermos uma redução de tempo polinomial de um problema para outro, isso garante que qualquer algoritmo de tempo polinomial do segundo problema possa ser convertido em um algoritmo de tempo polinomial correspondente para o primeiro problema.

• Em segundo lugar, ele focou a atenção na classe NP de problemas de decisão que podem ser resolvidos em tempo polinomial por um computador não determinístico. A maioria dos problemas intratáveis ​​pertence a esta classe, NP.

• Terceiro, ele provou que um problema particular em NP tem a propriedade de que todos os outros problemas em NP podem ser polinomialmente reduzidos a ele. Se o problema de satisfatibilidade pode ser resolvido com um algoritmo de tempo polinomial, então todo problema em NP também pode ser resolvido em tempo polinomial. Se algum problema em NP for intratável, então o problema de satisfatibilidade deve ser intratável. Assim, o problema de satisfatibilidade é o problema mais difícil em NP.

• Em quarto lugar, Cook sugeriu que outros problemas em NP podem compartilhar com o problema da satisfatibilidade essa propriedade de ser o membro mais difícil de NP.

Um problema está na classe NPC se for NP e for tão hardcomo qualquer problema no NP. Um problema éNP-hard se todos os problemas em NP são redutíveis em tempo polinomial a ele, mesmo que não seja no próprio NP.

Se um algoritmo de tempo polinomial existir para qualquer um desses problemas, todos os problemas em NP seriam solucionáveis ​​em tempo polinomial. Esses problemas são chamadosNP-complete. O fenômeno da NP-completude é importante por razões teóricas e práticas.

Definição de NP-Completude

Uma linguagem B é NP-complete se satisfaz duas condições

• B está em NP

• Cada A em NP é o tempo polinomial redutível a B.

Se um idioma satisfaz a segunda propriedade, mas não necessariamente a primeira, o idioma B é conhecido como NP-Hard. Informalmente, um problema de pesquisaB é NP-Hard se existe algum NP-Complete problema A que Turing reduz a B.

O problema em NP-Hard não pode ser resolvido em tempo polinomial, até P = NP. Se for provado que um problema é NPC, não há necessidade de perder tempo tentando encontrar um algoritmo eficiente para ele. Em vez disso, podemos nos concentrar no algoritmo de aproximação de projeto.

Problemas NP-Completos

A seguir estão alguns problemas NP-Completos, para os quais nenhum algoritmo de tempo polinomial é conhecido.

• Determinar se um gráfico tem um ciclo hamiltoniano
• Determinar se uma fórmula booleana é satisfatória, etc.

Problemas NP-Difícil

Os seguintes problemas são NP-difíceis

• O problema de satisfatibilidade do circuito
• Conjunto de capa
• Capa de vértice
• Problema do caixeiro viajante

Neste contexto, agora iremos discutir o TSP é NP-Completo

TSP é NP-completo

O problema do caixeiro viajante consiste em um vendedor e um conjunto de cidades. O vendedor deve visitar cada uma das cidades partindo de uma determinada e voltando para a mesma. O desafio do problema é que o caixeiro viajante quer minimizar a duração total da viagem

Prova

Provar TSP is NP-Complete, primeiro temos que provar que TSP belongs to NP. No TSP, encontramos um passeio e verificamos se o passeio contém cada vértice uma vez. Em seguida, o custo total das bordas do passeio é calculado. Por fim, verificamos se o custo é mínimo. Isso pode ser concluído em tempo polinomial. portantoTSP belongs to NP.

Em segundo lugar, temos que provar que TSP is NP-hard. Para provar isso, uma maneira é mostrar queHamiltonian cycle ≤_p TSP (como sabemos que o problema do ciclo hamiltoniano é NPcompleto).

Presumir G = (V, E) para ser uma instância do ciclo hamiltoniano.

Portanto, uma instância do TSP é construída. Nós criamos o gráfico completoG^' = (V, E^'), Onde

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

Assim, a função de custo é definida da seguinte forma -

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

Agora, suponha que um ciclo hamiltoniano h existe em G. É claro que o custo de cada borda emh é 0 dentro G^' como cada borda pertence a E. Portanto,h tem um custo de 0 dentro G^'. Assim, se o gráficoG tem um ciclo hamiltoniano, então o gráfico G^' tem um tour de 0 custo.

Por outro lado, assumimos que G^' tem um tour h^' de custo no máximo 0. O custo das arestas emE^' está 0 e 1por definição. Portanto, cada aresta deve ter um custo de0 como o custo de h^' é 0. Portanto, concluímos queh^' contém apenas bordas em E.

Assim, provamos que G tem um ciclo hamiltoniano, se e somente se G^' tem um tour de custo no máximo 0. TSP é NP-completo.

Os algoritmos discutidos nos capítulos anteriores são executados sistematicamente. Para atingir a meta, um ou mais caminhos previamente explorados em direção à solução precisam ser armazenados para encontrar a solução ideal.

Para muitos problemas, o caminho para a meta é irrelevante. Por exemplo, no problema de N-Rainhas, não precisamos nos preocupar com a configuração final das rainhas, bem como em que ordem as rainhas são adicionadas.

Hill Climbing

Hill Climbing é uma técnica para resolver certos problemas de otimização. Nesta técnica, começamos com uma solução subótima e a solução é melhorada repetidamente até que alguma condição seja maximizada.

A ideia de começar com uma solução abaixo do ideal é comparada a começar da base da colina, melhorar a solução é comparada a subir a colina e, finalmente, maximizar alguma condição é comparada a alcançar o topo da colina.

Assim, a técnica de hill climbing pode ser considerada nas seguintes fases -

• Construir uma solução abaixo do ideal obedecendo às restrições do problema
• Melhorando a solução passo a passo
• Melhorar a solução até que nenhuma melhoria seja possível

A técnica de Hill Climbing é usada principalmente para resolver problemas computacionalmente difíceis. Ele olha apenas para o estado atual e o estado futuro imediato. Portanto, essa técnica é eficiente em termos de memória, pois não mantém uma árvore de pesquisa.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Melhoria Iterativa

No método de melhoria iterativa, a solução ótima é alcançada progredindo em direção a uma solução ótima em cada iteração. No entanto, esta técnica pode encontrar máximos locais. Nesta situação, não há estado próximo para uma solução melhor.

Este problema pode ser evitado por diferentes métodos. Um desses métodos é o recozimento simulado.

Reinício Aleatório

Este é outro método de resolver o problema de ótimos locais. Essa técnica realiza uma série de pesquisas. Toda vez, ele começa a partir de um estado inicial gerado aleatoriamente. Portanto, a solução ótima ou quase ótima pode ser obtida comparando as soluções das pesquisas realizadas.

Problemas da técnica de escalada

Máxima Local

Se a heurística não for convexa, Hill Climbing pode convergir para máximos locais, em vez de máximos globais.

Cordilheiras e becos

Se a função de destino criar uma crista estreita, o alpinista só poderá subir a crista ou descer o beco em zigue-zague. Nesse cenário, o escalador precisa dar passos muito pequenos, exigindo mais tempo para atingir a meta.

Platô

Um platô é encontrado quando o espaço de busca é plano ou suficientemente plano para que o valor retornado pela função de destino seja indistinguível do valor retornado para regiões próximas, devido à precisão usada pela máquina para representar seu valor.

Complexidade da técnica de escalada

Esta técnica não apresenta problemas relacionados ao espaço, visto que analisa apenas o estado atual. Caminhos explorados anteriormente não são armazenados.

Para a maioria dos problemas na técnica Hill Climbing de reinício aleatório, uma solução ótima pode ser alcançada em tempo polinomial. No entanto, para problemas NP-Completos, o tempo computacional pode ser exponencial com base no número de máximos locais.

Aplicações da técnica de escalada

A técnica de Hill Climbing pode ser usada para resolver muitos problemas, onde o estado atual permite uma função de avaliação precisa, como fluxo de rede, problema do caixeiro viajante, problema de 8 Rainhas, projeto de circuito integrado, etc.

O Hill Climbing também é usado em métodos de aprendizagem indutiva. Esta técnica é usada em robótica para coordenação entre vários robôs em uma equipe. Existem muitos outros problemas quando essa técnica é usada.

Exemplo

Essa técnica pode ser aplicada para resolver o problema do caixeiro viajante. Primeiro é determinada uma solução inicial que visita todas as cidades exatamente uma vez. Portanto, essa solução inicial não é ótima na maioria dos casos. Mesmo esta solução pode ser muito pobre. O algoritmo Hill Climbing começa com essa solução inicial e faz melhorias de maneira iterativa. Eventualmente, uma rota muito mais curta provavelmente será obtida.