List of NP-complete problems

np-problems

(Adavidoaiei Dumitru-Cornel) #1

Una dintre cele mai mari provocari in informatica este sa gasesti solutii care ruleaza in timp polinomial la probleme care au pana acuma doar solutii nepolinomiale(ex. exponentiale), o problema clasica este determinarea circuitul hamiltonian intr-un graf, acesta trece prin toate nodurile grafului o singura data, exista o lista impresionanta de astfel de probleme pe partea de grafuri, o lista cuprinzatoare:


(Adavidoaiei Dumitru-Cornel) #2

svg

Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)


(Adavidoaiei Dumitru-Cornel) #3

Contine implementarea unui algoritm de determinare a componentelor conectate dintr-un graf o componenta poate fi privita ca un oras iar legaturile dintre orase ca si componente conectate foloseste ceva algoritm de parcurgere grafuri cu BFS, si stocheaza graful cu o matrice de adiacenta.

Google Maps foloseste grafuri in pathfinding dintre cei mai cunoscuti algoritmi de pathfinding este algoritmul Dijkstra, din cate am inteles din articol Google Maps foloseste o variatie de A*.