Note de curs, clasele 9-10, 22 februarie 2013

Tema

Discuții rezolvări la teme:

• megascoala: Floyd-Warshall O(n³) + toate combinațiile O(n³).
• traseu1: Dijkstra modificat, în loc de sumă calculăm maximul O(n²).
• grafxy: Dijkstra modificat, pornirea este din mai multe noduri o dată. E necesară implementarea O((M+N) log N) și reprezentarea cu liste de adiacență.

Lecție

Backtracking

• Algoritmul general, implementări recursive versus nerecursive, ideea că orice program recursiv poate fi scris nerecursiv folosind o stivă.
• Optimizări de backtracking: pe cît posibil alegerea următoarei opțiuni în O(1). Exemplu la problema damelor, folosirea vectorilor de linii, coloane și diagonale.
• Euristici:
  • un backtracking informat va fi mai eficient decît unul neinformat; optimizările sînt dependente de problemă; există unele idei generale.
  • alegerea locului cu număr minim de posibilități (early pruning); exemple:
    • problema calului, selecția în ordinea inversă a numărului posibil de mutări
  • alegerea greedy (drum hamiltonian)
  • funcție de verificare dacă soluția parțială mai are șanse să ducă la o soluție
    • se obține prin relaxarea unora din condiții
    • drum hamiltonian: soluția parțială să fie mai mică decît cel mai bun drum găsit pînă acum
    • drum hamiltonian: dacă soluția parțială plus numărul de arce rămase ori costul minim al unui arc este mai mare ca soluția optimă găsită pînă acum, ne putem opri
• Omorîrea backtrackingului. Tehnică folositoare și atunci cînd vreți să măsurați cît timp ruleaza programul vostru:

#include <sys/time.h>

#define MAX_VAL 990

int startT;
int stop;

void bkt(...) {
  struct timeval tv;

  if ( stop )
    return;
  gettimeofday(&tv, NULL);
  if (  tv.tv_sec * 1000 + tv.tv_usec / 1000 - startT > MIN_VAL ) {
    stop = 1;
    return;
  }
  for(...) // generare mutari urmatoare
}

int main() {
  struct timeval tv;

  gettimeofday(&tv, NULL);
  startT = tv.tv_sec * 1000 + tv.tv_usec / 1000; // pastram milisecunde
  stop = 0;
...
  return 0;
}

Operațiuni pe biți

• Operatorii pe biți: &, |, ~, ^, <<, >>. Atenție: shift este mult mai rapid decît împărțirea! Vezi tabelul din lecția 14, clasele VI/VII/VIII.
• Extragerea unui bit. Ideea de mască. Constante hexa în C (care încep cu 0x, ex: 0xFF12).
• Setarea unui bit pe 0.
• Setarea unui bit pe 1.
• Compunerea mai multor valori într-un întreg. Aplicație: reprezentarea zecimal împachetat.
• Aplicație: operații pe mulțimi mari, reuniune, intersecție, etc. De menționat că reuniunea și intersecția se fac mai rapid, deoarece reunim cîte 32 (sau 64) elemente deodată.
• Codul Gray

Teme

La alegere, pentru viitor:

• implementați un backtracking cu euristică și omorît, ca să vă faceți mîna, cum ar fi drumul hamiltonian într-un graf (în particular această problemă are o soluție exponențială mai rapidă decît backtracking-ul, prin programare dinamică).
• operațiuni pe vector de biți:
  • int get(int i, unsigned int v[]) returnează valoarea bitului pe poziția i.
  • void set(int i, unsigned int v[], int e) setează elementul pe poziția i la valoarea e, unde e este 0 sau 1.
• se dă o permutare, a cîta este în ordine lexicografică?
• se dă un număr între 0 și n!-1, ce permutare reprezintă el în ordine lexicografică?
• implementați permutările sub forma unei funcții care la fiecare apel ne returnează încă o permutare (foarte util în anumite situații). Aplicație directă a problemei anterioare.
• ultimele trei probleme, dar pentru combinări.