Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Matthew McGowan)

The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The serial code initially uses a naive depth first search approach, but determines that a solution based on Constraint Programming overcomes the weakness of the naïve approach. A constraint programming library is used to solve the problem as a constraint model. The chosen library (JaCoP) contains only sequential solvers, so a parallel solver was implemented using the sequential features of the library. Multiple solvers were scheduled for parallel execution through Java Threads. Simple load balancing heuristics were used to achieve the desired level of parallelism. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application.

DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

There are downloads available under the Creative Commons License license. Download Now
For more complete information about compiler optimizations, see our Optimization Notice.