Dynamic ordering between Asynchronous Backtracking algorithms

Abstract

A great number of problems, like scheduling shifts in a hospital, or dividing up resources for manufacturing, can be reduced to a problem called Constraint Satisfaction Problem (CSP). These CSPs make use of constraints placed on variables to determine if a problem can be satisfied. In this thesis, the effect of ordering variables on a backtracking algorithm used to solve a CSP will be explored. A number of graphs used to model a CSP problem will be solved, dynamically changing the order of the agents in between every run. Results found indicated a decline in median number of edges in the order of agents as they ranked from a high priority to a lower priority, as well as a reduced number of backtracks required on a lower decay rate. Conclusively, the order of agents seems to matter with respect to the median number of edges per agent, but where the decay rate barely has any influence on the median number of edges, they do greatly influence the number of backtracks required.