
Если Вы найдете статью полезной и интересной  не сочтите за труд,
переведите материал или хотя бы часть его и отправьте на адрес
algolist@manual.ru.
Задать вопросы или просто написать письмо можно
также на странице контактов.

A Story about the NQueens Problem:
From Exponential to (Almost) Constant Time

Constraint Satisfaction Problem

Local Search Optimization
A Story about the NQueens Problem:
From Exponential to (Almost) Constant Time
The nqueens problem is to place n queens on an N X N chessboard,
so that no two queens attack each other. An extensive bibliography on
the problem is available here.
The nqueens problem is
a classical search problem, used as a testbed for the development
and benchmarking of search algorithms. Traditional search methods
involve backtracking. Because the complexity of backtracking usually
rises exponentially with the size of the problem, it is desirable to
develop alternatives to backtracking search. To overcome the weaknesses
of backtracking, we have started to develop local search methods
in late 1987, using the nqueens problem as a testbed.
At that time, the best backtracking methods could find a solution for
the problem sizes of around 100.
The first local search algorithm was able to find a solution for the problem
size of 500,000 in around 10,000s on a Next computer. A description of
the algorithm can be found in R. Sosic and J. Gu. A Polynomial Time
Algorithm for the NQueens Problem. SIGART Bulletin, Vol. 1, 3,
pp. 711, Oct, 1990.
(retrieve a Postscript^{zip} version)
The algorithm was further improved, which reduced the search time to 94s
on a Next computer. A description of improvements and an analysis of the
algorithm behavior can be found in R. Sosic and J. Gu. Fast Search
Algorithms for the NQueens Problem. IEEE Transactions on Systems, Man,
and Cybernetics. Vol. 21, 6, pp. 15721576, Nov/Dec, 1991.
(retrieve a Postscript^{zip} version)
The final version of the algorithm is capable of solving the nqueens
problem in a linear time. On an IBM RS6000, it takes around 55s to find
a solution to the problem size of 3,000,000. An initial description
of the algorithm can be found in R. Sosic and J. Gu. 3,000,000 Queens
in Less Than One Minute. SIGART Bulletin, Vol. 2, 2, pp. 2224,
Apr, 1991.
(retrieve a Postscript^{zip} version)
A detailed description and an indepth analysis of the
algorithm can be found in R. Sosic and J. Gu. Efficient Local Search
with Conflict Minimization: A Case Study of the NQueens Problem.
IEEE Transactions on Knowledge and Data Engineering,
Vol. 6, 5, pp. 661668, Oct 1994.
(retrieve a Postscript^{zip} version)
The next stage was the development of a parallel version of the algorithm.
The algorithm performs a probabilistic parallel search and by using n
processors, its running time is O(log^2n). With some tunning, the algorithm
can find a solution in a constant number of steps  12  in a PRAM model.
A description and analysis of the algorithm can be found in R. Sosic.
A Parallel Search Algorithm for the NQueens Problem. Parallel Computing
and Transputer Conference, Wollongong, pp. 162172, IOS Press, Nov 1994.
(retrieve a Postscript^{zip} version)
Constraint Satisfaction Problem
The nqueens problem has been studied in relationship to the research
on the constraint satisfaction problem. The goal of the research is
to develop fast and practical solutions to large scale constraint
satisfaction problems.
Some results of this research can be found in J. Gu and R. Sosic.
A Parallel, Optimal Arc Consistency Algorithm.
1990 International Conference on Parallel Processing,
pp. I599600, 1990.
and
J. Gu and R. Sosic.
A Parallel Architecture for Constraint Satisfaction.
International Conference on Industrial and Engineering
Applications of Artificial Intelligence and Expert Systems,
June 1991, Kauai, Hawaii, pp. 229237, 1991.
(retrieve a Postscript^{zip} version)
Local Search Optimization
Local search methods are often approximative. The improvement in
the quality of the solution requires more computational time.
One of the questions is how long an algorithm should run for
a given quality of solution. An initial investigation of this question
is presented in R. Sosic and G. Wilby.
Using the QualityTime Tradeoff in Local Optimization.
IEEE Second ANZIIS Conference,
Brisbane, pp. 253257, IEEE, Dec 1994.
(retrieve a Postscript^{zip} version)
