Zusammenfassungen

Edit Distance

La traccia del problema è la seguente:

Date due stringhe x e y, la edit distance tra x e y è definita come il numero minimo di edit operation da effettuare per trasformare x in y.

ESEMPIO: stringa x "astro", stringa y "arto", editDistance(x, y) = 2

Le edit operation sono:

• INSERTION: inserire un simbolo in una qualunque posizione;
• DELETION: cancellare un simbolo da una qualunque posizione;
• SUBSTITUTION: sostituire un simbolo c con un simbolo c'.

I sottoproblemi sono rappresentati dalla edit distance tra i prefissi delle stringhe. Con il bottom-up risolviamo prima i sottoproblemi semplici (la edit distance tra due simboli), per poi usarli nella risoluzione dei sottoproblemi più difficili (la edit distance tra due prefissi).

Come definiamo le relazioni tra i sottoproblemi (come uso la soluzione di un sottoproblema per un altro?)? Siano i (risp. j) una posizione nelle stringhe x (risp. y), allora:

#include <iostream>
#include <string>

unsigned min(unsigned src1, unsigned src2, unsigned src3) {
  if(src1 > src2) {
    if(src2 > src3) {
      return src3;
    } else if(src2 < src3) {
      return src2;
    }
  } else if(src1 < src2) {
    if(src1 > src3) {
      return src3;
    } else if(src1 < src3) {
      return src1;
    }
  }
}

unsigned editDistance(const std::string & x, const std::string& y) {
  // d è una matrice x.size() + 1 * y.size() + 1
  unsigned** d = new unsigned*[x.size() + 1];
  for(unsigned i = 0; i <= x.size(); ++i)
    d[i] = new unsigned[y.size() + 1];

  // numero di operazioni per trasformare la stringa vuota in x
  // esempio: d[4][0] = 4 -> ho bisogno di 4 edit operation per trasformare
  // la stringa vuota in x (inserimento di 4 simboli)
  for(unsigned i = 0; i <= x.size(); ++i)
    d[i][0] = i;

  // numero di operazioni per trasformare la stringa vuota in y
  for(unsigned j = 0; j <= y.size(); ++j)
    d[0][j] = j;

  for(unsigned i = 1; i <= x.size(); ++i)
    for(unsigned j = 1; j <= y.size(); ++j) {
      int s = 0;
      if(x[i-1] != y[j-1])
        s = 1;

      d[i][j] = min(
        d[i-1][j] + 1,
        d[i][j-1] + 1,
        d[i-1][j-1] + s
      )
    }

  unsigned distance = d[x.size()][y.size()];

  for(unsigned i = 0; i <= x.size(); ++i)
    delete[] d[i];
  delete[] d;

  return distance;
}

int main() {
  unsigned d = editDistance("astro", "arto");
  std::cout<<"La edit distance tra astro e arto e' "<<d<<'\n';
  return 0;
}

DivCoins

La traccia del problema è la seguente:

Dato un sacchetto contenente n monete, dove ogni moneta ha un valore positivo, determinare la più equa divisione delle monete tra due persone.

Con equa divisione si intende la differenza tra la somma delle monete date alla prima persona e la somma delle monete date alla seconda persona deve essere la minima possibile (tra tutte le possibili divisioni).

ESEMPIO: {10, 4, 6, 3, 8, 2}, una equa divisione è {10, 6}, {8, 4, 3, 2} perché |16 - 17| = 1

I possibili approcci sono:

• BRUTEFORCE: provare tutte le possibili divisioni. Il punto positivo è soluzione ottima assicurata, il punto negativo è complessità temporale enorme.
• GREEDY: uno stage dell'algoritmo greedy sceglie se inserire o meno la monete corrente in una partizione e il criterio della scelta è locale (si basa solo sulle monete inserite fino a questo punto). Il punto positivo è complessità lineare, il punto negativo è soluzione ottima non assicurata.
• ALTRI APPROCCI?
  • Variazione del problema subset sum (dato un insieme I di numeri positivi e una soglia T, stabilire se esiste un sottoinsieme I' tale che sum(I') ≤ T e sia la più grande possibile);
  • Variazione del problema coin change (dato un numero N e un insieme di monete M, in quanti modi possiamo ottenere N usando le monete di M?)

Dobbiamo affrontare due fasi:

• FASE 1, determinare tutte le possibili somme: quali sono le possibili somme che possiamo fare con tutte le monete? Enumerare tutte le possibili somme in un modo intelligente.
• FASE 2, qual è la somma, tra tutte le possibili, che ci permette di ottenere la differenza minima? Manteniamo una variabile min indicante la differenza minima possibile (inizialmente = T, dove T è la somma di tutte le monete), e aggiorniamo min se troviamo una somma che ci permette di avere una differenza più piccola di min.