Algorithms: ideas and approaches

What algorithm ideas do we have and how would we implement them?

Topological order

• Just do a topological sort on the input graph and schedule everything on one processor
• Will be very fast
• Will not be optimal
• Can use for milestone

Branch and Bound

• As presented in lectures
• Concept: start at the root, and then do DFS, and when we reach a solution, update our upper bound
• Stop searching a path if the upper bound is reached
• Branch and Bound will be easy to parallelize: can just give each processor one part of the solution space
• We can probably speed it up by bounding based on a heuristic
  • Could pick which nodes to DFS first greedily based on this

A*

• Also as presented in lectures
• Need a good heuristic
• Priority queue needs to be maintained
  • Could use up a lot of memory
• Parallelization?
  • Might be tricky: algorithm operates over the same heap

Other algorithm ideas

Iterative Deepening A*

• Repeated DFS with a different 'upper bound'
• DFS stops each iteration when cost estimate is greater than iteration's upper bound
• Bound is then increased
• Parallelizable in a similar way to Branch and Bound

Fringe search

• Similar to IDA* as above but instead keep a linked list of the bottom fringe of the explored space
• No more iterations required
• Linked list might get long (but much shorter than the priority queue required for regular A*)
• Some people have successfully implemented this (in parallel!) for the shortest path problem and it was faster than plain A*