-BOLYAI Facultatea de Matematică şi Informatică...

FUNDAMENTELE

PROGRAMĂRII

Laura Dioşan

Metode de rezolvare a problemelor

Backtracking

UNIVERSITATEA BABEŞ-BOLYAI

Facultatea de Matematică şi Informatică

Conținut curs Introducere în procesul de dezvoltare software Programare procedurală Programare modulară Tipuri definite de utilizator Principii de dezvoltare a aplicațiilor soft Testarea și inspectarea programelor Recursivitate Complexitatea algoritmilor Metode de rezolvare a problemelor

Backtracking Divide et impera Programare dinamică Greedy

Algoritmi de căutare Algoritmi de sortare Recapitulare

Ianuarie, 2016 Fundamentele programării - tehnici de rezolvare a problemelor 2

Sumar

Rezolvarea problemelor

Tipologie

Tehnici

Divide et impera

Backtracking


Probleme

Tipologie

În funcție de structură

Care pot fi descompuse în sub-probleme

Căutarea unui element într-un vector

Care nu pot fi descompuse

Amplasarea reginelor pe o tablă de șah

În funcție de numărul de soluții

Cu o singură soluție

Sortarea unui vector

Cu mai multe soluții

Generarea permutărilor


http://1.bp.blogspot.com/_xOb625sShwI/TMeSe9pABKI/AAAAAAAAAUw/jG2N0OP6MXY/s1600/image001.gif

Probleme

Tipologie

În funcție de posibilitățile de rezolvare

Rezolvabile în mod determinist

Calculul sinusului unui unghi sau a rădăcinii pătrate dintr-un număr

Rezolvabile în mod stocastic (euristic)

Probleme din lumea reală proiectarea unui ABS

Presupun căutarea unei soluţii

Ianuarie, 2016 5 Fundamentele programării - tehnici de rezolvare a problemelor

http://1.bp.blogspot.com/_xOb625sShwI/TMeSe9pABKI/AAAAAAAAAUw/jG2N0OP6MXY/s1600/image001.gif

Probleme

Tipologie

În funcție de complexitatea temporală a rezolvării

Probleme din clasa P – rezolvabile în timp polinomial (n2, n3, ...)

sortări

Probleme din clasa NP – rezolvabile în timp non polinomial (2n, n!,, ..)

Cel mai scurt drum într-un graf de orașe


Probleme

Tipologie În funcție de scop

Probleme de căutare/optimizare

Planificare, proiectare Mersul trenurilor proiectarea sateliţilor

Probleme de modelare

Predicţii, clasificări

Predictia cursului valutar Predictia aparitiei unei maladii

Probleme de simulare

Teoria jocurilor economice

Productie cerere-oferta

Speculatii bursiere

model intrări ieşiri




http://www.west.sd57.bc.ca/fileadmin/sites/west.sd57.bc.ca/Clip_Art_General/classification.gif

Rezolvarea problemelor

Constă în identificarea unei soluţii

În informatică proces de căutare

În inginerie şi matematică proces de optimizare

Cum?

Reprezentarea soluţiilor (parţiale) puncte în spaţiul de căutare

Proiectarea unor operatori de căutare transformă o posibilă soluţie în altă soluţie


http://www.behavioradvisor.com/sbPuzzled.jpg

Paşi în rezolvarea problemelor

Definirea problemei

Analiza problemei

Alegerea unei tehnici de rezolvare

căutare

reprezentarea cunoştinţelor

abstractizare


http://www.problemsolvingactivities.org/wp-content/uploads/2011/10/5steploop2.jpg

Paşi în rezolvarea problemelor prin căutare –


Rezolvarea prin utilizarea regulilor (în combinaţie cu o strategie de control) de deplasare în spaţiul problemei până la găsirea unui drum între starea iniţială şi cea finală

Rezolvare prin căutare

Examinarea sistematică a stărilor posibile în vederea identificării

unui drum de la o stare iniţială la o stare finală

unei stări optime

Spaţiul stărilor = toate stările posibile + operatorii care definesc legăturile între stări



http://1.bp.blogspot.com/_eKaQV1wZFmU/TOGYKiO9tAI/AAAAAAAAAyo/XIFZk7Ox3l0/s1600/puzzle_20pieces_20resized.jpg



Rezolvare prin căutare

Multiple strategii de căutare cum alegem o

strategie?

