DAA - Guida rapida
Un algoritmo è un insieme di passaggi di operazioni per risolvere un problema durante l'esecuzione di attività di calcolo, elaborazione dati e ragionamento automatico. Un algoritmo è un metodo efficiente che può essere espresso in una quantità finita di tempo e spazio.
Un algoritmo è il modo migliore per rappresentare la soluzione di un particolare problema in modo molto semplice ed efficiente. Se abbiamo un algoritmo per un problema specifico, possiamo implementarlo in qualsiasi linguaggio di programmazione, il che significa che il filealgorithm is independent from any programming languages.
Progettazione di algoritmi
Gli aspetti importanti della progettazione di algoritmi includono la creazione di un algoritmo efficiente per risolvere un problema in modo efficiente utilizzando il minimo tempo e spazio.
Per risolvere un problema, è possibile seguire diversi approcci. Alcuni di essi possono essere efficienti rispetto al consumo di tempo, mentre altri approcci possono essere efficienti in termini di memoria. Tuttavia, è necessario tenere presente che sia il consumo di tempo che l'utilizzo della memoria non possono essere ottimizzati contemporaneamente. Se richiediamo che un algoritmo venga eseguito in minor tempo, dobbiamo investire in più memoria e se richiediamo che un algoritmo venga eseguito con meno memoria, dobbiamo avere più tempo.
Fasi di sviluppo del problema
I seguenti passaggi sono coinvolti nella risoluzione dei problemi di calcolo.
- Definizione del problema
- Sviluppo di un modello
- Specifica di un algoritmo
- Progettare un algoritmo
- Verifica della correttezza di un algoritmo
- Analisi di un algoritmo
- Implementazione di un algoritmo
- Test del programma
- Documentation
Caratteristiche degli algoritmi
Le caratteristiche principali degli algoritmi sono le seguenti:
Gli algoritmi devono avere un nome univoco
Gli algoritmi dovrebbero avere una serie di input e output definiti in modo esplicito
Gli algoritmi sono ben ordinati con operazioni non ambigue
Gli algoritmi si arrestano in un periodo di tempo finito. Gli algoritmi non dovrebbero funzionare all'infinito, ovvero un algoritmo deve terminare ad un certo punto
Pseudocodice
Lo pseudocodice fornisce una descrizione di alto livello di un algoritmo senza l'ambiguità associata al testo normale ma anche senza la necessità di conoscere la sintassi di un particolare linguaggio di programmazione.
Il tempo di esecuzione può essere stimato in modo più generale utilizzando Pseudocode per rappresentare l'algoritmo come un insieme di operazioni fondamentali che possono poi essere conteggiate.
Differenza tra algoritmo e pseudocodice
Un algoritmo è una definizione formale con alcune caratteristiche specifiche che descrive un processo, che potrebbe essere eseguito da un computer completo di Turing per eseguire un compito specifico. In generale, la parola "algoritmo" può essere utilizzata per descrivere qualsiasi compito di alto livello in informatica.
D'altra parte, lo pseudocodice è una descrizione informale e (spesso rudimentale) leggibile dall'uomo di un algoritmo che ne lascia molti dettagli granulari. La scrittura di uno pseudocodice non ha limitazioni di stili e il suo unico obiettivo è descrivere i passaggi di alto livello dell'algoritmo in modo molto realistico nel linguaggio naturale.
Ad esempio, di seguito è riportato un algoritmo per l'ordinamento di inserzione.
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
Ecco uno pseudocodice che descrive come il processo astratto di alto livello menzionato sopra nell'algoritmo Insertion-Sort potrebbe essere descritto in un modo più realistico.
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
In questo tutorial, gli algoritmi verranno presentati sotto forma di pseudocodice, che è simile per molti aspetti a C, C ++, Java, Python e altri linguaggi di programmazione.
Nell'analisi teorica degli algoritmi, è comune stimare la loro complessità in senso asintotico, cioè stimare la funzione di complessità per input arbitrariamente grandi. Il termine"analysis of algorithms" è stato coniato da Donald Knuth.
L'analisi degli algoritmi è una parte importante della teoria della complessità computazionale, che fornisce una stima teorica delle risorse richieste da un algoritmo per risolvere uno specifico problema computazionale. La maggior parte degli algoritmi sono progettati per funzionare con input di lunghezza arbitraria. L'analisi degli algoritmi è la determinazione della quantità di risorse di tempo e spazio necessarie per eseguirla.
Di solito, l'efficienza o il tempo di esecuzione di un algoritmo è indicato come una funzione che collega la lunghezza dell'ingresso al numero di passi, nota come time complexityo volume di memoria, noto come space complexity.
Il bisogno di analisi
In questo capitolo, discuteremo la necessità di analisi degli algoritmi e come scegliere un algoritmo migliore per un particolare problema poiché un problema computazionale può essere risolto da algoritmi differenti.
Considerando un algoritmo per un problema specifico, possiamo iniziare a sviluppare il riconoscimento di modelli in modo che tipi di problemi simili possano essere risolti con l'aiuto di questo algoritmo.
Gli algoritmi sono spesso molto diversi l'uno dall'altro, sebbene l'obiettivo di questi algoritmi sia lo stesso. Ad esempio, sappiamo che un insieme di numeri può essere ordinato utilizzando diversi algoritmi. Il numero di confronti eseguiti da un algoritmo può variare con altri per lo stesso input. Quindi, la complessità temporale di questi algoritmi può differire. Allo stesso tempo, dobbiamo calcolare lo spazio di memoria richiesto da ogni algoritmo.
L'analisi dell'algoritmo è il processo di analisi della capacità di risoluzione dei problemi dell'algoritmo in termini di tempo e dimensione richiesti (la dimensione della memoria per l'archiviazione durante l'implementazione). Tuttavia, la preoccupazione principale dell'analisi degli algoritmi è il tempo o le prestazioni richiesti. In generale, eseguiamo i seguenti tipi di analisi:
Worst-case - Il numero massimo di passaggi eseguiti su qualsiasi istanza di dimensione a.
Best-case - Il numero minimo di passaggi eseguiti su qualsiasi istanza di dimensione a.
Average case - Un numero medio di passaggi eseguiti su qualsiasi istanza di dimensione a.
Amortized - Una sequenza di operazioni applicate all'input della dimensione a media nel tempo.
Per risolvere un problema, dobbiamo considerare la complessità dello spazio e del tempo poiché il programma può essere eseguito su un sistema in cui la memoria è limitata ma è disponibile uno spazio adeguato o può essere viceversa. In questo contesto, se confrontiamobubble sort e merge sort. L'ordinamento a bolle non richiede memoria aggiuntiva, ma l'ordinamento di unione richiede spazio aggiuntivo. Sebbene la complessità temporale del Bubble Sort sia maggiore rispetto al Merge Sort, potrebbe essere necessario applicare il Bubble Sort se il programma deve essere eseguito in un ambiente in cui la memoria è molto limitata.
Per misurare il consumo di risorse di un algoritmo, vengono utilizzate diverse strategie come discusso in questo capitolo.
Analisi asintotica
Il comportamento asintotico di una funzione f(n) si riferisce alla crescita di f(n) come n diventa grande.
In genere ignoriamo valori piccoli di n, poiché di solito siamo interessati a stimare la lentezza del programma su input di grandi dimensioni.
Una buona regola pratica è che più lento è il tasso di crescita asintotico, migliore è l'algoritmo. Anche se non è sempre vero.
Ad esempio, un algoritmo lineare $f(n) = d * n + k$ è sempre asintoticamente migliore di uno quadratico, $f(n) = c.n^2 + q$.
Risoluzione di equazioni di ricorrenza
Una ricorrenza è un'equazione o una disuguaglianza che descrive una funzione in termini di valore su input più piccoli. Le ricorrenze sono generalmente utilizzate nel paradigma divide et impera.
Lasciaci considerare T(n) essere il tempo di esecuzione su un problema di dimensioni n.
Se la dimensione del problema è abbastanza piccola, diciamo n < c dove c è una costante, la soluzione semplice richiede tempo costante, che è scritto come θ(1). Se la divisione del problema produce una serie di sottoproblemi con le dimensioni$\frac{n}{b}$.
Per risolvere il problema, il tempo necessario è a.T(n/b). Se consideriamo il tempo necessario per la divisione èD(n) e il tempo necessario per combinare i risultati dei sottoproblemi è C(n), la relazione di ricorrenza può essere rappresentata come -
$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$
Una relazione di ricorrenza può essere risolta utilizzando i seguenti metodi:
Substitution Method - In questo metodo, indoviniamo un limite e usando l'induzione matematica dimostriamo che la nostra ipotesi era corretta.
Recursion Tree Method - In questo metodo, viene formato un albero di ricorrenza in cui ogni nodo rappresenta il costo.
Master’s Theorem - Questa è un'altra tecnica importante per trovare la complessità di una relazione di ricorrenza.
Analisi ammortizzata
L'analisi ammortizzata viene generalmente utilizzata per alcuni algoritmi in cui viene eseguita una sequenza di operazioni simili.
L'analisi ammortizzata fornisce un limite al costo effettivo dell'intera sequenza, invece di limitare separatamente il costo della sequenza di operazioni.
L'analisi ammortizzata differisce dall'analisi del caso medio; la probabilità non è coinvolta nell'analisi ammortizzata. L'analisi ammortizzata garantisce la performance media di ogni operazione nel caso peggiore.
Non è solo uno strumento di analisi, è un modo di pensare alla progettazione, poiché progettazione e analisi sono strettamente correlate.
Metodo aggregato
Il metodo aggregato fornisce una visione globale di un problema. In questo metodo, sen le operazioni richiedono il tempo peggiore T(n)in totale. Quindi il costo ammortizzato di ciascuna operazione èT(n)/n. Sebbene operazioni diverse possano richiedere tempi diversi, in questo metodo il costo variabile viene trascurato.
Metodo contabile
In questo metodo, addebiti diversi vengono assegnati a operazioni diverse in base al loro costo effettivo. Se il costo ammortizzato di un'operazione supera il suo costo effettivo, la differenza viene attribuita all'oggetto come credito. Questo credito aiuta a pagare per operazioni successive per le quali il costo ammortizzato è inferiore al costo effettivo.
Se il costo effettivo e il costo ammortizzato di ith operazione sono $c_{i}$ e $\hat{c_{l}}$, poi
$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$
Metodo potenziale
Questo metodo rappresenta il lavoro prepagato come energia potenziale, invece di considerare il lavoro prepagato come credito. Questa energia può essere rilasciata per pagare le operazioni future.
Se ci esibiamo n operazioni che iniziano con una struttura dati iniziale D0. Lasciaci considerare,ci come il costo effettivo e Di come struttura dati di ithoperazione. La funzione potenziale Ф mappa su un numero reale Ф (Di), il potenziale associato di Di. Il costo ammortizzato$\hat{c_{l}}$ può essere definito da
$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$
Quindi, il costo ammortizzato totale è
$$\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})$$
Tabella dinamica
Se lo spazio allocato per la tabella non è sufficiente, dobbiamo copiare la tabella in una tabella di dimensioni maggiori. Allo stesso modo, se un numero elevato di membri viene cancellato dalla tabella, è una buona idea riallocare la tabella con una dimensione inferiore.
Utilizzando l'analisi ammortizzata, possiamo dimostrare che il costo ammortizzato di inserimento e cancellazione è costante e lo spazio inutilizzato in una tabella dinamica non supera mai una frazione costante dello spazio totale.
Nel prossimo capitolo di questo tutorial, discuteremo brevemente delle notazioni asintotiche.
Nella progettazione di algoritmi, l'analisi della complessità di un algoritmo è un aspetto essenziale. Principalmente, la complessità algoritmica riguarda le sue prestazioni, quanto velocemente o lentamente funzioni.
La complessità di un algoritmo descrive l'efficienza dell'algoritmo in termini di quantità di memoria richiesta per elaborare i dati e tempo di elaborazione.
La complessità di un algoritmo viene analizzata in due prospettive: Time e Space.
Complessità temporale
È una funzione che descrive la quantità di tempo necessaria per eseguire un algoritmo in termini di dimensione dell'input. "Tempo" può significare il numero di accessi alla memoria eseguiti, il numero di confronti tra interi, il numero di volte in cui viene eseguito un ciclo interno o qualche altra unità naturale correlata alla quantità di tempo reale che l'algoritmo impiegherà.
Complessità spaziale
È una funzione che descrive la quantità di memoria che un algoritmo richiede in termini di dimensione dell'input dell'algoritmo. Si parla spesso di memoria "extra" necessaria, senza contare la memoria necessaria per memorizzare l'input stesso. Ancora una volta, usiamo unità naturali (ma di lunghezza fissa) per misurarlo.
La complessità dello spazio a volte viene ignorata perché lo spazio utilizzato è minimo e / o ovvio, tuttavia a volte diventa una questione importante quanto il tempo.
Notazioni asintotiche
Il tempo di esecuzione di un algoritmo dipende dal set di istruzioni, dalla velocità del processore, dalla velocità di I / O del disco, ecc. Pertanto, stimiamo l'efficienza di un algoritmo in modo asintotico.
La funzione temporale di un algoritmo è rappresentata da T(n), dove n è la dimensione dell'input.
Diversi tipi di notazioni asintotiche vengono utilizzati per rappresentare la complessità di un algoritmo. Le seguenti notazioni asintotiche vengono utilizzate per calcolare la complessità del tempo di esecuzione di un algoritmo.
O - Grande Oh
Ω - Big omega
θ - Grande theta
o - Piccolo Oh
ω - Un po 'di omega
O: limite superiore asintotico
'O' (Big Oh) è la notazione più comunemente usata. Una funzionef(n) può essere rappresentato è l'ordine di g(n) questo è O(g(n)), se esiste un valore intero positivo n come n0 e una costante positiva c tale che -
$f(n)\leqslant c.g(n)$ per $n > n_{0}$ in ogni caso
Quindi, funzione g(n) è un limite superiore per la funzione f(n), come g(n) cresce più velocemente di f(n).
Esempio
Consideriamo una data funzione, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$
Considerando $g(n) = n^3$,
$f(n)\leqslant 5.g(n)$ per tutti i valori di $n > 2$
Quindi, la complessità di f(n) può essere rappresentato come $O(g(n))$, ie $O(n^3)$
Ω: limite inferiore asintotico
Lo diciamo noi $f(n) = \Omega (g(n))$ quando esiste una costante c quello $f(n)\geqslant c.g(n)$ per tutti un valore sufficientemente elevato di n. Quinè un numero intero positivo. Significa funzioneg è un limite inferiore per la funzione f; dopo un certo valore din, f non andrà mai sotto g.
Esempio
Consideriamo una data funzione, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.
Considerando $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ per tutti i valori di $n > 0$.
Quindi, la complessità di f(n) può essere rappresentato come $\Omega (g(n))$, ie $\Omega (n^3)$
θ: Asintotico Tight Bound
Lo diciamo noi $f(n) = \theta(g(n))$ quando esistono costanti c1 e c2 quello $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ per tutti un valore sufficientemente elevato di n. Quin è un numero intero positivo.
Questo significa funzione g è un limite stretto per la funzione f.
Esempio
Consideriamo una data funzione, $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)$ per tutti i grandi valori di n.
Quindi, la complessità di f(n) può essere rappresentato come $\theta (g(n))$, ie $\theta (n^3)$.
O - Notazione
Il limite superiore asintotico fornito da O-notationpuò o non può essere asintoticamente stretto. Il vincolato$2.n^2 = O(n^2)$ è asintoticamente stretto, ma il limite $2.n = O(n^2)$ non è.
Noi usiamo o-notation per denotare un limite superiore che non è asintoticamente stretto.
Definiamo formalmente o(g(n)) (little-oh of g of n) come l'insieme f(n) = o(g(n)) per qualsiasi costante positiva $c > 0$ e esiste un valore $n_{0} > 0$, tale che $0 \leqslant f(n) \leqslant c.g(n)$.
Intuitivamente, in o-notation, la funzione f(n) diventa insignificante rispetto a g(n) come nsi avvicina all'infinito; questo è,
$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$
Esempio
Consideriamo la stessa funzione, $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$$
Quindi, la complessità di f(n) può essere rappresentato come $o(g(n))$, ie $o(n^4)$.
ω - Notazione
Noi usiamo ω-notationper denotare un limite inferiore che non è asintoticamente stretto. Formalmente, tuttavia, definiamoω(g(n)) (little-omega of g of n) as the set f(n) = ω(g(n)) per qualsiasi costante positiva C > 0 e esiste un valore $n_{0} > 0$, tale che $ 0 \ leqslant cg (n) <f (n) $.
Per esempio, $\frac{n^2}{2} = \omega (n)$, ma $\frac{n^2}{2} \neq \omega (n^2)$. La relazione$f(n) = \omega (g(n))$ implica che esista il seguente limite
$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$
Questo è, f(n) diventa arbitrariamente grande rispetto a g(n) come n si avvicina all'infinito.
Esempio
Consideriamo la stessa funzione, $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$$
Quindi, la complessità di f(n) può essere rappresentato come $o(g(n))$, ie $\omega (n^2)$.
Analisi Apriori e Apostiari
Analisi Apriori significa che l'analisi viene eseguita prima di eseguirla su un sistema specifico. Questa analisi è una fase in cui una funzione viene definita utilizzando un modello teorico. Quindi, determiniamo la complessità temporale e spaziale di un algoritmo semplicemente osservando l'algoritmo anziché eseguirlo su un particolare sistema con una memoria, un processore e un compilatore diversi.
Analisi apostiari di un algoritmo significa che eseguiamo l'analisi di un algoritmo solo dopo averlo eseguito su un sistema. Dipende direttamente dal sistema e cambia da sistema a sistema.
In un settore non possiamo eseguire analisi Apostiari in quanto il software è generalmente realizzato per un utente anonimo, che lo esegue su un sistema diverso da quelli presenti nel settore.
In Apriori, è il motivo per cui usiamo notazioni asintotiche per determinare la complessità temporale e spaziale mentre cambiano da computer a computer; tuttavia, asintoticamente sono gli stessi.
In questo capitolo discuteremo la complessità dei problemi computazionali rispetto alla quantità di spazio richiesta da un algoritmo.
La complessità dello spazio condivide molte delle caratteristiche della complessità del tempo e serve come un ulteriore modo per classificare i problemi in base alle loro difficoltà computazionali.
Cos'è la complessità spaziale?
La complessità dello spazio è una funzione che descrive la quantità di memoria (spazio) che un algoritmo richiede in termini di quantità di input all'algoritmo.
Si parla spesso di extra memorynecessario, senza contare la memoria necessaria per memorizzare l'input stesso. Ancora una volta, usiamo unità naturali (ma di lunghezza fissa) per misurarlo.
Possiamo usare i byte, ma è più facile usare, diciamo, il numero di interi usati, il numero di strutture di dimensioni fisse, ecc.
Alla fine, la funzione che creeremo sarà indipendente dal numero effettivo di byte necessari per rappresentare l'unità.
La complessità dello spazio a volte viene ignorata perché lo spazio utilizzato è minimo e / o ovvio, tuttavia a volte diventa una questione importante quanto la complessità del tempo
Definizione
Permettere M essere deterministico Turing machine (TM)che si ferma su tutti gli input. La complessità spaziale diM è la funzione $f \colon N \rightarrow N$, dove f(n) è il numero massimo di celle del nastro e M esegue la scansione di qualsiasi input di lunghezza M. Se la complessità dello spazio diM è f(n), possiamo dirlo M corre nello spazio f(n).
Stimiamo la complessità spaziale della macchina di Turing utilizzando la notazione asintotica.
Permettere $f \colon N \rightarrow R^+$essere una funzione. Le classi di complessità spaziale possono essere definite come segue:
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 è la classe di linguaggi decidibili nello spazio polinomiale su una macchina di Turing deterministica.
In altre parole, PSPACE = Uk SPACE (nk)
Teorema di Savitch
Uno dei primi teoremi relativi alla complessità spaziale è il teorema di Savitch. Secondo questo teorema, una macchina deterministica può simulare macchine non deterministiche utilizzando una piccola quantità di spazio.
Per la complessità temporale, una simile simulazione sembra richiedere un aumento esponenziale del tempo. Per la complessità spaziale, questo teorema mostra che qualsiasi macchina di Turing non deterministica che utilizzaf(n) lo spazio può essere convertito in una TM deterministica che utilizza f2(n) spazio.
Quindi, il teorema di Savitch afferma che, per qualsiasi funzione, $f \colon N \rightarrow R^+$, dove $f(n) \geqslant n$
NSPACE(f(n)) ⊆ SPACE(f(n))
Relazione tra classi di complessità
Il diagramma seguente illustra la relazione tra le diverse classi di complessità.
Fino ad ora, non abbiamo discusso delle classi P e NP in questo tutorial. Questi saranno discussi in seguito.
Molti algoritmi sono di natura ricorsiva per risolvere un dato problema ricorsivamente trattando sotto-problemi.
In divide and conquer approach, un problema viene diviso in problemi più piccoli, quindi i problemi più piccoli vengono risolti indipendentemente e infine le soluzioni di problemi più piccoli vengono combinate in una soluzione per il problema più grande.
In generale, gli algoritmi divide et impera hanno tre parti:
Divide the problem in una serie di problemi secondari che sono istanze più piccole dello stesso problema.
Conquer the sub-problemsrisolvendoli in modo ricorsivo. Se sono abbastanza piccoli, risolvi i sottoproblemi come casi base.
Combine the solutions ai sotto-problemi nella soluzione del problema originale.
Pro e contro dell'approccio Divide and Conquer
L'approccio divide et impera supporta il parallelismo poiché i problemi secondari sono indipendenti. Quindi, un algoritmo, progettato utilizzando questa tecnica, può essere eseguito sul sistema multiprocessore o su macchine diverse contemporaneamente.
In questo approccio, la maggior parte degli algoritmi sono progettati utilizzando la ricorsione, quindi la gestione della memoria è molto alta. Per le funzioni ricorsive viene utilizzato lo stack, in cui è necessario memorizzare lo stato della funzione.
Applicazione dell'approccio Divide and Conquer
Di seguito sono riportati alcuni problemi, che vengono risolti utilizzando l'approccio divide et impera.
- Trovare il massimo e il minimo di una sequenza di numeri
- La moltiplicazione della matrice di Strassen
- Unisci ordinamento
- Ricerca binaria
Consideriamo un semplice problema che può essere risolto con la tecnica del divide et impera.
Dichiarazione problema
Il problema Max-Min nell'analisi algoritmica è trovare il valore massimo e minimo in un array.
Soluzione
Per trovare i numeri massimi e minimi in un dato array numbers[] di dimensioni n, è possibile utilizzare il seguente algoritmo. Per prima cosa rappresentiamo ilnaive method e poi ci presenteremo divide and conquer approach.
Metodo naïve
Il metodo naïve è un metodo di base per risolvere qualsiasi problema. In questo metodo, il numero massimo e minimo possono essere trovati separatamente. Per trovare i numeri massimi e minimi, è possibile utilizzare il seguente semplice algoritmo.
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)
Analisi
Il numero di confronti nel metodo Naive è 2n - 2.
Il numero di confronti può essere ridotto utilizzando l'approccio divide et impera. Di seguito è la tecnica.
Approccio di divisione e conquista
In questo approccio, l'array è diviso in due metà. Quindi utilizzando l'approccio ricorsivo si trovano i numeri massimi e minimi in ciascuna metà. Successivamente, restituisci il massimo di due massimi di ciascuna metà e il minimo di due minimi di ciascuna metà.
In questo dato problema, il numero di elementi in un array è $y - x + 1$, dove y è più grande di O uguale a x.
$\mathbf{\mathit{Max - Min(x, y)}}$ restituirà i valori massimo e minimo di un array $\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))
Analisi
Permettere T(n) essere il numero di confronti effettuati da $\mathbf{\mathit{Max - Min(x, y)}}$, dove il numero di elementi $n = y - x + 1$.
Se T(n) rappresenta i numeri, quindi la relazione di ricorrenza può essere rappresentata come
$$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}$$
Supponiamo che n è sotto forma di potere di 2. Quindi,n = 2k dove k è l'altezza dell'albero di ricorsione.
Così,
$$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$$
Rispetto al metodo Naïve, nell'approccio divide et impera, il numero di confronti è inferiore. Tuttavia, utilizzando la notazione asintotica entrambi gli approcci sono rappresentati daO(n).
In questo capitolo, discuteremo l'ordinamento di tipo merge e ne analizzeremo la complessità.
Dichiarazione problema
Il problema dell'ordinamento di un elenco di numeri si presta immediatamente a una strategia divide et impera: dividere l'elenco in due metà, ordinare ricorsivamente ciascuna metà e quindi unire le due sotto-liste ordinate.
Soluzione
In questo algoritmo, i numeri vengono memorizzati in una matrice numbers[]. Qui,p e q rappresenta l'indice iniziale e finale di un sotto-array.
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
Analisi
Consideriamo il tempo di esecuzione di Merge-Sort come T(n). Quindi,
$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$dove c e d sono costanti
Pertanto, utilizzando questa relazione di ricorrenza,
$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$
Come, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$
$=\:c.n + d.n.log\:n$
Perciò, $T(n) = O(n\:log\:n)$
Esempio
Nel seguente esempio, abbiamo mostrato passo dopo passo l'algoritmo Merge-Sort. Innanzitutto, ogni array di iterazione è diviso in due sotto-array, fino a quando il sotto-array non contiene solo un elemento. Quando questi sotto-array non possono essere divisi ulteriormente, vengono eseguite le operazioni di unione.
In questo capitolo, discuteremo un altro algoritmo basato sul metodo divide et impera.
Dichiarazione problema
La ricerca binaria può essere eseguita su un array ordinato. In questo approccio, l'indice di un elementoxviene determinato se l'elemento appartiene all'elenco degli elementi. Se l'array non è ordinato, viene utilizzata la ricerca lineare per determinare la posizione.
Soluzione
In questo algoritmo, vogliamo trovare se element x appartiene a un insieme di numeri memorizzati in un array numbers[]. Dovel e r rappresentano l'indice sinistro e destro di un sotto-array in cui deve essere eseguita l'operazione di ricerca.
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)
Analisi
La ricerca lineare viene eseguita O(n)tempo. Mentre la ricerca binaria produce il risultato inO(log n) tempo
Permettere T(n) essere il numero di confronti nel caso peggiore in un array di n elementi.
Quindi,
$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$
Usando questa relazione di ricorrenza $T(n) = log\:n$.
Pertanto, la ricerca binaria utilizza $O(log\:n)$ tempo.
Esempio
In questo esempio, cercheremo l'elemento 63.
In questo capitolo discuteremo prima il metodo generale di moltiplicazione di matrici e successivamente discuteremo l'algoritmo di moltiplicazione di matrici di Strassen.
Dichiarazione problema
Consideriamo due matrici X e Y. Vogliamo calcolare la matrice risultanteZ moltiplicando X e Y.
Metodo naïve
Per prima cosa, discuteremo del metodo ingenuo e della sua complessità. Qui stiamo calcolandoZ = X × Y. Utilizzando il metodo Naïve, due matrici (X e Y) può essere moltiplicato se l'ordine di queste matrici è p × q e q × r. Di seguito è riportato l'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]
Complessità
Qui, assumiamo che le operazioni su interi richiedano O(1)tempo. Ce ne sono treforloop in questo algoritmo e uno è annidato in un altro. Quindi, l'algoritmo accettaO(n3) tempo di eseguire.
Algoritmo di moltiplicazione della matrice di Strassen
In questo contesto, utilizzando l'algoritmo di moltiplicazione Matrix di Strassen, il consumo di tempo può essere leggermente migliorato.
La moltiplicazione Matrix di Strassen può essere eseguita solo su square matrices dove n è un power of 2. L'ordine di entrambe le matrici èn × n.
Dividere X, Y e Z in quattro (n / 2) × (n / 2) matrici come rappresentato di seguito -
$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}$
Utilizzando l'algoritmo di Strassen, calcola quanto segue:
$$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)$$
Poi,
$$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}$$
Analisi
$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$dove c e d sono costanti
Usando questa relazione di ricorrenza, otteniamo $T(n) = O(n^{log7})$
Quindi, la complessità dell'algoritmo di moltiplicazione di matrici di Strassen è $O(n^{log7})$.
Tra tutti gli approcci algoritmici, l'approccio più semplice e diretto è il metodo Greedy. In questo approccio, la decisione viene presa sulla base delle informazioni attualmente disponibili senza preoccuparsi degli effetti della decisione corrente in futuro.
Gli algoritmi avidi costruiscono una soluzione parte per parte, scegliendo la parte successiva in modo tale da dare un vantaggio immediato. Questo approccio non riconsidera mai le scelte prese in precedenza. Questo approccio viene utilizzato principalmente per risolvere i problemi di ottimizzazione. Il metodo Greedy è facile da implementare e abbastanza efficiente nella maggior parte dei casi. Quindi, possiamo dire che l'algoritmo Greedy è un paradigma algoritmico basato sull'euristica che segue la scelta ottimale locale in ogni fase con la speranza di trovare una soluzione ottimale globale.
In molti problemi, non produce una soluzione ottimale sebbene dia una soluzione approssimativa (quasi ottimale) in un tempo ragionevole.
Componenti di Greedy Algorithm
Gli algoritmi Greedy hanno i seguenti cinque componenti:
A candidate set - Una soluzione viene creata da questo set.
A selection function - Utilizzato per scegliere il miglior candidato da aggiungere alla soluzione.
A feasibility function - Utilizzato per determinare se un candidato può essere utilizzato per contribuire alla soluzione.
An objective function - Utilizzato per assegnare un valore a una soluzione o una soluzione parziale.
A solution function - Usato per indicare se è stata raggiunta una soluzione completa.
Aree di applicazione
L'approccio avido viene utilizzato per risolvere molti problemi, ad esempio
Trovare il percorso più breve tra due vertici utilizzando l'algoritmo di Dijkstra.
Trovare lo spanning tree minimo in un grafico usando l'algoritmo di Prim / Kruskal, ecc.
Dove l'approccio avido fallisce
In molti problemi, l'algoritmo Greedy non riesce a trovare una soluzione ottimale, inoltre può produrre una soluzione peggiore. Problemi come il venditore ambulante e lo zaino non possono essere risolti utilizzando questo approccio.
L'algoritmo Greedy potrebbe essere compreso molto bene con un noto problema denominato problema dello zaino. Sebbene lo stesso problema possa essere risolto impiegando altri approcci algoritmici, l'approccio Greedy risolve il problema dello zaino frazionario ragionevolmente in tempo utile. Parliamo in dettaglio del problema dello zaino.
Problema dello zaino
Dato un insieme di articoli, ciascuno con un peso e un valore, determinare un sottoinsieme di articoli da includere in una raccolta in modo che il peso totale sia inferiore o uguale a un determinato limite e il valore totale sia il più grande possibile.
Il problema dello zaino è nel problema dell'ottimizzazione combinatoria. Appare come un sottoproblema in molti modelli matematici più complessi di problemi del mondo reale. Un approccio generale ai problemi difficili consiste nell'identificare il vincolo più restrittivo, ignorare gli altri, risolvere un problema con lo zaino e in qualche modo aggiustare la soluzione per soddisfare i vincoli ignorati.
Applicazioni
In molti casi di allocazione delle risorse insieme a qualche vincolo, il problema può essere derivato in modo simile al problema dello zaino. Di seguito è riportato un insieme di esempi.
- Trovare il modo meno dispendioso per tagliare le materie prime
- ottimizzazione del portafoglio
- Problemi di taglio delle scorte
Scenario problematico
Un ladro sta rapinando un negozio e può portare un peso massimo di Wnello zaino. Ci sono n articoli disponibili nel negozio e il peso diith l'oggetto è wi e il suo profitto è pi. Quali oggetti dovrebbe prendere il ladro?
In questo contesto, gli oggetti dovrebbero essere selezionati in modo tale che il ladro trasporterà quegli oggetti per i quali otterrà il massimo profitto. Quindi, l'obiettivo del ladro è massimizzare il profitto.
In base alla natura degli articoli, i problemi dello zaino sono classificati come
- Zaino frazionario
- Knapsack
Zaino frazionario
In questo caso, gli oggetti possono essere suddivisi in pezzi più piccoli, quindi il ladro può selezionare frazioni di oggetti.
Secondo la dichiarazione del problema,
Ci sono n articoli nel negozio
Peso di ith articolo $w_{i} > 0$
Utile per ith articolo $p_{i} > 0$ e
La capacità dello zaino è W
In questa versione del problema dello zaino, gli oggetti possono essere suddivisi in pezzi più piccoli. Quindi, il ladro può prendere solo una frazionexi di ith articolo.
$$0 \leqslant x_{i} \leqslant 1$$
Il ith l'elemento contribuisce al peso $x_{i}.w_{i}$ al peso totale nello zaino e profitto $x_{i}.p_{i}$ al profitto totale.
Quindi, l'obiettivo di questo algoritmo è quello di
$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$
soggetto a vincolo,
$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$
È chiaro che una soluzione ottimale deve riempire esattamente lo zaino, altrimenti potremmo aggiungere una frazione di una delle rimanenti voci e aumentare il profitto complessivo.
Pertanto, una soluzione ottimale può essere ottenuta con
$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$
In questo contesto, prima dobbiamo ordinare gli elementi in base al valore di $\frac{p_{i}}{w_{i}}$, così che $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. Qui,x è un array per memorizzare la frazione di elementi.
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
Analisi
Se gli elementi forniti sono già ordinati in ordine decrescente di $\mathbf{\frac{p_{i}}{w_{i}}}$, quindi il whileloop impiega un po 'di tempo O(n); Pertanto, il tempo totale compreso l'ordinamento è inO(n logn).
Esempio
Consideriamo quella la capacità dello zaino W = 60 e l'elenco degli elementi forniti sono riportati nella tabella seguente:
Articolo | UN | B | C | D |
---|---|---|---|---|
Profitto | 280 | 100 | 120 | 120 |
Peso | 40 | 10 | 20 | 24 |
Rapporto $(\frac{p_{i}}{w_{i}})$ | 7 | 10 | 6 | 5 |
Poiché gli elementi forniti non vengono ordinati in base a $\mathbf{\frac{p_{i}}{w_{i}}}$. Dopo l'ordinamento, gli articoli sono come mostrato nella tabella seguente.
Articolo | B | UN | C | D |
---|---|---|---|---|
Profitto | 100 | 280 | 120 | 120 |
Peso | 10 | 40 | 20 | 24 |
Rapporto $(\frac{p_{i}}{w_{i}})$ | 10 | 7 | 6 | 5 |
Soluzione
Dopo aver ordinato tutti gli articoli in base a $\frac{p_{i}}{w_{i}}$. Prima di tuttoB è scelto come peso di Bè inferiore alla capacità dello zaino. Successivamente, elementoA viene scelto, poiché la capacità disponibile dello zaino è maggiore del peso di A. Adesso,Cviene scelto come elemento successivo. Tuttavia, l'intero articolo non può essere scelto poiché la capacità rimanente dello zaino è inferiore al peso diC.
Quindi, frazione di C (cioè (60 - 50) / 20) è scelto.
Ora, la capacità dello zaino è uguale agli articoli selezionati. Pertanto, non è più possibile selezionare alcun elemento.
Il peso totale degli articoli selezionati è 10 + 40 + 20 * (10/20) = 60
E il profitto totale è 100 + 280 + 120 * (10/20) = 380 + 60 = 440
Questa è la soluzione ottimale. Non possiamo guadagnare di più selezionando una diversa combinazione di articoli.
Dichiarazione problema
Nel problema della sequenza dei lavori, l'obiettivo è trovare una sequenza di lavori che venga completata entro le scadenze e dia il massimo profitto.
Soluzione
Consideriamo un insieme di ndeterminati lavori associati a scadenze e profitto viene guadagnato, se un lavoro viene completato entro la scadenza. Questi lavori devono essere ordinati in modo tale da ottenere il massimo profitto.
Può accadere che tutti i lavori forniti non vengano completati entro le scadenze.
Supponiamo, scadenza del ith lavoro Ji è di e il profitto ricevuto da questo lavoro è pi. Quindi, la soluzione ottimale di questo algoritmo è una soluzione fattibile con il massimo profitto.
Quindi, $D(i) > 0$ per $1 \leqslant i \leqslant n$.
Inizialmente, questi lavori vengono ordinati in base al profitto, ovvero $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
Analisi
In questo algoritmo, stiamo usando due loop, uno all'interno dell'altro. Quindi, la complessità di questo algoritmo è$O(n^2)$.
Esempio
Consideriamo un insieme di lavori dati come mostrato nella tabella seguente. Dobbiamo trovare una sequenza di lavori, che saranno completati entro le scadenze e daranno il massimo profitto. Ad ogni lavoro è associata una scadenza e un profitto.
Lavoro | J1 | J2 | J3 | J4 | J5 |
---|---|---|---|---|---|
Scadenza | 2 | 1 | 3 | 2 | 1 |
Profitto | 60 | 100 | 20 | 40 | 20 |
Soluzione
Per risolvere questo problema, i lavori forniti vengono ordinati in base al loro profitto in ordine decrescente. Quindi, dopo l'ordinamento, i lavori vengono ordinati come mostrato nella tabella seguente.
Lavoro | J2 | J1 | J4 | J3 | J5 |
---|---|---|---|---|---|
Scadenza | 1 | 2 | 2 | 3 | 1 |
Profitto | 100 | 60 | 40 | 20 | 20 |
Da questo insieme di lavori, prima selezioniamo J2, in quanto può essere completato entro la sua scadenza e contribuisce al massimo profitto.
Il prossimo, J1 è selezionato in quanto dà più profitto rispetto a J4.
Nel prossimo orologio, J4 non può essere selezionato poiché la sua scadenza è scaduta, quindi J3 è selezionato mentre viene eseguito entro la scadenza.
Il lavoro J5 viene scartato in quanto non può essere eseguito entro la scadenza.
Quindi, la soluzione è la sequenza di lavori (J2, J1, J3), che vengono eseguiti entro la loro scadenza e danno il massimo profitto.
Il profitto totale di questa sequenza è 100 + 60 + 20 = 180.
Unisci una serie di file ordinati di diversa lunghezza in un unico file ordinato. Dobbiamo trovare una soluzione ottimale, in cui il file risultante verrà generato in un tempo minimo.
Se viene fornito il numero di file ordinati, esistono molti modi per unirli in un unico file ordinato. Questa unione può essere eseguita in coppia. Quindi, questo tipo di fusione è chiamato come2-way merge patterns.
Poiché accoppiamenti diversi richiedono quantità di tempo diverse, in questa strategia vogliamo determinare un modo ottimale per unire più file insieme. Ad ogni passaggio, vengono unite due sequenze più brevi.
Per unire un file p-record file e a q-record file richiede possibilmente p + q registrare le mosse, la scelta più ovvia è unire i due file più piccoli insieme ad ogni passaggio.
I modelli di unione a due vie possono essere rappresentati da alberi di unione binari. Consideriamo un insieme din file ordinati {f1, f2, f3, …, fn}. Inizialmente, ogni elemento di questo è considerato come un albero binario a nodo singolo. Per trovare questa soluzione ottimale, viene utilizzato il seguente algoritmo.
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);
Alla fine di questo algoritmo, il peso del nodo radice rappresenta il costo ottimale.
Esempio
Consideriamo i file dati, f 1 , f 2 , f 3 , f 4 e f 5 con rispettivamente 20, 30, 10, 5 e 30 numero di elementi.
Se le operazioni di unione vengono eseguite secondo la sequenza fornita, allora
M1 = merge f1 and f2 => 20 + 30 = 50
M2 = merge M1 and f3 => 50 + 10 = 60
M3 = merge M2 and f4 => 60 + 5 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Quindi, il numero totale di operazioni è
50 + 60 + 65 + 95 = 270
Ora, sorge la domanda: esiste una soluzione migliore?
Ordinando i numeri in base alla loro dimensione in ordine crescente, otteniamo la seguente sequenza:
f4, f3, f1, f2, f5
Quindi, le operazioni di unione possono essere eseguite su questa sequenza
M1 = merge f4 and f3 => 5 + 10 = 15
M2 = merge M1 and f1 => 15 + 20 = 35
M3 = merge M2 and f2 => 35 + 30 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Pertanto, il numero totale di operazioni è
15 + 35 + 65 + 95 = 210
Ovviamente questo è migliore del precedente.
In questo contesto, risolveremo ora il problema utilizzando questo algoritmo.
Set iniziale
Passo 1
Passo 2
Passaggio 3
Passaggio 4
Quindi, la soluzione richiede 15 + 35 + 60 + 95 = 205 numero di confronti.
La programmazione dinamica viene utilizzata anche nei problemi di ottimizzazione. Come il metodo divide et impera, la programmazione dinamica risolve i problemi combinando le soluzioni dei sottoproblemi. Inoltre, l'algoritmo di programmazione dinamica risolve ogni sottoproblema una sola volta e poi salva la sua risposta in una tabella, evitando così il lavoro di rielaborare la risposta ogni volta.
Due proprietà principali di un problema suggeriscono che il problema dato può essere risolto utilizzando la programmazione dinamica. Queste proprietà sonooverlapping sub-problems and optimal substructure.
Problemi secondari sovrapposti
Simile all'approccio Divide-and-Conquer, la programmazione dinamica combina anche soluzioni a problemi secondari. Viene utilizzato principalmente quando è necessaria ripetutamente la soluzione di un sottoproblema. Le soluzioni calcolate vengono memorizzate in una tabella, in modo che non debbano essere ricalcolate. Quindi, questa tecnica è necessaria laddove esistono problemi secondari sovrapposti.
Ad esempio, la ricerca binaria non presenta problemi secondari sovrapposti. Considerando che il programma ricorsivo di numeri di Fibonacci ha molti problemi secondari sovrapposti.
Sottostruttura ottimale
Un dato problema ha una proprietà di sottostruttura ottimale, se la soluzione ottimale del problema dato può essere ottenuta utilizzando soluzioni ottimali dei suoi problemi secondari.
Ad esempio, il problema del percorso più breve ha la seguente proprietà di sottostruttura ottimale:
Se un nodo x si trova nel percorso più breve da un nodo di origine u al nodo di destinazione v, quindi il percorso più breve da u per v è la combinazione del percorso più breve da u per xe il percorso più breve da x per v.
Gli algoritmi standard All Pair Shortest Path come Floyd-Warshall e Bellman-Ford sono esempi tipici di programmazione dinamica.
Fasi dell'approccio dinamico alla programmazione
L'algoritmo di programmazione dinamica è progettato utilizzando i seguenti quattro passaggi:
- Caratterizzano la struttura di una soluzione ottimale.
- Definisci ricorsivamente il valore di una soluzione ottimale.
- Calcola il valore di una soluzione ottimale, in genere dal basso verso l'alto.
- Costruisci una soluzione ottimale dalle informazioni calcolate.
Applicazioni dell'approccio dinamico alla programmazione
- Matrix Chain Moltiplicazione
- Successione comune più lunga
- Problema del commesso viaggiatore
In questo tutorial, in precedenza abbiamo discusso il problema dello zaino frazionario utilizzando l'approccio Greedy. Abbiamo dimostrato che l'approccio Greedy fornisce una soluzione ottimale per Fractional Knapsack. Tuttavia, questo capitolo tratterà il problema dello zaino 0-1 e la sua analisi.
In 0-1 Knapsack, gli oggetti non possono essere rotti, il che significa che il ladro dovrebbe prendere l'oggetto nel suo insieme o lasciarlo. Questo è il motivo per chiamarlo 0-1 Knapsack.
Quindi, in caso di 0-1 Knapsack, il valore di xi può essere l'uno o l'altro 0 o 1, dove gli altri vincoli rimangono gli stessi.
Lo zaino 0-1 non può essere risolto con un approccio avido. L'approccio avido non garantisce una soluzione ottimale. In molti casi, l'approccio Greedy può fornire una soluzione ottimale.
I seguenti esempi stabiliranno la nostra dichiarazione.
Esempio 1
Si consideri che la capacità dello zaino è W = 25 e gli articoli sono come mostrato nella tabella seguente.
Articolo | UN | B | C | D |
---|---|---|---|---|
Profitto | 24 | 18 | 18 | 10 |
Peso | 24 | 10 | 10 | 7 |
Senza considerare il profitto per unità di peso (pi/wi), se applichiamo l'approccio Greedy per risolvere questo problema, primo elemento Asaranno selezionati in quanto contribuirà massimo i profitti mamma tra tutti gli elementi.
Dopo aver selezionato l'elemento A, non verrà selezionato più alcun elemento. Quindi, per questo dato insieme di elementi il profitto totale è24. Considerando che, la soluzione ottimale può essere ottenuta selezionando elementi,B e C, dove il profitto totale è 18 + 18 = 36.
Esempio-2
Invece di selezionare gli elementi in base al vantaggio complessivo, in questo esempio gli elementi vengono selezionati in base al rapporto p i / w i . Consideriamo che la capacità dello zaino è W = 60 e gli articoli sono come mostrato nella tabella seguente.
Articolo | UN | B | C |
---|---|---|---|
Prezzo | 100 | 280 | 120 |
Peso | 10 | 40 | 20 |
Rapporto | 10 | 7 | 6 |
Usando l'approccio Greedy, primo elemento Aè selezionato. Quindi, l'elemento successivoBè scelto. Quindi, il profitto totale è100 + 280 = 380. Tuttavia, la soluzione ottimale di questa istanza può essere ottenuta selezionando elementi,B e C, dove si trova il profitto totale 280 + 120 = 400.
Quindi, si può concludere che l'approccio Greedy potrebbe non fornire una soluzione ottimale.
Per risolvere lo zaino 0-1, è richiesto l'approccio della programmazione dinamica.
Dichiarazione problema
Un ladro sta derubando un negozio e può trasportare un massimo i peso mal diWnello zaino. Ci sonon articoli e peso di ith l'oggetto è wi e il profitto della selezione di questo articolo è pi. Quali oggetti dovrebbe prendere il ladro?
Approccio alla programmazione dinamica
Permettere i essere l'elemento con il numero più alto in una soluzione ottimale S per Wdollari. PoiS' = S - {i} è una soluzione ottimale per W - wi dollari e il valore della soluzione S è Vi più il valore del problema secondario.
Possiamo esprimere questo fatto nella seguente formula: definire c[i, w] per essere la soluzione per gli oggetti 1,2, … , ie il massimo che peso mammaw.
L'algoritmo accetta i seguenti input
Il massimo i peso mammaW
Il numero di elementi n
Le due sequenze v = <v1, v2, …, vn> e w = <w1, w2, …, wn>
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]
L'insieme di elementi da prendere può essere dedotto dalla tabella, a partire da c[n, w] e risalendo all'indietro da dove provengono i valori ottimali.
Se c [i, w] = c [i-1, w] , allora elementoi non fa parte della soluzione e continuiamo a tracciare con c[i-1, w]. Altrimenti, articoloi è parte della soluzione e continuiamo a tracciare con c[i-1, w-W].
Analisi
Questo algoritmo richiede θ ( n , w ) volte poiché la tabella c ha ( n + 1). ( W + 1) voci, dove ogni voce richiede θ (1) tempo per essere calcolata.
Il problema di sottosequenza comune più lungo è trovare la sequenza più lunga che esiste in entrambe le stringhe date.
Sotto sequenza
Consideriamo una successione S = <s 1 , s 2 , s 3 , s 4 ,…, s n >.
Una successione Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > su S è detta sottosequenza di S, se e solo se può essere derivata dalla cancellazione di S di alcuni elementi.
Successione comune
Supponiamo, X e Ysono due sequenze su un insieme finito di elementi. Possiamo dirloZ è una sottosequenza comune di X e Y, Se Z è una sottosequenza di entrambi X e Y.
Successione comune più lunga
Se viene fornito un insieme di sequenze, il problema di sottosequenza comune più lungo è trovare una sottosequenza comune di tutte le sequenze che sia di lunghezza massima.
Il problema di sottosequenza comune più lungo è un classico problema di informatica, la base dei programmi di confronto dei dati come l'utilità diff e ha applicazioni in bioinformatica. È anche ampiamente utilizzato dai sistemi di controllo delle revisioni, come SVN e Git, per riconciliare più modifiche apportate a una raccolta di file controllata dalla revisione.
Metodo naïve
Permettere X essere una sequenza di lunghezza m e Y una sequenza di lunghezza n. Verificare ogni sottosequenza diX se è una sottosequenza di Ye restituisce la sottosequenza comune più lunga trovata.
Ci sono 2m sottosequenze di X. Verificare le sequenze che si tratti o meno di una sottosequenza diY prende O(n)tempo. Quindi, l'algoritmo ingenuo prenderebbeO(n2m) tempo.
Programmazione dinamica
Siano le sequenze X = <x 1 , x 2 , x 3 ,…, x m > e Y = <y 1 , y 2 , y 3 ,…, y n > . Per calcolare la lunghezza di un elemento viene utilizzato il seguente algoritmo.
In questa procedura, table C[m, n] viene calcolato in ordine di riga principale e un'altra tabella B[m,n] viene calcolato per costruire una soluzione ottimale.
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)
Questo algoritmo stamperà la sottosequenza comune più lunga di X e Y.
Analisi
A popolare la tabella, il file outer for ciclo itera m volte e l'interno for ciclo itera nvolte. Quindi, la complessità dell'algoritmo è O (m, n) , dovem e n sono la lunghezza di due stringhe.
Esempio
In questo esempio, abbiamo due stringhe X = BACDB e Y = BDCB per trovare la sottosequenza comune più lunga.
Seguendo l'algoritmo LCS-Length-Table-Formulation (come indicato sopra), abbiamo calcolato la tabella C (mostrata a sinistra) e la tabella B (mostrata a destra).
Nella tabella B, invece di "D", "L" e "U", utilizziamo rispettivamente la freccia diagonale, la freccia sinistra e la freccia su. Dopo aver generato la tabella B, l'LCS è determinato dalla funzione LCS-Print. Il risultato è BCB.
UN spanning tree è un sottoinsieme di un Graph non orientato che ha tutti i vertici collegati da un numero minimo di bordi.
Se tutti i vertici sono collegati in un grafo, esiste almeno uno spanning tree. In un grafico, possono esistere più di uno spanning tree.
Proprietà
- Uno spanning tree non ha alcun ciclo.
- Qualsiasi vertice può essere raggiunto da qualsiasi altro vertice.
Esempio
Nel grafico seguente, i bordi evidenziati formano uno spanning tree.
Spanning Tree minimo
UN Minimum Spanning Tree (MST)è un sottoinsieme di bordi di un grafo non orientato ponderato connesso che collega tutti i vertici insieme con il peso del bordo totale minimo possibile. Per derivare un MST, è possibile utilizzare l'algoritmo di Prim o l'algoritmo di Kruskal. Quindi, discuteremo l'algoritmo di Prim in questo capitolo.
Come abbiamo discusso, un grafo può avere più di uno spanning tree. Se ci sonon numero di vertici, lo spanning tree dovrebbe avere n - 1numero di bordi. In questo contesto, se ogni bordo del grafico è associato a un peso ed esistono più di uno spanning tree, dobbiamo trovare lo spanning tree minimo del grafico.
Inoltre, se esistono bordi ponderati duplicati, il grafico può avere più spanning tree minimi.
Nel grafico sopra, abbiamo mostrato uno spanning tree sebbene non sia lo spanning tree minimo. Il costo di questo albero di copertura è (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.
Useremo l'algoritmo di Prim per trovare lo spanning tree minimo.
Algoritmo di Prim
L'algoritmo di Prim è un approccio avido per trovare l'albero di copertura minimo. In questo algoritmo, per formare un MST possiamo partire da un vertice arbitrario.
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)
La funzione Extract-Min restituisce il vertice con il minimo costo del bordo. Questa funzione funziona su min-heap.
Esempio
Usando l'algoritmo di Prim, possiamo partire da qualsiasi vertice, partiamo dal vertice 1.
Vertice 3 è connesso al vertice 1 con il minimo costo del bordo, quindi bordo (1, 2) viene aggiunto allo spanning tree.
Avanti, bordo (2, 3) è considerato come questo è il minimo tra i bordi {(1, 2), (2, 3), (3, 4), (3, 7)}.
Nel passaggio successivo, otteniamo vantaggio (3, 4) e (2, 4)con un costo minimo. Bordo(3, 4) è selezionato a caso.
In modo simile, i bordi (4, 5), (5, 7), (7, 8), (6, 8) e (6, 9)sono selezionati. Quando tutti i vertici vengono visitati, ora l'algoritmo si ferma.
Il costo dello spanning tree è (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. Non c'è più spanning tree in questo grafico con un costo inferiore a 23.
Algoritmo di Dijkstra
L'algoritmo di Dijkstra risolve il problema dei cammini minimi da una sola sorgente su un grafo ponderato diretto G = (V, E) , dove tutti gli archi sono non negativi (cioè, w (u, v) ≥ 0 per ogni arco (u, v ) Є E ).
Nel seguente algoritmo, useremo una funzione Extract-Min(), che estrae il nodo con la chiave più piccola.
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
Analisi
La complessità di questo algoritmo dipende completamente dall'implementazione della funzione Extract-Min. Se la funzione di estrazione min è implementata utilizzando la ricerca lineare, la complessità di questo algoritmo èO(V2 + E).
In questo algoritmo, se usiamo min-heap su cui Extract-Min() funziona per restituire il nodo da Q con la chiave più piccola, la complessità di questo algoritmo può essere ulteriormente ridotta.
Esempio
Consideriamo il vertice 1 e 9rispettivamente come vertice iniziale e vertice di destinazione. Inizialmente, tutti i vertici tranne il vertice iniziale sono contrassegnati da ∞ e il vertice iniziale è contrassegnato da0.
Vertice | Iniziale | Passaggio 1 V 1 | Passaggio 2 V 3 | Passaggio 3 V 2 | Passaggio 4 V 4 | Passaggio 5 V 5 | Passaggio 6 V 7 | Passaggio 7 V 8 | Passaggio 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 |
Quindi, la distanza minima del vertice 9 dal vertice 1 è 20. E il percorso è
1 → 3 → 7 → 8 → 6 → 9
Questo percorso è determinato in base alle informazioni sul predecessore.
Algoritmo di Bellman Ford
Questo algoritmo risolve il problema del percorso minimo della singola sorgente di un grafo orientato G = (V, E)in cui i pesi dei bordi possono essere negativi. Inoltre, questo algoritmo può essere applicato per trovare il percorso più breve, se non esiste alcun ciclo ponderato negativo.
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
Analisi
Il primo for loop viene utilizzato per l'inizializzazione, che viene eseguita in O(V)volte. Il prossimofor il ciclo viene eseguito |V - 1| passa oltre i bordi, che prendeO(E) volte.
Quindi, l'algoritmo Bellman-Ford funziona O(V, E) tempo.
Esempio
Il seguente esempio mostra passo dopo passo come funziona l'algoritmo Bellman-Ford. Questo grafico ha un margine negativo ma non ha alcun ciclo negativo, quindi il problema può essere risolto utilizzando questa tecnica.
Al momento dell'inizializzazione, tutti i vertici tranne la sorgente sono contrassegnati da ∞ e la sorgente è contrassegnata da 0.
Nella prima fase, tutti i vertici raggiungibili dalla sorgente vengono aggiornati con un costo minimo. Quindi, verticia e h vengono aggiornati.
Nel passaggio successivo, vertici a, b, f e e vengono aggiornati.
Seguendo la stessa logica, in questo passaggio vertici b, f, c e g vengono aggiornati.
Qui, vertici c e d vengono aggiornati.
Quindi, la distanza minima tra i vertici s e vertice d è 20.
In base alle informazioni sul predecessore, il percorso è s → h → e → g → c → d
Un grafico a più fasi G = (V, E) è un grafo diretto in cui sono partizionati i vertici k (dove k > 1) numero di sottoinsiemi disgiunti S = {s1,s2,…,sk}tale che l'arco (u, v) sia in E, allora u Є s i e v Є s 1 + 1 per alcuni sottoinsiemi nella partizione e |s1| = |sk| = 1.
Il vertice s Є s1 si chiama source e il vertice t Є sk è chiamato sink.
Gdi solito si presume che sia un grafico ponderato. In questo grafico, il costo di un arco (i, j) è rappresentato da c (i, j) . Quindi, il costo del percorso dalla fontes affondare t è la somma dei costi di ciascun bordo in questo percorso.
Il problema del grafico multistadio è trovare il percorso con il minimo costo dalla sorgente s affondare t.
Esempio
Considera il seguente esempio per comprendere il concetto di grafo multistadio.
Secondo la formula, dobbiamo calcolare il costo (i, j) utilizzando i seguenti passaggi
Passaggio 1: costo (K-2, j)
In questa fase, tre nodi (nodo 4, 5. 6) vengono selezionati come j. Quindi, abbiamo tre opzioni per scegliere il costo minimo in questo passaggio.
Costo (3, 4) = min {c (4, 7) + Costo (7, 9), c (4, 8) + Costo (8, 9)} = 7
Costo (3, 5) = min {c (5, 7) + Costo (7, 9), c (5, 8) + Costo (8, 9)} = 5
Costo (3, 6) = min {c (6, 7) + Costo (7, 9), c (6, 8) + Costo (8, 9)} = 5
Passaggio 2: costo (K-3, j)
Due nodi sono selezionati come j perché allo stadio k - 3 = 2 ci sono due nodi, 2 e 3. Quindi, il valore i = 2 e j = 2 e 3.
Costo (2, 2) = min {c (2, 4) + Costo (4, 8) + Costo (8, 9), c (2, 6) +
Costo (6, 8) + Costo (8, 9)} = 8
Costo (2, 3) = {c (3, 4) + Costo (4, 8) + Costo (8, 9), c (3, 5) + Costo (5, 8) + Costo (8, 9), c (3, 6) + Costo (6, 8) + Costo (8, 9)} = 10
Passaggio 3: costo (K-4, j)
Costo (1, 1) = {c (1, 2) + Costo (2, 6) + Costo (6, 8) + Costo (8, 9), c (1, 3) + Costo (3, 5) + Costo (5, 8) + Costo (8, 9))} = 12
c (1, 3) + Costo (3, 6) + Costo (6, 8 + Costo (8, 9))} = 13
Quindi, il percorso che ha il costo minimo è 1→ 3→ 5→ 8→ 9.
Dichiarazione problema
Un viaggiatore deve visitare tutte le città da un elenco, in cui le distanze tra tutte le città sono note e ogni città dovrebbe essere visitata una sola volta. Qual è il percorso più breve possibile che visita ogni città esattamente una volta e ritorna alla città di origine?
Soluzione
Il problema del venditore ambulante è il problema computazionale più noto. Possiamo usare l'approccio della forza bruta per valutare ogni possibile tour e selezionare il migliore. Pern numero di vertici in un grafo, ci sono (n - 1)! numero di possibilità.
Invece della forza bruta usando un approccio di programmazione dinamico, la soluzione può essere ottenuta in minor tempo, sebbene non esista un algoritmo temporale polinomiale.
Consideriamo un grafico G = (V, E), dove V è un insieme di città e Eè un insieme di bordi ponderati. Un bordoe(u, v) rappresenta quei vertici u e vsono collegati. Distanza tra i verticiu e v è d(u, v), che dovrebbe essere non negativo.
Supponiamo di aver iniziato in città 1 e dopo aver visitato alcune città ora siamo in città j. Quindi, questo è un tour parziale. Abbiamo sicuramente bisogno di saperej, poiché questo determinerà quali città è più conveniente visitare dopo. Dobbiamo anche conoscere tutte le città visitate finora, in modo da non ripeterne nessuna. Quindi, questo è un problema secondario appropriato.
Per un sottoinsieme di città S Є {1, 2, 3, ... , n} quello include 1, e j Є S, permettere C(S, j) essere la lunghezza del percorso più breve che visita ogni nodo in S esattamente una volta, a partire da 1 e termina a j.
Quando |S| > 1, definiamoC(S, 1) = ∝ poiché il percorso non può iniziare e finire in 1.
Ora, esprimi C(S, j)in termini di sottoproblemi minori. Dobbiamo iniziare da1 e termina a j. Dovremmo selezionare la prossima città in modo tale
$$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)
Analisi
Ce ne sono al massimo $2^n.n$problemi secondari e ognuno richiede tempo lineare per risolverlo. Pertanto, il tempo di esecuzione totale è$O(2^n.n^2)$.
Esempio
Nel seguente esempio, illustreremo i passaggi per risolvere il problema del venditore ambulante.
Dal grafico sopra, viene preparata la seguente tabella.
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}$$
Il percorso del costo minimo è 35.
Inizia dal costo {1, {2, 3, 4}, 1}, otteniamo il valore minimo per d [1, 2]. quandos = 3, seleziona il percorso da 1 a 2 (il costo è 10) quindi torna indietro. quandos = 2, otteniamo il valore minimo per d [4, 2]. Seleziona il percorso da 2 a 4 (il costo è 10) quindi torna indietro.
quando s = 1, otteniamo il valore minimo per d [4, 3]. Selezionando il percorso da 4 a 3 (il costo è 9), andremo a poi as = Φpasso. Otteniamo il valore minimo perd [3, 1] (il costo è 6).
Un albero di ricerca binario (BST) è un albero in cui i valori delle chiavi sono memorizzati nei nodi interni. I nodi esterni sono nodi nulli. Le chiavi sono ordinate lessicograficamente, cioè per ogni nodo interno tutte le chiavi nel sottoalbero di sinistra sono minori delle chiavi nel nodo e tutte le chiavi nel sottoalbero di destra sono maggiori.
Quando conosciamo la frequenza di ricerca di ciascuna chiave, è abbastanza facile calcolare il costo previsto per l'accesso a ciascun nodo dell'albero. Un albero di ricerca binario ottimale è un BST, che ha un costo minimo previsto per l'individuazione di ciascun nodo
Il tempo di ricerca di un elemento in un BST è O(n), mentre in una ricerca Balanced-BST il tempo è O(log n). Anche in questo caso il tempo di ricerca può essere migliorato in Optimal Cost Binary Search Tree, posizionando i dati utilizzati più di frequente nella radice e più vicini all'elemento radice, mentre i dati utilizzati meno frequentemente vicino alle foglie e nelle foglie.
Qui viene presentato l'algoritmo dell'albero di ricerca binaria ottimale. Per prima cosa, costruiamo un BST da una serie di filen numero di chiavi distinte < k1, k2, k3, ... kn >. Qui assumiamo la probabilità di accedere a una chiaveKi è pi. Alcune chiavi fittizie (d0, d1, d2, ... dn) vengono aggiunti in quanto potrebbero essere eseguite alcune ricerche per i valori che non sono presenti nel Key set K. Assumiamo, per ogni chiave fittiziadi la probabilità di accesso è qi.
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
Analisi
L'algoritmo richiede O (n3) tempo, poiché tre annidati forvengono utilizzati i loop. Ciascuno di questi cicli assume al massimon valori.
Esempio
Considerando il seguente albero, il costo è 2,80, anche se questo non è un risultato ottimale.
Nodo | Profondità | Probabilità | Contributo |
---|---|---|---|
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 |
Per ottenere una soluzione ottimale, utilizzando l'algoritmo discusso in questo capitolo, vengono generate le seguenti tabelle.
Nelle tabelle seguenti, l'indice di colonna è i e l'indice di riga è 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 |
radice | 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 |
Da queste tabelle è possibile formare l'albero ottimale.
Esistono diversi tipi di heap, tuttavia in questo capitolo discuteremo di heap binari. UNbinary heapè una struttura dati, simile a un albero binario completo. La struttura dei dati dell'heap obbedisce alle proprietà di ordinamento discusse di seguito. In genere, un heap è rappresentato da un array. In questo capitolo, rappresentiamo un mucchio diH.
Poiché gli elementi di un heap sono archiviati in un array, considerando l'indice iniziale come 1, la posizione del nodo padre di ith elemento può essere trovato a ⌊ i/2 ⌋. Figlio sinistro e figlio destro diith il nodo è in posizione 2i e 2i + 1.
Un heap binario può essere ulteriormente classificato come file max-heap o a min-heap in base alla proprietà dell'ordine.
Max-Heap
In questo heap, il valore della chiave di un nodo è maggiore o uguale al valore della chiave del figlio più alto.
Quindi, H[Parent(i)] ≥ H[i]
Min-Heap
In mean-heap, il valore della chiave di un nodo è minore o uguale al valore della chiave del figlio più basso.
Quindi, H[Parent(i)] ≤ H[i]
In questo contesto, le operazioni di base sono mostrate di seguito rispetto a Max-Heap. L'inserimento e la cancellazione di elementi in e da heap richiedono una riorganizzazione degli elementi. Quindi,Heapify la funzione deve essere chiamata.
Rappresentazione di array
Un albero binario completo può essere rappresentato da un array, memorizzando i suoi elementi utilizzando l'attraversamento dell'ordine dei livelli.
Consideriamo un heap (come mostrato di seguito) che sarà rappresentato da un array H.
Considerando l'indice di partenza come 0, utilizzando l'attraversamento dell'ordine dei livelli, gli elementi vengono mantenuti in un array come segue.
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
elements | 70 | 30 | 50 | 12 | 20 | 35 | 25 | 4 | 8 | ... |
In questo contesto, le operazioni sull'heap vengono rappresentate rispetto a Max-Heap.
Per trovare l'indice del genitore di un elemento in index i, il seguente algoritmo Parent (numbers[], i) si usa.
Algorithm: Parent (numbers[], i)
if i == 1
return NULL
else
[i / 2]
L'indice del figlio sinistro di un elemento in index i può essere trovato utilizzando il seguente algoritmo, Left-Child (numbers[], i).
Algorithm: Left-Child (numbers[], i)
If 2 * i ≤ heapsize
return [2 * i]
else
return NULL
L'indice del figlio destro di un elemento in index i può essere trovato utilizzando il seguente algoritmo, Right-Child(numbers[], i).
Algorithm: Right-Child (numbers[], i)
if 2 * i < heapsize
return [2 * i + 1]
else
return NULL
Per inserire un elemento in un heap, il nuovo elemento viene inizialmente aggiunto alla fine dell'heap come ultimo elemento dell'array.
After inserting this element, heap property may be violated, hence the heap property is repaired by comparing the added element with its parent and moving the added element up a level, swapping positions with the parent. This process is called percolation up.
The comparison is repeated until the parent is larger than or equal to the percolating element.
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)
Analysis
Initially, an element is being added at the end of the array. If it violates the heap property, the element is exchanged with its parent. The height of the tree is log n. Maximum log n number of operations needs to be performed.
Hence, the complexity of this function is O(log n).
Example
Let us consider a max-heap, as shown below, where a new element 5 needs to be added.
Initially, 55 will be added at the end of this array.
After insertion, it violates the heap property. Hence, the element needs to swap with its parent. After swap, the heap looks like the following.
Again, the element violates the property of heap. Hence, it is swapped with its parent.
Now, we have to stop.
Heapify method rearranges the elements of an array where the left and right sub-tree of ith element obeys the heap property.
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)
When the provided array does not obey the heap property, Heap is built based on the following algorithm 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)
Extract method is used to extract the root element of a Heap. Following is the algorithm.
Algorithm: Heap-Extract-Max (numbers[])
max = numbers[1]
numbers[1] = numbers[heapsize]
heapsize = heapsize – 1
Max-Heapify (numbers[], 1)
return max
Example
Let us consider the same example discussed previously. Now we want to extract an element. This method will return the root element of the heap.
After deletion of the root element, the last element will be moved to the root position.
Now, Heapify function will be called. After Heapify, the following heap is generated.
Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.
This is the simplest technique among all sorting algorithms.
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]
Implementation
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;
}
}
Analysis
Here, the number of comparisons are
1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n2)
Clearly, the graph shows the n2 nature of the bubble sort.
In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided input elements are in sorted order or in reverse order or at random.
Memory Requirement
From the algorithm stated above, it is clear that bubble sort does not require extra memory.
Example
Unsorted list: |
|
1st iteration:
5 > 2 swap |
|
|||||||
5 > 1 swap |
|
|||||||
5 > 4 swap |
|
|||||||
5 > 3 swap |
|
|||||||
5 < 7 no swap |
|
|||||||
7 > 6 swap |
|
2nd iteration:
2 > 1 swap |
|
|||||||
2 < 4 no swap |
|
|||||||
4 > 3 swap |
|
|||||||
4 < 5 no swap |
|
|||||||
5 < 6 no swap |
|
There is no change in 3rd, 4th, 5th and 6th iteration.
Finally,
the sorted list is |
|
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(n2) time.
Example
Unsorted list: |
|
1st iteration:
Key = a[2] = 13
a[1] = 2 < 13
Swap, no swap |
|
2nd iteration:
Key = a[3] = 5
a[2] = 13 > 5
Swap 5 and 13 |
|
Next, a[1] = 2 < 13
Swap, no swap |
|
3rd iteration:
Key = a[4] = 18
a[3] = 13 < 18,
a[2] = 5 < 18,
a[1] = 2 < 18
Swap, no swap |
|
4th iteration:
Key = a[5] = 14
a[4] = 18 > 14
Swap 18 and 14 |
|
Next, a[3] = 13 < 14,
a[2] = 5 < 14,
a[1] = 2 < 14
So, no swap |
|
Finally,
the sorted list is |
|
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: |
|
1st iteration:
Smallest = 5
2 < 5, smallest = 2
1 < 2, smallest = 1
4 > 1, smallest = 1
3 > 1, smallest = 1
Swap 5 and 1 |
|
2nd iteration:
Smallest = 2
2 < 5, smallest = 2
2 < 4, smallest = 2
2 < 3, smallest = 2
No Swap |
|
3rd iteration:
Smallest = 5
4 < 5, smallest = 4
3 < 4, smallest = 3
Swap 5 and 3 |
|
4th iteration:
Smallest = 4
4 < 5, smallest = 4
No Swap |
|
Finally,
the sorted list is |
|
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(n2). 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
Analisi
Ogni chiave viene esaminata contemporaneamente per ogni cifra (o lettera se le chiavi sono alfabetiche) della chiave più lunga. Quindi, se la chiave più lunga ham cifre e ci sono n chiavi, radix sort ha ordine O(m.n).
Tuttavia, se guardiamo a questi due valori, la dimensione delle chiavi sarà relativamente piccola rispetto al numero di chiavi. Ad esempio, se abbiamo chiavi a sei cifre, potremmo avere un milione di record diversi.
Qui, vediamo che la dimensione delle chiavi non è significativa e questo algoritmo è di complessità lineare O(n).
Esempio
L'esempio seguente mostra come l'ordinamento Radix opera su un numero di sette cifre.
Ingresso | 1 ° Passo | 2 ° passaggio | 3 ° passaggio |
---|---|---|---|
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 |
Nell'esempio sopra, la prima colonna è l'input. Le colonne rimanenti mostrano l'elenco dopo ordinamenti successivi in posizione di cifre sempre più significative. Il codice per l'ordinamento Radix presuppone che ogni elemento in un arrayA di n elementi ha d cifre, dove cifra 1 è la cifra di ordine più basso e d è la cifra di ordine più alto.
Per capire la classe P e NP, per prima cosa dovremmo conoscere il modello computazionale. Quindi, in questo capitolo discuteremo due importanti modelli computazionali.
Calcolo deterministico e classe P
Macchina di Turing deterministica
Uno di questi modelli è la macchina di Turing deterministica a nastro singolo. Questa macchina è composta da un controllo a stati finiti, una testina di lettura-scrittura e un nastro a due vie con sequenza infinita.
Di seguito è riportato il diagramma schematico di una macchina di Turing deterministica a nastro singolo.
Un programma per una macchina di Turing deterministica specifica le seguenti informazioni:
- Un insieme finito di simboli del nastro (simboli di input e un simbolo vuoto)
- Un insieme finito di stati
- Una funzione di transizione
Nell'analisi algoritmica, se un problema è risolvibile in tempo polinomiale da una macchina di Turing deterministica a nastro, il problema appartiene alla classe P.
Calcolo non deterministico e classe NP
Macchina di Turing non deterministica
Per risolvere il problema computazionale, un altro modello è la macchina di Turing non deterministica (NDTM). La struttura di NDTM è simile a DTM, tuttavia qui abbiamo un modulo aggiuntivo noto come modulo di ipotesi, che è associato a una testina di sola scrittura.
Di seguito è riportato il diagramma schematico.
Se il problema è risolvibile in tempo polinomiale da una macchina di Turing non deterministica, il problema appartiene alla classe NP.
In un grafo non orientato, a cliqueè un sottografo completo del grafico dato. Il sottografo completo significa che tutti i vertici di questo sottografo sono collegati a tutti gli altri vertici di questo sottografo.
Il problema Max-Clique è il problema computazionale di trovare la massima clique del grafico. Max clique viene utilizzato in molti problemi del mondo reale.
Consideriamo un'applicazione di social networking, in cui i vertici rappresentano il profilo delle persone e i bordi rappresentano la conoscenza reciproca in un grafico. In questo grafico, una cricca rappresenta un sottoinsieme di persone che si conoscono tutte.
Per trovare una cricca massima, è possibile ispezionare sistematicamente tutti i sottoinsiemi, ma questo tipo di ricerca a forza bruta richiede troppo tempo per le reti che comprendono più di poche dozzine di vertici.
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
Analisi
Il problema di Max-Clique è un algoritmo non deterministico. In questo algoritmo, proviamo prima a determinare un insieme dik vertici distinti e quindi proviamo a verificare se questi vertici formano un grafo completo.
Non esiste un algoritmo deterministico temporale polinomiale per risolvere questo problema. Questo problema è NP-Complete.
Esempio
Dai un'occhiata al grafico seguente. Qui, il sottografo contenente i vertici 2, 3, 4 e 6 forma un grafo completo. Quindi, questo sottografo è un fileclique. Poiché questo è il sottografo completo massimo del grafico fornito, è un file4-Clique.
Una copertura del vertice di un grafo non orientato G = (V, E) è un sottoinsieme di vertici V' ⊆ V tale che se bordo (u, v) è un vantaggio di G, allora neanche u in V o v in V' o entrambi.
Trova una copertura del vertice della dimensione massima in un dato grafo non orientato. Questo vertexcover ottimale è la versione di ottimizzazione di un problema NP-completo. Tuttavia, non è troppo difficile trovare una copertura del vertice che sia quasi ottimale.
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
Esempio
L'insieme dei bordi del grafico dato è -
{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}
Ora, iniziamo selezionando un arco arbitrario (1,6). Eliminiamo tutti i bordi, che sono incidenti al vertice 1 o 6 e aggiungiamo il bordo (1,6) alla copertura.
Nel passaggio successivo, abbiamo scelto un altro bordo (2,3) a caso
Ora selezioniamo un altro bordo (4,7).
Selezioniamo un altro bordo (8,5).
Quindi, la copertura del vertice di questo grafico è {1,2,4,5}.
Analisi
È facile vedere che il tempo di esecuzione di questo algoritmo è O(V + E), utilizzando l'elenco di adiacenza per rappresentare E'.
In Informatica, molti problemi vengono risolti laddove l'obiettivo è massimizzare o minimizzare alcuni valori, mentre in altri problemi si cerca di scoprire se esiste o meno una soluzione. Quindi, i problemi possono essere classificati come segue:
Problema di ottimizzazione
I problemi di ottimizzazione sono quelli per i quali l'obiettivo è massimizzare o minimizzare alcuni valori. Per esempio,
Trovare il numero minimo di colori necessari per colorare un dato grafico.
Trovare il percorso più breve tra due vertici in un grafo.
Problema decisionale
Esistono molti problemi per i quali la risposta è Sì o No. Questi tipi di problemi sono noti come decision problems. Per esempio,
Se un dato grafico può essere colorato solo con 4 colori.
Trovare il ciclo hamiltoniano in un grafo non è un problema decisionale, mentre controllare un grafo sia hamiltoniano o meno è un problema decisionale.
Cos'è la lingua?
Ogni problema decisionale può avere solo due risposte, sì o no. Quindi, un problema decisionale può appartenere a una lingua se fornisce una risposta "sì" per un input specifico. Una lingua è la totalità degli input per i quali la risposta è Sì. La maggior parte degli algoritmi discussi nei capitoli precedenti lo sonopolynomial time algorithms.
Per la dimensione di input n, se la complessità temporale nel caso peggiore di un algoritmo è O(nk), dove k è una costante, l'algoritmo è un algoritmo temporale polinomiale.
Algoritmi come Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, ecc. Vengono eseguiti in tempo polinomiale. Tuttavia ci sono molti problemi, come il venditore in viaggio, la colorazione ottimale del grafo, i cicli hamiltoniani, la ricerca del percorso più lungo in un grafo e il soddisfacimento di una formula booleana, per la quale non sono noti algoritmi di tempo polinomiale. Questi problemi appartengono a un'interessante classe di problemi, denominataNP-Complete problemi, il cui stato è sconosciuto.
In questo contesto, possiamo classificare i problemi come segue:
Classe P.
La classe P è costituita da quei problemi che sono risolvibili in tempo polinomiale, cioè questi problemi possono essere risolti nel tempo O(nk) nel peggiore dei casi, dove k è costante.
Questi problemi sono chiamati tractable, mentre altri vengono chiamati intractable or superpolynomial.
Formalmente, un algoritmo è un algoritmo temporale polinomiale, se esiste un polinomio p(n) in modo tale che l'algoritmo possa risolvere qualsiasi istanza di dimensione n in un tempo O(p(n)).
Problema che richiede Ω(n50) il tempo per risolvere sono essenzialmente intrattabili per i grandi n. L'algoritmo del tempo polinomiale più noto viene eseguito nel tempoO(nk) per un valore piuttosto basso di k.
Il vantaggio nel considerare la classe degli algoritmi tempo-polinomiali è che tutto ragionevole deterministic single processor model of computation possono essere simulati l'uno sull'altro con al massimo un polinomio slow-d
Classe NP
La classe NP è costituita da quei problemi verificabili in tempo polinomiale. NP è la classe di problemi decisionali per i quali è facile verificare la correttezza di una risposta asserita, con l'ausilio di poche informazioni extra. Quindi, non stiamo chiedendo un modo per trovare una soluzione, ma solo per verificare che una presunta soluzione sia davvero corretta.
Ogni problema in questa classe può essere risolto in tempo esponenziale utilizzando una ricerca esaustiva.
P contro NP
Ogni problema decisionale risolvibile da un algoritmo tempo polinomiale deterministico è risolvibile anche da un algoritmo tempo polinomiale non deterministico.
Tutti i problemi in P possono essere risolti con algoritmi di tempo polinomiale, mentre tutti i problemi in NP - P sono intrattabili.
Non è noto se P = NP. Tuttavia, molti problemi sono noti in NP con la proprietà che se appartengono a P, allora si può dimostrare che P = NP.
Se P ≠ NP, ci sono problemi in NP che non sono né in P né in NP-Complete.
Il problema appartiene alla classe Pse è facile trovare una soluzione al problema. Il problema appartiene aNP, se è facile controllare una soluzione che potrebbe essere stata molto noiosa da trovare.
Stephen Cook ha presentato quattro teoremi nel suo articolo "The Complexity of Theorem Proving Procedures". Questi teoremi sono indicati di seguito. Comprendiamo che in questo capitolo vengono utilizzati molti termini sconosciuti, ma non abbiamo alcun margine per discutere tutto in dettaglio.
Di seguito sono riportati i quattro teoremi di Stephen Cook:
Teorema-1
Se un set S di stringhe è accettato da qualche macchina di Turing non deterministica entro un tempo polinomiale, quindi S è P-riducibile a {DNF tautologies}.
Teorema-2
I seguenti insiemi sono P-riducibili l'uno all'altro in coppia (e quindi ciascuno ha lo stesso grado di difficoltà polinomiale): {tautologies}, {DNF tautologies}, D3, {sub-graph pair}.
Teorema-3
Per ogni TQ(k) di tipo Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ è illimitato
C'è un TQ(k) di tipo Q tale che $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$
Teorema-4
Se l'insieme S di stringhe viene accettato da una macchina non deterministica entro il tempo T(n) = 2n, e se TQ(k) è una funzione di tipo onesta (cioè numerabile in tempo reale) Q, allora c'è una costante K, così S può essere riconosciuto da una macchina deterministica nel tempo TQ(K8n).
In primo luogo, ha sottolineato il significato della riducibilità del tempo polinomiale. Significa che se abbiamo una riduzione del tempo polinomiale da un problema a un altro, questo garantisce che qualsiasi algoritmo temporale polinomiale del secondo problema possa essere convertito in un algoritmo temporale polinomiale corrispondente per il primo problema.
In secondo luogo, ha focalizzato l'attenzione sulla classe NP dei problemi decisionali che possono essere risolti in tempo polinomiale da un computer non deterministico. La maggior parte dei problemi intrattabili appartengono a questa classe, NP.
Terzo, ha dimostrato che un particolare problema in NP ha la proprietà che ogni altro problema in NP può essere ridotto polinomialmente ad esso. Se il problema di soddisfacibilità può essere risolto con un algoritmo di tempo polinomiale, allora ogni problema in NP può essere risolto anche in tempo polinomiale. Se un problema in NP è intrattabile, il problema di soddisfacibilità deve essere intrattabile. Pertanto, il problema della soddisfacibilità è il problema più difficile in NP.
Quarto, Cook ha suggerito che altri problemi in NP potrebbero condividere con il problema di soddisfacibilità questa proprietà di essere il membro più difficile di NP.
Un problema è nella classe NPC se è in NP ed è come hardcome qualsiasi problema in NP. Un problema èNP-hard se tutti i problemi in NP sono riducibili in tempo polinomiale ad esso, anche se potrebbe non essere in NP stesso.
Se esiste un algoritmo temporale polinomiale per uno qualsiasi di questi problemi, tutti i problemi in NP sarebbero risolvibili in tempo polinomiale. Questi problemi sono chiamatiNP-complete. Il fenomeno della NP-completezza è importante sia per ragioni teoriche che pratiche.
Definizione di NP-completezza
Una lingua B è NP-complete se soddisfa due condizioni
B è in NP
Ogni A in NP è il tempo polinomiale riducibile a B.
Se una lingua soddisfa la seconda proprietà, ma non necessariamente la prima, la lingua B è conosciuto come NP-Hard. Informalmente, un problema di ricercaB è NP-Hard se ce ne sono alcuni NP-Complete problema A che Turing riduce a B.
Il problema in NP-Hard non può essere risolto in tempo polinomiale, fino a quando P = NP. Se si dimostra che un problema è NPC, non è necessario perdere tempo a cercare un algoritmo efficiente. Invece, possiamo concentrarci sull'algoritmo di approssimazione del progetto.
Problemi NP-Complete
Di seguito sono riportati alcuni problemi NP-Complete, per i quali non è noto alcun algoritmo temporale polinomiale.
- Determinare se un grafico ha un ciclo hamiltoniano
- Determinare se una formula booleana è soddisfacente, ecc.
Problemi NP-Hard
I seguenti problemi sono NP-Hard
- Il problema della soddisfacibilità dei circuiti
- Imposta copertina
- Vertex Cover
- Problema del commesso viaggiatore
In questo contesto, ora discuteremo che TSP è NP-Complete
TSP è NP-Complete
Il problema del venditore ambulante consiste in un venditore e un insieme di città. Il venditore deve visitare ciascuna delle città partendo da una certa e tornando nella stessa città. La sfida del problema è che il venditore ambulante vuole ridurre al minimo la durata totale del viaggio
Prova
Provare TSP is NP-Complete, prima dobbiamo dimostrarlo TSP belongs to NP. In TSP, troviamo un tour e controlliamo che il tour contenga ogni vertice una volta. Quindi viene calcolato il costo totale dei bordi del tour. Infine, controlliamo se il costo è minimo. Questo può essere completato in tempo polinomiale. CosìTSP belongs to NP.
In secondo luogo, dobbiamo dimostrarlo TSP is NP-hard. Per dimostrarlo, un modo è dimostrarloHamiltonian cycle ≤p TSP (come sappiamo che il problema del ciclo hamiltoniano è NPcompleto).
Assumere G = (V, E) per essere un'istanza del ciclo hamiltoniano.
Quindi, viene costruita un'istanza di TSP. Creiamo il grafico completoG' = (V, E'), dove
$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$
Pertanto, la funzione di costo è definita come segue:
$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$
Supponiamo ora che sia un ciclo hamiltoniano h esiste in G. È chiaro che il costo di ogni bordo inh è 0 in G' come ogni bordo appartiene E. Perciò,h ha un costo di 0 in G'. Quindi, if graphG ha un ciclo hamiltoniano, quindi un grafico G' ha un tour di 0 costo.
Al contrario, lo assumiamo G' ha un tour h' di costo al massimo 0. Il costo dei bordi inE' siamo 0 e 1per definizione. Quindi, ogni bordo deve avere un costo di0 come il costo di h' è 0. Concludiamo quindi quelloh' contiene solo bordi in E.
Lo abbiamo così dimostrato G ha un ciclo hamiltoniano, se e solo se G' ha un giro di costo al massimo 0. TSP è NP-completo.
Gli algoritmi discussi nei capitoli precedenti vengono eseguiti in modo sistematico. Per raggiungere l'obiettivo, è necessario memorizzare uno o più percorsi esplorati in precedenza verso la soluzione per trovare la soluzione ottimale.
Per molti problemi, il percorso verso l'obiettivo è irrilevante. Ad esempio, nel problema N-Queens, non abbiamo bisogno di preoccuparci della configurazione finale delle regine e dell'ordine in cui le regine vengono aggiunte.
Arrampicata in collina
Hill Climbing è una tecnica per risolvere alcuni problemi di ottimizzazione. In questa tecnica, iniziamo con una soluzione subottimale e la soluzione viene migliorata ripetutamente fino a massimizzare alcune condizioni.
L'idea di partire con una soluzione subottimale è paragonata a partire dalla base della collina, migliorare la soluzione è paragonata a camminare su per la collina, e infine massimizzare alcune condizioni è paragonata al raggiungimento della cima della collina.
Quindi, la tecnica dell'arrampicata in collina può essere considerata come le seguenti fasi:
- Costruire una soluzione subottimale obbedendo ai vincoli del problema
- Migliorare la soluzione passo dopo passo
- Migliorare la soluzione fino a quando non sono più possibili miglioramenti
La tecnica Hill Climbing viene utilizzata principalmente per risolvere problemi computazionalmente complessi. Guarda solo lo stato attuale e lo stato futuro immediato. Quindi, questa tecnica è efficiente in termini di memoria in quanto non mantiene un albero di ricerca.
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
Miglioramento iterativo
Nel metodo di miglioramento iterativo, la soluzione ottimale si ottiene facendo progressi verso una soluzione ottimale in ogni iterazione. Tuttavia, questa tecnica può incontrare i massimi locali. In questa situazione, non esiste uno stato vicino per una soluzione migliore.
Questo problema può essere evitato con metodi diversi. Uno di questi metodi è la ricottura simulata.
Riavvio casuale
Questo è un altro metodo per risolvere il problema dell'ottimo locale. Questa tecnica conduce una serie di ricerche. Ogni volta parte da uno stato iniziale generato casualmente. Quindi, la soluzione ottimale o quasi ottimale può essere ottenuta confrontando le soluzioni delle ricerche eseguite.
Problemi di tecnica di arrampicata in collina
Maxima locale
Se l'euristica non è convessa, Hill Climbing può convergere ai massimi locali, invece che ai massimi globali.
Creste e vicoli
Se la funzione target crea una cresta stretta, lo scalatore può solo salire la cresta o scendere il vicolo a zig-zag. In questo scenario, lo scalatore deve compiere passi molto piccoli che richiedono più tempo per raggiungere l'obiettivo.
Altopiano
Si verifica un plateau quando lo spazio di ricerca è piatto o sufficientemente piatto che il valore restituito dalla funzione di destinazione è indistinguibile dal valore restituito per le regioni vicine, a causa della precisione utilizzata dalla macchina per rappresentarne il valore.
Complessità della tecnica di arrampicata in collina
Questa tecnica non soffre di problemi legati allo spazio, poiché guarda solo allo stato attuale. I percorsi esplorati in precedenza non vengono memorizzati.
Per la maggior parte dei problemi nella tecnica dell'arrampicata in collina con riavvio casuale, è possibile ottenere una soluzione ottimale in tempo polinomiale. Tuttavia, per i problemi NP-Complete, il tempo di calcolo può essere esponenziale in base al numero di massimi locali.
Applicazioni di Hill Climbing Technique
La tecnica Hill Climbing può essere utilizzata per risolvere molti problemi, dove lo stato corrente consente una funzione di valutazione accurata, come il flusso di rete, il problema del venditore in viaggio, il problema delle 8 regine, la progettazione del circuito integrato, ecc.
L'arrampicata in collina viene utilizzata anche nei metodi di apprendimento induttivo. Questa tecnica viene utilizzata nella robotica per il coordinamento tra più robot in una squadra. Ci sono molti altri problemi in cui viene utilizzata questa tecnica.
Esempio
Questa tecnica può essere applicata per risolvere il problema del venditore ambulante. Per prima cosa viene determinata una soluzione iniziale che visita tutte le città esattamente una volta. Quindi, questa soluzione iniziale non è ottimale nella maggior parte dei casi. Anche questa soluzione può essere molto scarsa. L'algoritmo Hill Climbing inizia con una tale soluzione iniziale e apporta miglioramenti ad essa in modo iterativo. Alla fine, è probabile che si ottenga un percorso molto più breve.