Parallel solution to Taxi Path Problem (mdma)

The included code and white paper provides a parallel solution for enumerating Delannoy paths visualized as paths of a taxi through a grid of city streets. A divide and conquer algorithm divides the Cartesian grid into smaller regions. These subregions are themselves further recursively subdivided until the base case, a 1x1 block, is reached. For the base case, the set of paths are known in advance. The subdivided blocks are then joined together, to create larger blocks with longer paths, until eventually the complete grid has been built and the full set of paths generated. Each block-size is solved once and the results are reused multiple times. Parallelism is achieved using Java and Java Threads.

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

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.