Algorithms – A* Algorithm Completeness Proof

The NP-Hard domain of problems means that, as far as current mathematical knowledge goes, the problem can only be solved by trying every permutation and choosing the correct answer.

If you can solve the problem more efficiently than the brute force method, you will win a Noble Prize in mathematics as a bonus. The best mathematicians have been working on a general answer to this problem for decades.

Perhaps as you are wanting to create a test data-set for your NP-Hard problem solver, your approach may be to design the test data backwards - rather than solve the NP-Hard problem, create an NP-Hard problem with a known answer - I don't even know if that is a NP-Hard problem on it's own.

It depends on the kind of problem.

If there is a polynomial-time approximation scheme (PTAS) for the problem (e.g. Euclidian TSP), then you can get a solution that's arbitrarily close to the optimal solution in polynomial time. That means, for every e > 0, there is a polynomial time algorithm that will find an approximate solution to your problem, that is guaranteed to be within (1+e) of the optimal solution. In that case, you would just compare the runtime/memory complexity for two algorithms for the same values of e. If one algorithm can make the same "optimality guarantees" than the other, but at a lower running time/memory cost, then it's probably the better algorithm.

If the problem is APX, but not PTAS, i.e. if there are polynomial time approximation algorithms that are guaranteed to produce solutions that are within a constant factor of the optimal solution, then you can compare that constant factor. The one with the lower factor will produce the better solutions (but often at the cost of higher running time/memory costs)

If the problem is in neither of those classes, then I think the best you can do is to compare their solutions for a set of random problems, or for problems with known optimal solutions.