最近接触到为客户的客服排班的需求，之前根据客户的需求，同事已经完成了自动排班系统，需要我继续支撑的是做一些优化即可。当我接触到这个项目之后，我便联想到以前所学的CSP最小冲突法或许可以解决排班问题。在这里，想要介绍一下这种方法。
CSP最小冲突法的主要思想是，找到满足约束条件的情况。
主要步骤：
具体的算法代码，我们可以使用这本书上的 Artificial Intelligence: A Modern Approach，有兴趣的也可以看他的GitHub
import random
def min_conflicts(vars, domains, constraints, neighbors, max_steps=1000):
"""Solve a CSP by stochastic hillclimbing on the number of conflicts."""
# Generate a complete assignment for all vars (probably with conflicts)
current = {}
for var in vars:
val = min_conflicts_value(var, current, domains, constraints, neighbors)
current[var] = val
# Now repeatedly choose a random conflicted variable and change it
for i in range(max_steps):
conflicted = conflicted_vars(current,vars,constraints,neighbors)
if not conflicted:
return (current,i)
var = random.choice(conflicted)
val = min_conflicts_value(var, current, domains, constraints, neighbors)
current[var] = val
return (None,None)
def min_conflicts_value(var, current, domains, constraints, neighbors):
"""Return the value that will give var the least number of conflicts.
If there is a tie, choose at random."""
return argmin_random_tie(domains[var],
lambda val: nconflicts(var, val, current, constraints, neighbors))
def conflicted_vars(current,vars,constraints,neighbors):
"Return a list of variables in current assignment that are in conflict"
return [var for var in vars
if nconflicts(var, current[var], current, constraints, neighbors) > 0]
def nconflicts(var, val, assignment, constraints, neighbors):
"Return the number of conflicts var=val has with other variables."
# Subclasses may implement this more efficiently
def conflict(var2):
val2 = assignment.get(var2, None)
return val2 != None and not constraints(var, val, var2, val2)
return len(list(filter(conflict, neighbors[var])))
def argmin_random_tie(seq, fn):
"""Return an element with lowest fn(seq[i]) score; break ties at random.
Thus, for all s,f: argmin_random_tie(s, f) in argmin_list(s, f)"""
best_score = fn(seq[0]); n = 0
for x in seq:
x_score = fn(x)
if x_score < best_score:
best, best_score = x, x_score; n = 1
elif x_score == best_score:
n += 1
if random.randrange(n) == 0:
best = x
return best
上面是书中作者写好的几个方程，而我们要做的就是利用这几个方程，去解决实际的问题。下面，就让我们先从最简单的八皇后问题看起。
说起CSP最小冲突法，就要说很著名的八皇后问题，具体的描述可以点击：八皇后
先定义我们的八个皇后，这里我们可以用0-7八个数字表示
vars = range(8)再定义一下，八个皇后对应可以移动的区域，这里我们可以用字典型数据表示
domains = {key: range(8) for key in vars}print(domains)接下来，既然我们要使用最小冲突法，那么就要确定冲突值。
neighbors = {var: [v for v in vars if v != var] for var in vars}print(neighbors)下面，我们需要给一些约束条件，这些即帮助最小冲突法去迭代运算。
def constraints_ok(col1, row1, col2, row2):
return (row1 != row2 and
col1+row1 != col2+row2 and
col1-row1 != col2-row2 and
col1 != col2)
最后，当我们需要测试这些代码是否正确，那么如何保证对呢，这里我们就需要可视化展示了。
print(‘\u265b‘)def display(assignment):
for row in range(8):
for col in range(8):
if assignment[col] == row:
print('\u265b', end='')
else:
print('--', end='')
print()测试一下这个可视化展示函数,可以使用一下代码测试
display({0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7:7})?--------------
--?------------
----?----------
------?--------
--------?------
----------?----
------------?--
--------------?
接下来，就可以愉快的测试我们的函数，算法了
solution, steps = min_conflicts(vars, domains, constraints_ok, neighbors)
print('Solution found in', steps, 'steps')
display(solution)
这里，我放上一种展示结果
----------?----
?--------------
--------?------
--?------------
--------------?
----?----------
------------?--
------?--------
至此，我们对八皇后的测试就结束了，当然，这里都是通用的，你也可以说设置N个皇后，只需要改遍var的值范围就可以了。
简单的八皇后问题，我们已经解决了，那么复杂一点的排课表呢？
问题描述：
首先，定义初始变量
classes = ['CS160', 'CS163', 'CS164',
'CS220', 'CS270', 'CS253',
'CS320', 'CS314', 'CS356', 'CS370',
'CS410', 'CS414', 'CS420', 'CS430', 'CS440', 'CS445', 'CS453', 'CS464',
'CS510', 'CS514', 'CS535', 'CS540', 'CS545']
times = [' 9 am','10 am', '11 am','12 pm',' 1 pm',' 2 pm',' 3 pm', '4 pm']
rooms = ['CSB 130', 'CSB 325', 'CSB 425']接下来，我们依然要使用上述的算法方程，需要我们自己写的只有三个方程
这里对每个方程里面的参数进行一下简单的说明：
下面，展示一下我写的几个方程：
def schedule(classes, times, rooms, max_steps):
domains = {}
neighbors = {}
for classname in classes:
# define neighbors
classbridge = copy.deepcopy(classes)
classbridge.remove(classname)
neighbors[classname] = classbridge
# define assigments
domains[classname]=[]
for time in times:
for roomname in rooms:
domains[classname].append((roomname,time))
solution, steps = min_conflicts(classes, domains, constraints_ok, neighbors, max_steps=1000)
return solution, stepsdef constraints_ok(class_name_1, value_1, class_name_2, value_2):
if (class_name_1=='CS163' and class_name_2=='CS164') or (class_name_1=='CS164' and class_name_2=='CS163'):
if value_1[0]!= value_2[0] or value_1[1] != value_2[1]:
return True
else:
return False
if class_name_1[2] == class_name_2[2]:
if value_1[1] != value_2[1]:
return True
else:
if value_1[0]!= value_2[0] or value_1[1] != value_2[1]:
return True
return Falsedef display(assignments, rooms, times):
data={}
data[' ']=[]
for time in times:
data[' '].append(time)
for roomname in rooms:
data[roomname]=[]
for time in times:
i = 0
for assignment in assignments:
if assignments[assignment][0]==roomname and assignments[assignment][1]==time:
data[roomname].append(assignment)
break
if i == 22:
data[roomname].append(' ')
i+=1
frame = pd.DataFrame(data)
print(frame)
max_steps = 100
solution, steps = schedule(classes, times, rooms, max_steps)
print('Took', steps, 'steps')
display(solution, rooms, times)
运行上面的语句，测试代码，可以看到具体的展示，这里由于是随机初始化，生成的解每次都是不同的，下面展示一种情况：
CSB 130 CSB 325 CSB 425
0 9 am CS535 CS410 CS164
1 10 am CS356 CS420 CS270
2 11 am CS414 CS514
3 12 pm CS314 CS545 CS453
4 1 pm CS510 CS220 CS440
5 2 pm CS540 CS430 CS370
6 3 pm CS464 CS160 CS253
7 4 pm CS163 CS320 CS445
至此，最小冲突法的介绍及一些简单应用就结束了，更为复杂的客服排排班等，也可用此方法解决。
原文：https://www.cnblogs.com/shenggang/p/12133270.html