N皇后问题随机算法性能分析

Performance Analysis of the Random Algorithm for N-Queen Problem

N皇后问题是NP问题,以随机算法结合回溯求解该问题,能获得很好性能。算法性能与随机皇后数量的关系曲线呈U型。随机皇后数量须在宽度不大于20的特定范围内才能获得较好性能。100以内随n变大,最佳随机皇后数量从n-10到n-17缓慢变化。最佳随机皇后数量使算法能在常规时间内求解n>100的情况,远大于单纯回溯法求解规模30。由于回溯开销,提高随机算法性能的做法不能有效降低总用时。算法用时随n值递增的速度不断趋缓。

N-Queen problem is a NP problem. By the way of Random algorithm with BackTrack, the problem is solved with a good performance. The performance graph is the shap of U. While the number of random queens is in a special range that is nar row than 20, the algorithm's performance is good. With the increasing of the number of queens below 100, the best number of random queens changes slowly from n-10 to n-17. Algorithm can solve 100-Queen in common time, far larger than pure Back Track way. Because of the BackTack expenses, it is hard to reduce the total time by Optimizing the Random algorithm. As n in creases, the algorithm time increases more and more slowly.