Heuristic Algorithms for NP-Complete Problems |
Thomas V. Christensen
|
| Abstract | I have implemented a small framework of NP-complete problems in Java, where it is possible to transform instances of one NP-Complete problem into instance of another NP-Complete problem. The framework also consists of a few heuristic algorithms, which makes it possible to find a heuristic solution for instances of an NP-Complete problem.
Combining these two features it is possible to transform an instance of one NP- Complete problem into another instance. This transformed instance may then be solved by the available heuristic algorithm and the found heuristic solution may then be detransformed to the original instance. Last but not least it is possible to view this scheme through a nice user friendly GUI.
This report analyzes the design of the framework, the behavior of the heuristic algorithms to transformed instances and how one may find the best transformation automatically to a given NP-Complete problem. |
| Type | Bachelor of Engineering thesis [Academic thesis] |
| Year | 2007 |
| Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU |
| Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby |
| Series | IMM-B.Sc-2007-12 |
| Note | Supervised by Assoc. Prof. Paul Fischer, IMM, DTU. |
| Electronic version(s) | [pdf] |
| BibTeX data | [bibtex] |
| IMM Group(s) | Computer Science & Engineering |