Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def mrv(csp):
- counter = 0
- refvariable = csp.variables[0], 0
- for var in csp.variables:
- if var.get_value() is None:
- for peer in var.peers:
- if peer.get_value() is not None:
- counter += 1
- print peer
- variable = var, counter
- counter = 0
- if variable[1] > refvariable[1]:
- refvariable = variable
- print refvariable
- return refvariable
- def backtracking(csp, ac_3=False):
- """
- Implement the basic backtracking algorithm to solve a CSP.
- Optional: if ac_3 == True use the AC-3 algorithm for constraint
- propagation. Important: if ac_3 == false don't use
- AC-3!
- :param csp: A csp.ConstrainedSatisfactionProblem object
- representing the CSP to solve
- :return: A csp.ConstrainedSatisfactionProblem, where all Variables
- are set and csp.complete() returns True. (I.e. the solved
- CSP)
- """
- variable = csp.variables[0]
- if csp.complete():
- return csp
- for var in csp.variables:
- if var.get_value() is None:
- variable = var
- for value in variable.domain:
- variable.set_value(value)
- if csp.consistent():
- result = backtracking(csp)
- if csp.consistent():
- return result
- variable.set_value(None)
- def minimum_remaining_values(csp, ac_3=False):
- """
- Implement the basic backtracking algorithm to solve a CSP with
- minimum remaining values heuristic and no tie-breaker. Thus the
- first of all best solution is taken.
- Optional: if ac_3 == True use the AC-3 algorithm for constraint
- propagation. Important: if ac_3 == false don't use
- AC-3!
- :param csp: A csp.ConstrainedSatisfactionProblem object
- representing the CSP to solve
- :return: A tuple of 1) a csp.ConstrainedSatisfactionProblem, where
- all Variables are set and csp.complete() returns True. (I.e.
- the solved CSP) and 2) a list of all variables in the order
- they have been assigned.
- """
- return min_rem_rec(csp, [])
- def min_rem_rec(csp, varlist):
- if csp.complete():
- return csp, varlist
- variable,_ = mrv(csp)
- varlist.append(variable)
- print varlist
- for value in variable.domain:
- variable.set_value(value)
- if csp.consistent():
- result, varlist = min_rem_rec(csp, varlist)
- if csp.consistent():
- return result, varlist
- variable.set_value(None)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement