Beta 1

Title A Multi-Agent Approach to Solving NP-Complete Problems
Author Agerbeck, Christian
Hansen, Mikael O.
Supervisor Bolander, Thomas (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract 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 SAT-solving. 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.
Series IMM-M.Sc.-2008-05
Original PDF ep08_05.pdf (1.09 MB)
Admin Creation date: 2008-01-30    Update date: 2010-10-28    Source: dtu    ID: 209668    Original MXD