Complexitatea computaţională (temporală şi spaţială)

Completitudine algoritmul se sfârşeşte întotdeauna şi găseşte o

soluţie (dacă ea există)

Optimalitate algoritmul găseşte soluţia optimă (costul optim al

drumului de la starea iniţială la starea finală)



http://marianistor.files.wordpress.com/2011/10/searching.jpg



Rezolvare prin căutare Strategii de căutare multiple cum alegem

o strategie? Complexitatea computaţională (temporală şi spaţială)

Performanţa strategiei depinde de:

Timpul necesar rulării

Spaţiul (memoria) necesară rulării

Mărimea intrărilor algoritmului

Viteza calculatorului

Calitatea compilatorului

Se măsoară cu ajutorul complexităţii Eficienţă computaţională

Spaţială memoria necesară identificării soluţiei

S(n) – cantitatea de memorie utilizată de cel mai bun algoritm A care rezolvp o problemă de decizie f cu n date de intrare

Temporală timpul necesar identificării soluţiei

T(n) – timpul de rulare (numărul de paşi) al celui mai bun algoritm A care rezolvă o problemă de decizie f cu n date de intrare

Factori interni

Factori externi


http://3.bp.blogspot.com/-N1UWzjAQrFs/Tox0Fz_TBJI/AAAAAAAABo8/I4IU0v_al2k/s1600/choose1.jpg




Rezolvarea problemelor prin căutare poate consta în:

Construirea progresivă a soluţiei

Identificarea soluţiei potenţiale optime



http://us.123rf.com/400wm/400/400/andresr/andresr0605/andresr060500131/409997-puzzle-pieces-forming-a-path--3d-render.jpg

http://image.shutterstock.com/display_pic_with_logo/292436/292436,1252516103,6/stock-photo-four-colored-puzzle-pieces-assemled-isolated-on-white-with-a-clipping-path-36774760.jpg



Rezolvarea problemelor prin metode clasice

Metode exacte

Metoda generării și testării

backtracking

Metoda divizării -> Divide et Impera

Metoda programării dinamice

Metode euristice

Metoda greedy



Gnerează și testează Ideea de bază

Generarea unei posibile soluții și verificarea corectitudinii ei

Trial and error

Căutare exhaustivă

Mecanism Generare:

determinarea tuturor soluțiilor posibile

Testare: căutarea acelor soluții care sunt corecte (respectă anumite

condiții)

Când se poate folosi Probleme care pot avea mai multe soluții

Probleme cu constrângeri (ale căror soluții trebuie să respecte anumite condiții)


Generează și testează

Algoritm


#D = D(D1) = D(D1(D2))... def generate_test(D): while (True): sol = generate_solution() if (test(sol) == True): return sol


Exemple

Generarea permutărilor cu n=3 elemente

Analiza complexității

Numărul de soluții posibile: 33, adică nn


start

1

1

1 2 3

2

1 2 3

3

1 2 3

2

1

1 2 3

2

1 2 3

3

1 2 3

3

1

1 2 3

2

1 2 3

3

1 2 3

def permut3(): for i in range(1,4): for j in range(1,4): for k in range(1, 4): #generate possibleSolution = [i,j,k] #test if ((i != j) and (j != k) and (k != i)): print(possibleSolution)

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]


Algoritm

Adăugarea de condiții la generarea unei soluții

nu se mai explorează toate soluțiile posibile

se construiesc soluții (parțial) corecte

care respectă anumite condiții


#D = D(D1) = D(D1(D2))... def generate_test(D): while (True): sol = generate_solution_cond() if (test(sol) == True): return sol

Generează și testează Algoritm

Backtracking Spațiul de căutare a unei soluții s

este S (domeniul de definiție) O soluție

este formată din mai multe elemente (s[0], s[1], s[2],...)

Funcția init generează o valoare nulă pentru domeniul de definiție

al soluției Funcția getNext

returnează succesorul (din domeniul de definiție) al unui element al soluției

Funcția isConsistent verifică dacă o soluție (parțială) este corectă

Funcția isSolution verifică dacă o soluție (parțială) este soluție finală

(completă) a problemei



Exemple


Backtracking - variantă iterativă


def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def isConsistent(sol): isCons = True i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 return isCons def isSolution(solution, n): return len(solution) == n

