Algoritmi e Strutture Dati

• http://forums.civfanatics.com/showthread.php?t=426472
• https://harablog.wordpress.com/tag/pathfinding/
• https://en.wikipedia.org/wiki/Pathfinding
• https://en.wikipedia.org/wiki/Travelling_salesman_problem
• https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
• https://en.wikipedia.org/wiki/Shortest_path_problem#Unweighted_graphs
• http://www.sanfoundry.com/cpp-program-implement-nearest-neighbour-algorithm/ approximate solution for travelign salesamn
• http://gamedev.stackexchange.com/questions/83225/find-shortest-path-to-gather-items
• https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm best all shorterst paths n³
• All pairs in undirected unweighted:http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6EAF4418390EBF9851A03AED56F8713A?doi=10.1.1.67.5789&rep=rep1&type=pdf
• http://www.algolist.net/Data_structures/Graph/Internal_representation
• http://www.algolist.net/Data_structures/Graph/Internal_representation
• https://en.wikipedia.org/wiki/Dijkstra's_algorithm

For sparse graphs, that is, graphs with far fewer than |V|² edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. To perform decrease-key steps in a binary heap efficiently, it is necessary to use an auxiliary data structure that maps each vertex to its position in the heap, and to keep this structure up to date as the priority queue Q changes.

• http://www.seas.gwu.edu/~simhaweb/champalg/tsp/tsp.html

Sito Corso

Algoritmi e strutture dati. Demetrescu, Finocchi, Italiano

Programma

• Tabelle Hash
• Alberi e ABR
• Grafi
• Divite et Impera
• Programmazione Golosa
• Programmazione dinamica
• Backtracking

• Complessità Temporale (di cui si occuperà il corso)
• Complessità Spaziale

Istruzioni Elementari:

• Assegnamento
• Operazioni Aritmetiche Semplici
• Espressioni Booleane
• Accesso ad elementi di Array V[i]
• Lettura
• Scritture

Complessità asintotica \(n \to \infty\)

\(f(n)\) è \(O(g(n))\) se \[\exists c, n_0 > 0 \text{ tale che } \forall n > n_0, \quad 0 \leq f(n) \leq cg(n)\]

\(f(n) \in \Omega(g(x))\) se \[\exists c, n_0 > 0 | \forall n > n_0 ,\quad f(n) \geq c g(n) > 0\] \(f(n) \in \Theta (g(x))\) se \[\exists c_1, c_2, n_0 > 0 | \forall n > n_0,\quad c_1 g(n) \leq f(n) \leq c_2 g(n)\]

Istruzioni semplici

\(O(1)\)

Blocchi di istruzioni

\(f_1(n), f_2(n) \dots O(\max \{f_1(n), f_2(n) \dots \})\)

Costrutti selettivi

\(f_{\mbox{cond}} ,f_{\mbox{then}} ,f_{\mbox{else}}\) dobbiamo fare valutazioni di caso migliori e di caso peggiore. Non faremo analisi di caso medio.

cicli

while.

funzione

passaggio dei parametri

Alberi Strutture Gerarchice

Insieme di nodi ed un insieme di archi. A = <N, E>

Ogni nodo ha un solo padre, più figli.

Radice, unico nodo a non avere padri. foglia, nodo che non ha figli

profondità livello, numero di archi da attraversare da una radice per raggiungere il nodo. la profondità dell'albero è la profondità massima.

fratelli nodi che condividono lo stesso padre.

Albero d-ARIO numer massimo di figli che ogni nodo può avere. Max 2 sono alberi binari.

Un albero completo è uno in cui tutti i nodi hanno tutti i figli possibili, eccetto l'ultimo.

albero bilanciato : (caso binario) Per ogni nodo la profondità dell'albero sinistro meno la profondità di quello destro è al più 1.

Il numero di nodi massimo è n=2^liv - 1 Dato un numero di nodi la profondità minima è log2 n

class Albero {
    radice // contenuto della radice
    figlio(x); // può restituire un nodo o un albero
    padre; // albero
    foglia; // boolean
    nullo; // boolean
  }

Rappresentazioni indicizzate / collegate Indicizzate: Non fanno uso di puntatori, solo di array.

Vettore dei padri

ogni nodo è in un array e oltre il suo contenuto ha un indice corrispondente al nodo padre. accedere ad un figlio richiede una scansione lineare.

Vettore Posizionale

