| dc.description.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. | |
