程序示例

TIP

阅读程序并运行

完成习题

📥

本节附件下载

Hospital (局部搜索)

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 (线性规划)

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 (约束满足)

"""没有任何启发式或推理的自然回溯搜索"""
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 库

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. 对于以下哪一项，即使多次重新运行算法，也会始终找到相同的解决方案？ 假设一个问题的目标是最小化成本函数，并且状态空间中的每个状态都有不同的成本。

   1. Steepest-ascent hill-climbing，每次从不同的初始状态开始
   2. Steepest-ascent hill-climbing，每次都从相同的初始状态开始
   3. Stochastic hill-climbing，每次从不同的初始状态开始
   4. Stochastic hill-climbing，每次都从相同的初始状态开始
   5. 无论是 steepest-ascent 还是 stochastic hill climbing，只要你总是从同一个初始状态开始
   6. 无论是 steepest-ascent 还是 stochastic hill climbing，只要每次都从不同的初始状态开始
   7. 没有任何版本的爬山算法能保证每次都能得到相同的解决方案

2. 下面两个问题都会问你关于下面描述的优化问题。 一位农民正在尝试种植两种作物， 作物 1 和 作物 2 ，并希望实现利润最大化。农民将从种植的每英亩 作物 1 中获得 500 美元的利润，从种植的每英亩 作物 2 中获得 400 美元的利润。然而，农民今天需要在早上 7 点到晚上 7 点之间的 12 个小时内完成所有的种植。种植一英亩的 作物 1 需要 3 个小时，种植一英亩 作物 2 需要 2 个小时。农民在供应方面也很有限：他有足够的供应种植 10 英亩的 作物 1 ，有足够的资源种植 4 英亩的 作物 2 。假设变量 C1 表示要种植的 作物 1 的英亩数，变量 C2 表示要种植 作物 2 的英亩数。

   对于这个问题，什么是有效的目标函数？

   1. 10 * C1 + 4 * C2
   2. -3 * C1 - 2 * C2
   3. 500 * 10 * C1 + 400 * 4 * C2
   4. 500 * C1 + 400 * C2
   5. C1 + C2

3. 这个问题的制约因素是什么？

   1. 3 * C1 + 2 * C2 <= 12, C1 <= 10, C2 <= 4
   2. 3 * C1 + 2 * C2 <= 12, C1 + C2 <= 14
   3. 3 * C1 <= 10, 2 * C2 <= 4
   4. C1 + C2 <= 12, C1 + C2 <= 14

4. 下面的问题将问你以下考试安排约束满足图，其中每个节点代表一个课程。每门课程都与可能的考试日的初始域相关联（大多数课程可能在周一、周二或周三；少数课程已经被限制在一天内）。两个节点之间的边意味着这两个课程必须在不同的日子进行考试。

   在对整个问题满足弧一致性之后，变量 C、D 和 E 的结果域是什么？

   1. C 的域是 {Mon，Tue}，D 的域是 {Wed}，E 的域是 {Mon}
   2. C 的域是 {Mon}，D 的域是 {Wed}，E 的域为 {Tue}
   3. C 的域是 {Mon}，D 的域是 {Tue}，E 的域为 {Wed}
   4. C 的域是 {Mon}，D 的域是 {Mon，Wed}，E 的域是 {Tue，Wed}
   5. C 的域是 {Mon，Tue，Wed}，D 的域是 {Mon，Wed}，E 的域是 {Mon，Tue，Wed}
   6. C 的域是 {Mon}，D 的域是 {Mon，Wed}，E 的域是 {Mon，Tue，Wed}