def permut_back(n): k = 0 solution = [] initValue = init() solution.append(initValue) while (k>= 0): isSelected = False while ((isSelected==False) and (solution[k]<getLast(n))): solution[k] = getNext(solution, k) isSelected = isConsistent(solution) if (isSelected == True): if (isSolution(solution,n) == True): print(solution) else: k = k + 1 solution.append(init()) else: del(solution[k]) k = k - 1 permut_back(3)


Exemple


Backtracking - variantă recursivă


def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def isConsistent(sol): isCons = True i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 return isCons def isSolution(solution, n): return len(solution) == n

def permut_back_rec(n, solution): initValue = init() solution.append(initValue) elem = getNext(solution, len(solution) - 1) while (elem <= n): solution[len(solution) - 1] = elem if (isConsistent(solution) == True): if (isSolution(solution, n) == True): print(solution) else: permut_back_rec(n, solution[:]) elem = getNext(solution, len(solution) - 1) sol = [] permut_back_rec(3, sol)

start

1

1

1 2 3

2

1 2 3

3

1 2 3

2

1

1 2 3

2

1 2 3

3

1 2 3

3

1

1 2 3

2

1 2 3

3

1 2 3


Exemple

Backtracking

Analiza complexității



Exemple

Generarea turnurilor de m cuburi care nu se răstoarnă având la dispoziție n cuburi

Backtracking - variantă iterativă


cubes = [10, 2, 5, 6, 7] def init(): return 0 def getNext(sol, pos): return sol[pos] + 1 def getLast(n): return n def isConsistent(sol): isCons = True; i = 0 while ((i<len(sol)-1) and (isCons==True)): if (sol[i] == sol[len(sol) - 1]): isCons = False else: i = i + 1 if (len(sol) > 1): if (cubes[sol[len(sol) - 1] - 1] > cubes[sol[len(sol) - 2] - 1]): return False return isCons def isSolution(solution, n): return len(solution) == n def print_sol(solution): tower = [] for s in solution: tower.append(cubes[s - 1]) print(tower)

def towers(n, m): k = 0 solution = [] initValue = init() solution.append(initValue) while (k>= 0): isSelected = False while ((isSelected == False) and (solution[k] < getLast(n))): solution[k] = getNext(solution, k) isSelected = isConsistent(solution) if (isSelected == True): if (isSolution(solution,m) == True): print_sol(solution) else: k = k + 1 solution.append(init()) else: del(solution[k]) k = k - 1 towers(len(cubes), 4)

Recapitulare


exhaustiv

backtracking


Cursul următor

Rezolvarea problemelor prin metode clasice

Metode exacte

Metoda generării și testării

Metoda divizării -> Divide et Impera

Metoda programării dinamice

Metode euristice

Metoda greedy


Materiale de citit şi legături utile

1. Limbajul Python http://docs.python.org/3/reference/index.html

2. Biblioteca standard Python http://docs.python.org/3/library/index.html

3. Tutorial Python http://docs.python.org/3/tutorial/index.html

4. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini

5. Kent Beck.Test Driven Development: By Example. Addison-Wesley Longman, 2002 http://en.wikipedia.org/wiki/Test-driven_development

6. Martin Fowler. Refactoring. Improving the Design of Existing Code. Addison-Wesley, 1999 http://refactoring.com/catalog/index.html


http://docs.python.org/3/reference/index.html

http://docs.python.org/3/library/index.html

http://docs.python.org/3/tutorial/index.html

http://en.wikipedia.org/wiki/Test-driven_development



http://refactoring.com/catalog/index.html

Informaţiile prezentate au fost colectate din diferite surse de pe internet, precum şi din cursurile de Fundamentele Programării ţinute în anii anteriori de către:

Lect. Dr. Adriana Guran – www.cs.ubbcluj.ro/~adriana

Lect. Dr. Istvan Czibula - www.cs.ubbcluj.ro/~istvanc

Lect. Dr. Andreea Vescan -www.cs.ubbcluj.ro/~avescan

Lect. Dr. Ioan Lazăr -www.cs.ubbcluj.ro/~ilazar


http://www.cs.ubbcluj.ro/~adriana



http://www.cs.ubbcluj.ro/~istvanc



http://www.cs.ubbcluj.ro/~avescan



http://www.cs.ubbcluj.ro/~ilazar



-BOLYAI Facultatea de Matematică şi Informatică...

Documents

Transcript of -BOLYAI Facultatea de Matematică şi Informatică...