pyGM: CSPs

pyGM.csp.OK(factors)

Return 0 if constraints already violated; 1 otherwise

class pyGM.csp.PriorityQueue

Priority queue wrapper; returns highest priority element.

pyGM.csp.arcConsistent(csp, updated=None, nvalid=None)

Update csp to arc consistency, from changes to updated (default: all)

pyGM.csp.astar(model, order)

Basic A-star search for graphical model ‘model’ using search order ‘order’.

pyGM.csp.backtrack(model, order)

Backtracking search for CSPs. Use GraphModel container of constraint factors and search order ‘order’.

pyGM.csp.backtrackRecurse(csp, assign)

Internal recursive function for backtracking search on CSP given partial assignment

pyGM.csp.backtrackingSearch(constraints)

Backtracking search for list of constraint satisfaction factors. Returns a solution if one exists; None otherwise.

pyGM.csp.backtrackingSearch2(constraints)

Backtracking search for list of constraint satisfaction factors. Returns a solution if one exists; None otherwise.

pyGM.csp.condition(csp, Xi, xi)

Make a copy of the CSP, then assert Xi=xi in that copy & return it

pyGM.csp.consistent(csp, assign)

Return False if CSP known inconsistent; True otherwise. Note: assumes that “assign” has already been incorporated into the CSP

pyGM.csp.generate3SAT(alpha, n)

Generate factors corresponding to a random 3-SAT problem with n variables and alpha*n CNF clauses

pyGM.csp.hillClimbing(X, objectiveFn, xInit=None, maxSteps=100, maxValue=inf, verbose=False)

Basic greedy hill-climbing local search over configurations

pyGM.csp.hillClimbing2(X, objectiveFn, xInit=None, maxSteps=100, maxValue=inf, verbose=False)

Hill climbing local search, but with random walk on plateaus

pyGM.csp.inference(csp, Xi, xi)

Update the CSP after setting Xi=xi, to reduce other variable domains if desired

pyGM.csp.minConflicts(model, maxSteps=100, verbose=False)

Minimum conflicts local search for CSPs

pyGM.csp.nViolated(factors, x)

Evaluate the number of violated constraints in a set of 0/1 factors

pyGM.csp.orderDomainValues(csp, Xi, assign)

Return a sequence of values to test for Xi in CSP with current assignment

pyGM.csp.selectUnassignedVar(csp, assign)

Return the next variable to assign, given the CSP and current assignment

• Index
• Index
• Module Index
• Search Page