Unit-testing a complex algorithm

How would you write tests for t开发者_运维问答esting a solution to some rather complex algorithm like the N Queens problem? What I mean is what should be the right approach for testing an algorithm that

1. has many solutions (you don't know / don't care how many of them exist),

2. you can only have a small subset of all the possible solutions, and

3. verifying that a solution is correct can be a little bit tricky (maybe comparable in complexity with the algorithm itself).

I know that these conditions are not present in the N-Queens problem itself, but I mentioned it to provide sort of an example.

In your example I think you are saying you want to unit test an algorithm that verifies a proposed solution.

You'd want to cover the following cases:

• Happy path tests to verify that the algorithm accepts a variety of correct solutions
• Happy path tests to verify that the algorithm rejects a variety of incorrect solutions
• Sad path tests to ensure that the algorithm correctly handles non-candidates (e.g. a "solution" with 7 queens instead of 8, etc.)

Here, "a variety" means that you want the solutions to cover the space of possibilities. But what it means to cover that space is problem-specific. I'm not familiar enough with the N-queens problem to know what variety exists across correct solutions, but that information would be useful were I to implement tests. Regarding incorrect solutions, you'd want some involving the same rank, same file, same diagonal, and a mix. Some involving exposure along the edge of the board and some involving exposure off the edge. Etc.

Also, if you have information about the distribution of solutions, you might prioritize those that are more likely, though in the end you'll want to cover even those solutions that are less likely since those are the ones that tend to break things in real life.

Also if the algorithm is complicated then it makes sense to decompose it into parts and test the correctness of those parts in much the same way (distinguish happy from sad path, and test inputs of both sort).

I think this is a very good question and there is no silver bullet. I will just tell you about my experience.

I wrote an algorithm to find the nearest set of points between two cylinders in 3D space. This is a very complex problem and the input space is huge.

In order to test my code, at first I just generated some canonical cases, which were fairly axis aligned, so that the "correct" result was obvious. But that was too weak.

Then I was able to "beef up" the canonical cases by applying random transformations. This helped a bit.

Then I thought about writing another duplicate algorithm and implementation, but that was ridiculously hard, and there is no way to know if both algorithms might exhibit the same bug. However, for another problem this might be feasible, such as with brute-force: not efficient, but very simple to understand and verify.

Then I thought about the properties of the solutions set. For instance the separating vector must be a local minima, so I should be able "look around" each end point of the solution (for a small epsilon) and determine if the solution is a local minima.

Then I started to think about the topological properties of the function mapping the input to the output. In this case I know that the separation distance should vary smoothly. So I chose a random input and small delta, and then compare the output with and without the delta applied. If the algorithm is correct, then difference in the output should be small.

By combining all these techniques I was able to get high confidence in the code.

In testing complex algorithms, you rely on 'data' which needs to be verified. Assume that you already have a solutions (data) in some form the problem. You just take the data and let your algorithm run through and see if the answers match. Take the example of solving an n-puzzle using algorithm, it is non-deterministic, but you have a data to verify the solution.

If you know what kind of an algorithm you will need, then one option is to implement some parts of that algorithm using TDD. So that when those parts have been implemented, building the full algorithm will be trivial.

Here is one example of a problem (diagram of nine places) for which I did not know the solution, so writing a test for it would have been hard, if not impossible, or impractical from TDD's point of view (it would have required too big a leap). I recognized it to be quite similar to the Nine Queens problem, so I decided to use a similar algorithm as I had used for solving Nine Queens. I used DiagramTest to test-drive Diagram, after which putting everything together in DiagramOfNinePlaces was just a dozen lines of code. After running the code, I checked the end result by hand and it was indeed a solution to the problem.

Algorithms are actually the easiest things to unit test since you have no external dependencies. The best approach is use test-driven-development: figure out what the next tiny requirement you want the algorithm to accomplish, create a test for it, and then write the code to satisfy that test (and no more code than necessary, even if this means hardcoding the result). Then you keep going, refactoring the codebase as necessary to make it more general and accept more uses cases. By the time all your use cases are covered you should have a solid implementation of the algorithm.

You can only test for the behaviour you know you can expect.

Do you know that a solution exists for some test data? E.g. you might figure out by hand that it is definitely possible to put six queens on an 8x8 board, or you might read in a book that there exists at least one solution to putting eight queens on the 8x8 board. Then you can test that your program returns at least one solution (perhaps you don't check that it is a valid solution).

Do you know that no solution exists for some other test data? E.g. you can convince yourself quite easily it is impossible to put three queens on a 3x3 or nine queens on an 8x8. Then test that your program returns no solution, or throws the expected exception.

Do you want to test that a given solution is valid? Then you have to write code testing its validity, and you have to run this code, no matter how complex it may be. If it is sufficiently complex, write tests for it as well. If you are lucky, your program can naturally be refactored so that you can reuse some smaller parts of it to test your solution (It's OK to reuse these smaller parts, you won't "introduce the same bug" because you tested these parts thoroughly too).

Finally, once you do find a bug, you have an example of where the program returns an unexpected result. Write a test asserting that it does not return that result the next time.

You can't have 100% test coverage for any program. All you can do is test the cases you know about and have time to write.

There are a lot of problems where creating a solution is much more difficult than checking that any solution is correct.

In the case of something like your N-queens problem, then you merely need to check that their is only one queen on each row and diagonal of the board and that there are N queens on the board in the solution, to know that the solution is valid.

2:

If the problem is known to have other algorithms that work for some coincident set of inputs then try that other algorithm to test your original algorithm for sets of inputs they both work on. For example a brute-force search may work, or can be pre-computed and saved for a smaller range of inputs and used as tests. In some mathematical problems, answers for a restricted range of inputs (such as the squares, or powers of 2, etc), are more easily verified. You should at least test for thse cases.

The unit test should verify the output of the algorithm for a wide variety of inputs and because this task is also complex it has to be written by a different person (and hope that if there is a bug in the code he doesn't do the same mistake)