Algoritma Analizi - NP Hard - Çözümü Bulmak ve Doğrulamak Bile Zor İse

NP-Hard
Çözümü bulmanın yanında, doğrulamanın da zor olduğu problem sınıfına bu isim verilir. Açıklaması şöyle.

It is hard to check that it is the correct solution.

Özellikle çok fazla sayıda kombinasyona sahip problemlerde çözümü doğrulamak çok daha zor. Açıklaması şöyle.

...i.e. to find an optimal solution you had to create all possible combinations of assignments, and select one that fits best. Since this is of exponential time complexity, it is only feasible for small problems, and yours is apparently already too large.

Traveling Salesman Problem

Açıklaması şöyle

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Aslında bu problem NP-Complete olan Hamiltonian Path'in bir benzeri ancak daha zor. Açıklaması şöyle

... start with any node, then go through each other node exactly once, and then go back to the beginning, so it means the path is actually a cycle. A path that goes through all nodes exactly once called a Hamiltonian path. Consequently, such a cycle is a Hamiltonian cycle.