I lack formal knowledge about statistics and got lost in the Wikipedia articles about the subject.
I have an algorithm that produces a solution for a problem. There might be several solutions possible. Not all solutions are equally good, and I am able to give score for each solution.
I want to be able to tell if the algorithm is good or not.
For each problem I can calculate bounds on the best and worst possible solution (only bounds, not exact values). I can also generate a random solutions for a problem, but not every random solution is a valid one (high chances for getting a valid one, though).
The data set I am going to use have problems of approximately the same difficulty.
Clearly I should use some statistical test, but which one? It seems that they require knowledge about the distribution and are more suitable for comparing algorithms.
I do not want to add too much irrelevant specifics, so I will try to simplify.
I have an algorithm that solves a problem. for example, it finds a path between two nodes in a graph. The input is a graph. The output is a path.
Obviously, shorter paths are better than longer ones.
I want to know if my algorithm is good. I do not know exactly how to define "good", but that is where statistics can help me, is not it?
What I though about so far was to do the following:
- Run the algorithm on a set of problems (problem is a graph). The sizes of all these graphs are of the same order of magnitude.
- Find a random path (in my specific problem it is possible to do) for each graph, and do this many times.
- Compare the results of 1 and 2 to see if my algorithm is better than choosing a path at random.
Am I doing it right? How should I perform step 3?