algorithmsevaluationoptimization
is there a general method to evaluate the optimality of an optimization algorithm, for example an algorithm solving an otherwise NP-hard or NP-complete problem?
The only method I came up so far is comparing the results of the algorithm against already known optimal solutions.
If not, are there specific methods for some special problems?
EDIT To clarify: By optimality I mean how close the result is to an optimal solutions result.
Although it would be near impossible to track % complete accurately due to an undetermined number of links and keywords it is possible to show a rough status via depth. For example the first depth would be the url/s processed from the top level.
(100/Total Pages) * Pages Processed = % current status
Total Pages = Select count() from master_links
Pages Processed = Select count() from master_links where processed=true. When you have processed the page simply set the flag in the db.
(This could similarly be done by populating an array with your db values and using the index value as your pages processed)
Note: You can only get the status for each level. Do not start crawling your sub_links until all the master_links are crawled - this will also allow you to avoid duplicate url crawls and should have a minimal impact on the total time.
The squares in the diagram below represent the pages which need to be processed. Inside each box is the percentage complete if you were processing them left to right. This is for illustrative purposes the percentage would be based on this:
Your output would show percentage complete of that level:
e.g. Master Links 40% complete
or
e.g. Master Links 100%
Sub Links 49.8%
This should still give you enough info to indicate the progress, after all you cannot guess the actual density of keywords and links...
This is NP-hard. If you have a solution for this problem, then you can use it on a graph with all edge weights set to 1. Then the resulting path will have the same number of nodes as the graph if and only if there is a Hamiltonian path. Since determining the existence of a Hamiltonian path is NP-hard even without finding specific solutions, any solution to this problem is at least as hard.
Wikipedia page: http://en.wikipedia.org/wiki/Hamiltonian_path
Edit: You might want to look at approximate solutions, but I have little experience with those. The wiki page tells you a lot more than I can: http://en.wikipedia.org/wiki/Approximation_algorithm
Best Answer
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.