La prima cella contiene sempre la radice. Poi c'è lo spazio per figli sinistri e quelli destri. per accedere ad un figlio: P[d*v + i] d per d-Ario. Svantaggi: L'array deve essere grande abbastanza per contenere un'albero completo.

Collegate

• ogni nodo contiene info più un numero preciso di puntatori. Oppure una lista di puntatori per rappresentare alberi generici.
• due puntatori per ogni nodo, un puntatore punta al primo figlio, l'altro puntatore al fratello

Visitare gli alberi Le prime 3 vengono chiamate DFS depth first search, l'ultima BFS Breadth

preordine

prima valuto il nodo poi vado a visitare gli altri nodi.

postordine

valuto solo quando non posso scendere più

(no term)

simmetrica

per livelli

Complicata per ricorsione

// Esempio DFS
visitaDFS (Albero A) {
  if (A.nullo())
    return;
  valuta(A.radice());
  A.figli.perogni(f).visitaDFS(f);
}

bool cerca(Albero A, int x) {
  if (A.nullo())
    return false;
  if (A.radice() == x) return true;
  return cerca(A.figlio(sin), x) or cerca(A.figlio(des), x);
}

Costa O(n) perché è praticamente una ricerca lineare su alberi.

Per velocizzare dobbiamo "ordinare" devo vedere l'albero. A sinistra mettiamo tutto quello che è minore della radice e a destra quello che è maggiore. lo chiamiamo Albero binario di Ricerca

bool cerca(Abr A, int x) {
  if (A.nullo()) reutrn false;
  if (A.radice() == x) return true;
  if (x < A.radice()) return cerca(A.figlio(sin), x);
  return cerca(A.figlio(des), x);
}

Possiamo inturie la complessità perché è uguale alla profondità (media) dell'albero) L'albero però deve essere bilanciato (cioè ad ogni passo ne scarto più o meno la metà)

Come costruisco un'albero di ricerca bilanciato?

Mi costruisco un array ordinato dei valori: 3 5 7 15 22 34 40 42 La radice deve prendere il valore mediano.

. Ex: Dato un array ordinato costruire l'albero di ricerca bilanciato. (mi costerà O(n))

class ABR {
contenuto : albero;
interfaccia:
  ins(valore);
  cerca(valore x);
  rimuovi(valore x);
private:
  bilanciato(); // controllo ogni tanto dopo l'inserimento e la rimozione
  bilancia();
}

Posso costruire una funziona che mi controlla la profondità oltre la bilanciatezza.

bool bilanciatoProfondo(Albero A, int &p) {
  if (A.nullo()) {
    p = 0;
    return true;
  }
  int p1, p2;
  bool b1=bilanciatoProfondo(A.figlio(sin), p1);
  bool b2=bilanciatoProfondo(A.figlio(des), p2);
  p = max(p1, p2) + 1;
  return b1 and b2 and (abs(p1-p2) <= 1);
}

. Ex: Implementare la ins

preordiene postordine infissa , per livelli pre: valuta radice, pre figliodes, pre figlio sin post: post figliosin, post figliodes, valuta radice inf: inf figliosin, valuta radice, inf figliodest

// Es. modificare questa funzione per capire a che livello dell'albero siamo
  void visita_per_livelli(AlberoB<T> A, list<T>& l) {
    if(!A.nullo()) {
      coda<AlberoB<T> > C;
      C.in_coda(A);
      int level = 0;
      int thisLevel = 1;
      int nextLevel = 0;
      while (!C.vuota()) {
        AlberoB<T> at =C.fuori_coda(); // = pop
        l.push_back(at.valore());
        if (!at.figlio(sin).nullo()) {
          C.in_coda(at.figlio(sin));
          nextLevel++;
        }
        if (!at.figlio(des).nullo()) {
          C.in_coda(at.figlio(des));
          nextLevel++;
        }
        thisLevel--;
        if (thisLevel == 0) {
          level++;
          thisLevel = nextLevel;
          nextLevel = 0;
        }
      }
    }
  }

Rappresentazione Albero: [puntatore, valore, puntatore]

template<class T>
class SNodo {
public:
  T vinfo; // valore informativo
  snodo<T> *ppadre, *pfiglio[2];
  SNodo(const T& inf) : vinfo(inf) {
    ppadre = pfiglio[sin] = pfiglio[des] = 0
      }
  ~SNodo() {
    delete pfiglio[sin];
    delete pfiglio[des];
  }
};

