Maze-solving algorithm: Difference between revisions

Revision as of 15:51, 1 July 2016

Revision as of 19:31, 6 July 2016

Line 95:

== Maze-Routing algorithm ==

The Maze-Routing algorithm <ref>{{cite journal|last1=Fattah|first1=Mohammad|last2=et|first2=al.|title=A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips|journal=NOCS '15 Proceedings of the 9th International Symposium on Networks-on-Chip|date=2015-09-28|doi=10.1145/2786572.2786591|url=http://dl.acm.org/citation.cfm?id=2786591}}</ref> is a low overhead method to find the way between any two locations of the maze. The algorithm is initially proposed for Chip Multiprocessors (CMPs) ___domain and guarantees to work for any grid-based maze. In addition to finding paths between two ___location of the grid (maze), the algorithm can detect it when there is no path between the source and destination. Also, the algorithm is to be used by an inside traveler with no prior knowledge of the maze with fixed memory complexity regardless of the maze size; requiring 4 variables in total for finding the path and detecting the unreachable locations. Nevertheless, the algorithm is not to find the shortest-path.

Maze-routing algorithm uses the notion of Manhattan Distance (MD) and relies on the property of grids that the MD increments/decrements ''exactly'' by 1 when moving from one ___location to any 4 neighboring locations. Here is the pseudocode, without the capability to detect unreachable locations.