程序示例
TIP
阅读程序并运行
完成习题
📥
本节附件下载
Hospital (局部搜索)
python
import random
class Space():
def __init__(self, height, width, num_hospitals):
"""创建一个具有给定维度的新状态空间"""
self.height = height # 高度
self.width = width # 宽度
self.num_hospitals = num_hospitals # 医院数量
self.houses = set() # 住房位置集合
self.hospitals = set() # 医院位置集合
def add_house(self, row, col):
"""在状态空间中的特定位置添加住房"""
self.houses.add((row, col))
def available_spaces(self):
"""返回住房或医院当前未使用的所有单元格"""
# 考虑所有可能的单元格
candidates = set(
(row, col)
for row in range(self.height)
for col in range(self.width)
)
# 排除所有住房和医院
for house in self.houses:
candidates.remove(house)
for hospital in self.hospitals:
candidates.remove(hospital)
return candidates
def hill_climb(self, maximum=None, image_prefix=None, log=False):
"""执行爬山算法找到解决方案"""
count = 0
# 从随机初始化的医院位置开始
self.hospitals = set()
for i in range(self.num_hospitals):
self.hospitals.add(random.choice(list(self.available_spaces())))
...
# 执行算法，直到达到最大迭代次数
while maximum is None or count < maximum:
count += 1
best_neighbors = []
best_neighbor_cost = None
# 考虑所有医院移动
for hospital in self.hospitals:
# 考虑一下那家医院的所有邻居
for replacement in self.get_neighbors(*hospital):
# 生成一组相邻的医院
neighbor = self.hospitals.copy()
neighbor.remove(hospital)
neighbor.add(replacement)
# 检查邻居是否是迄今为止最好的
cost = self.get_cost(neighbor)
if best_neighbor_cost is None or cost < best_neighbor_cost:
best_neighbor_cost = cost
best_neighbors = [neighbor]
elif best_neighbor_cost == cost:
best_neighbors.append(neighbor)
# 没有一个邻居比目前的状态更好
if best_neighbor_cost >= self.get_cost(self.hospitals):
return self.hospitals
# 移动到价值最高的邻居
else:
...
self.hospitals = random.choice(best_neighbors)
...
def random_restart(self, maximum, image_prefix=None, log=False):
"""多次重复爬山算法"""
best_hospitals = None
best_cost = None
# 重复爬山算法的固定次数
for i in range(maximum):
hospitals = self.hill_climb()
cost = self.get_cost(hospitals)
if best_cost is None or cost < best_cost:
best_cost = cost
best_hospitals = hospitals
...
else:
...
...
return best_hospitals
def get_cost(self, hospitals):
"""计算从住房到最近医院的距离总和"""
cost = 0
for house in self.houses:
cost += min(
abs(house[0] - hospital[0]) + abs(house[1] - hospital[1])
for hospital in hospitals
)
return cost
def get_neighbors(self, row, col):
"""返回尚未包含住房或医院的邻居"""
candidates = [
(row - 1, col),
(row + 1, col),
(row, col - 1),
(row, col + 1)
]
neighbors = []
for r, c in candidates:
if (r, c) in self.houses or (r, c) in self.hospitals:
continue
if 0 <= r < self.height and 0 <= c < self.width:
neighbors.append((r, c))
return neighbors
def output_image(self, filename):
"""生成所有房屋和医院的图像（不作要求）"""
from PIL import Image, ImageDraw, ImageFont
cell_size = 100
cell_border = 2
cost_size = 40
padding = 10
# Create a blank canvas
img = Image.new(
"RGBA",
(self.width * cell_size,
self.height * cell_size + cost_size + padding * 2),
"white"
)
house = Image.open("assets/images/House.png").resize(
(cell_size, cell_size)
)
hospital = Image.open("assets/images/Hospital.png").resize(
(cell_size, cell_size)
)
font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 30)
draw = ImageDraw.Draw(img)
for i in range(self.height):
for j in range(self.width):
# Draw cell
rect = [
(j * cell_size + cell_border,
i * cell_size + cell_border),
((j + 1) * cell_size - cell_border,
(i + 1) * cell_size - cell_border)
]
draw.rectangle(rect, fill="black")
if (i, j) in self.houses:
img.paste(house, rect[0], house)
if (i, j) in self.hospitals:
img.paste(hospital, rect[0], hospital)
# Add cost
draw.rectangle(
(0, self.height * cell_size, self.width * cell_size,
self.height * cell_size + cost_size + padding * 2),
"black"
)
draw.text(
(padding, self.height * cell_size + padding),
f"Cost: {self.get_cost(self.hospitals)}",
fill="white",
font=font
)
img.save(filename)
# 创建一个状态空间并随机添加住房
s = Space(height=10, width=20, num_hospitals=3)
for i in range(15):
s.add_house(random.randrange(s.height), random.randrange(s.width))
# 使用局部搜索来确定医院位置
hospitals = s.random_restart(maximum=100, image_prefix="hospitals", log=True)Production (线性规划)
python
import scipy.optimize
# Objective Function: 50x_1 + 80x_2
# Constraint 1: 5x_1 + 2x_2 <= 20
# Constraint 2: -10x_1 + -12x_2 <= -90
result = scipy.optimize.linprog(
[50, 80], # Cost function: 50x_1 + 80x_2
A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities
b_ub=[20, -90], # Constraints for inequalities: 20 and -90
)
if result.success:
print(f"X1: {round(result.x[0], 2)} hours")
print(f"X2: {round(result.x[1], 2)} hours")
else:
print("No solution")Schedule (约束满足)
python
"""没有任何启发式或推理的自然回溯搜索"""
VARIABLES = ["A", "B", "C", "D", "E", "F", "G"]
CONSTRAINTS = [
("A", "B"),
("A", "C"),
("B", "C"),
("B", "D"),
("B", "E"),
("C", "E"),
("C", "F"),
("D", "E"),
("E", "F"),
("E", "G"),
("F", "G")
]
def backtrack(assignment):
"""运行回溯搜索以查找赋值"""
# 检查赋值是否完成
if len(assignment) == len(VARIABLES):
return assignment
# 尝试一个新变量
var = select_unassigned_variable(assignment)
for value in ["Monday", "Tuesday", "Wednesday"]:
new_assignment = assignment.copy()
new_assignment[var] = value
if consistent(new_assignment):
result = backtrack(new_assignment)
if result is not None:
return result
return None
def select_unassigned_variable(assignment):
"""按顺序选择尚未赋值的变量"""
for variable in VARIABLES:
if variable not in assignment:
return variable
return None
def consistent(assignment):
"""检查分配是否一致"""
for (x, y) in CONSTRAINTS:
# 仅考虑变量赋值都已指定的弧
if x not in assignment or y not in assignment:
continue
# 如果两者的值相同，则不一致
if assignment[x] == assignment[y]:
return False
# 如果没有不一致的地方，那么赋值是一致的
return True
solution = backtrack(dict())
print(solution)使用命令 pip install python-constraint 安装 constraint 库
python
from constraint import *
problem = Problem()
# 添加变量
problem.addVariables(
["A", "B", "C", "D", "E", "F", "G"],
["Monday", "Tuesday", "Wednesday"]
)
# 添加约束
CONSTRAINTS = [
("A", "B"),
("A", "C"),
("B", "C"),
("B", "D"),
("B", "E"),
("C", "E"),
("C", "F"),
("D", "E"),
("E", "F"),
("E", "G"),
("F", "G")
]
for x, y in CONSTRAINTS:
problem.addConstraint(lambda x, y: x != y, (x, y))
# Solve problem
for solution in problem.getSolutions():
print(solution)Quiz
对于以下哪一项，即使多次重新运行算法，也会始终找到相同的解决方案？ 假设一个问题的目标是最小化成本函数，并且状态空间中的每个状态都有不同的成本。
- 最陡爬山，每次从不同的初始状态开始
- 最陡爬山，每次都从相同的初始状态开始
- 随机爬山，每次从不同的初始状态开始
- 随机爬山，每次都从相同的初始状态开始
- 无论是 最陡爬山 还是 随机爬山，只要你总是从同一个初始状态开始
- 无论是 最陡爬山 还是 随机爬山，只要每次都从不同的初始状态开始
- 没有任何版本的爬山算法能保证每次都能得到相同的解决方案
答案：最陡爬山，每次都从相同的初始状态开始
下面两个问题都会问你关于下面描述的优化问题。 一位农民正在尝试种植两种作物，
作物 1和作物 2，并希望实现利润最大化。农民将从种植的每英亩作物 1中获得 500 美元的利润，从种植的每英亩作物 2中获得 400 美元的利润。然而，农民今天需要在早上 7 点到晚上 7 点之间的 12 个小时内完成所有的种植。种植一英亩的作物 1需要 3 个小时，种植一英亩作物 2需要 2 个小时。农民在供应方面也很有限：他有足够的供应种植 10 英亩的作物 1，有足够的资源种植 4 英亩的作物 2。假设变量 C1 表示要种植的作物 1的英亩数，变量 C2 表示要种植作物 2的英亩数。对于这个问题，什么是有效的目标函数？
- 10 * C1 + 4 * C2
- -3 * C1 - 2 * C2
- 500 * 10 * C1 + 400 * 4 * C2
- 500 * C1 + 400 * C2
- C1 + C2
答案：500 * C1 + 400 * C2
这个问题的制约因素是什么？
- 3 * C1 + 2 * C2 <= 12, C1 <= 10, C2 <= 4
- 3 * C1 + 2 * C2 <= 12, C1 + C2 <= 14
- 3 * C1 <= 10, 2 * C2 <= 4
- C1 + C2 <= 12, C1 + C2 <= 14
答案：3 * C1 + 2 * C2 <= 12, C1 <= 10, C2 <= 4
4. 下面的问题将问你以下考试安排约束满足图，其中每个节点代表一个课程。每门课程都与可能的考试日的初始域相关联（大多数课程可能在周一、周二或周三；少数课程已经被限制在一天内）。两个节点之间的边意味着这两个课程必须在不同的日子进行考试。
在对整个问题满足弧一致性之后，变量 C、D 和 E 的结果域是什么？
- C 的域是 {Mon，Tue}，D 的域是 {Wed}，E 的域是 {Mon}
- C 的域是 {Mon}，D 的域是 {Wed}，E 的域为 {Tue}
- C 的域是 {Mon}，D 的域是 {Tue}，E 的域为 {Wed}
- C 的域是 {Mon}，D 的域是 {Mon，Wed}，E 的域是 {Tue，Wed}
- C 的域是 {Mon，Tue，Wed}，D 的域是 {Mon，Wed}，E 的域是 {Mon，Tue，Wed}
- C 的域是 {Mon}，D 的域是 {Mon，Wed}，E 的域是 {Mon，Tue，Wed}
答案：C 的域是 {Mon}，D 的域是 {Mon，Wed}，E 的域是 {Tue，Wed}