Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Bradley Kuszmaul)

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 included write-up gives an overview of Cilk++ and some of the tools available for Cilk programming. The serial algorithm is a recursive search of all paths. To this basic algorithm, two heuristics have been added to reduce search time: remaining-degree and remaining-city. The former looks for situations where there is no path to some city not on the current potential path without revisiting some city already on the potential path. The latter looks for situations where a day between the current day on the potential schedule and the last possible day has home games only for cities already on the potential path. Both situations reveal that the current potential schedule is impossible. The parallelization was done with Cilk++ and simply involves spawning search tasks for all possible neighbors of the node currently being added to the potential path to the end of the tour. The code was intended for Linux OS and includes a makefile to build the applications.


There are downloads available under the Creative Commons License license. Scarica
Per informazioni complete sulle ottimizzazioni del compilatore, consultare l'Avviso sull'ottimizzazione