template<class T>
class AlberoB {
protected:
  SNodo<T> *pradice;
public:
  AlberoB() : pradice(0) {}
  AlberoB(const T& a) {
    pradice = new SNodo<T>(a);
  }
  void ins_figlio(direzione d, AlberoB<T> &AC) {
    if(!AC.nullo()) {
      pradice ->pfiglio[d] = AC.padre;
      AC.pradice->ppadre = pradice;
    }
  }
  // ci sono anche elimina_figlio, cambia radice
  AlberoB<T> figlio(direzione d) const {
    AlberoB<T> Ac();
    Ac.pradice = pradice->pfiglio[d];
    return Ac;
  }
}

Grafi G=<N,A> orientati - non orientati (bidirezionali?)

con n nodi il numero massimo di archi è circa n²

Alcuni nodi possono essere isolati, alcuni possono essere raggiunti ma non si può uscire da essi

nodi adiacenti raggiungibili attraverso un arco diretto

per quelli orintati abbiamo: grado di entrata, grado di uscita (numero di archi che escono o entrano da un nodo) per qulli non orientati esiste solamente il grado.

cammino una sequnza di archi che hanno in comune un nodo <1,2><2,4>, o <1,2><2,4><4,5> (anche <1,2> è un cammino, è composto però da un solo arco) il cammino chiuso è un ciclo. i grafi che contengono dei cicli vengono detti ciclici.

Rappresentazione un array di nodi, indicizzato e poi gli archi con matrici (matrice di adiacenza) o con una lista di nodi adiacenti ad ogni nodo (liste di adiacenza) La matrice di adiacenza conviene per grafi densi.

Struttura delle classi: GRafo , GrafoOr, GrafoNoOr, ListeAd, MatrAd, GrafOrM, GrafOrLista (che fa uso di GrafoOr e ListeAd)

Grafo G(n), funzioni: G(i,j, bool) / bool per conoscere l'orientamento bool G(i,j) / ritorna se esite l'arco.

vettore<int> n_adiacenti_per_nodo(Grafo G) {
  vettore<int> gradi(0,G.numero_nodi());
  for (int i = 1; i <= G.numero_nodi(), ++i) {
    for (int j = 1; j <= G.numero_nodi(), ++j) {
      if (G(i,j)) gradi[i]++;
    }
  }
  return gradi;
}

come aggiungere un contenuto informativo agli archi? Non vado a modificare le liste o matrici di adiacenza, aggiungo il contenuto da un'altra parte.

Visite dei grafi, se dobbiamo stampare tutti i nodi arbitrariamente non ci sono problemi. in caso dobbiamo partire da un particolare nodo? Abbiamo DFS(in profondità) , DBS (ampiezza).

Problemi, possono restituire:

• True/false
• la soluzioni
• una delle soluzioni
• la migliore soluzione

Le tecniche per risolvere questi problemi pososno essere diversi.

Spazio di ricerca Per esempio, nell'ordinamento sono tutti i possibili ordinamenti di un array. Dobbiamo cercare di restringerlo quando possibile.

Merge sort da fare: merge sort, quick sort, radix sort, programmazione golosa

della golosa: problema della bisaccia e altro.

Spazio soluzioni numeroso, tra le tante è difficile trovarne almeno una.

Esempio: Colorazione di una mappa.

supponiamo di avere una cartina geografica con 6 nazioni. Assegnare un colore a ciascuna nazione in modo che due nazioni confinanti non abbiano lo stesso colore.

N-colorabilità: se ho a disposizione n colori, posso risolvere il problema? Classicamente usiamo 3 colori.

Prova a colorare nazione per nazione, se rimani bloccato, torna indietro.

Il caso peggiore è sempre quello della forza bruta, ma in media è molto più veloce.

Requisiti:

• lo spazio delle soluzioni deve essere finito
• la soluzione deve essere rappresentata come una sequenza di soluzioni parziali.
• la dimensione massima della soluzione è nota a priori.
• il valore di ciascuna sottosoluzione deve appartenere ad un insieme finito di valori.

x: dominio delle sottosoluzioni ∈ [minval, maxval]

list sol = {}
bool solve(sol) {
    x = minval;
    while(x<=maxval) {
        if (canAdd(x,sol)) {
            add(x, sol); 
            if (isComplete(sol))
                return true; // ho trovato una soluzione
            else if (solve(sol)) return true;
            else { remove (x,sol); x=next(x);}
        } else {
            x = next(x);
        }
    }
    return false;
}