||A Multi-Agent Approach to Solving NP-Complete Problems
Hansen, Mikael O.
||Bolander, Thomas (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||This master's project concerns the use of multi-agent design principles in making efficient solvers for NP-complete problems. The design of computer programs
as multi-agent systems presents a new and very promising software engineering
paradigm, where systems are described as individual problem-solving agents pursuing high-level goals. Recently, researchers have started to apply the multi-agent
paradigm to the construction of efficient solvers for NP-complete problems. This
has resulted in very effective tools for routing problems, graph partitioning and
The objective of the present project is to make further studies into the application
of multi-agent principles to solving NP-complete problems. More specifically, the
project has the following two goals. First, it should result in a general discussion of
the use of multi-agent approaches to solving NP-complete problems. This should
include a discussion of strengths and weaknesses compared to other approaches of
solving the same problems. Second, it should result in a concrete software tool for
solving n2 £ n2 Sudoku puzzles, which is known to be an NP-complete problem.
The tool should be benchmarked against other solvers for Sudoku.
Creation date: 2008-01-30
Update date: 2010-10-28