基于Python的网格树叶概率扩散集中优化算法问询

一、核心模拟逻辑实现 #

首先实现符合规则的吹风操作模拟，用NumPy数组存储网格状态以高效计算：

规则明确 #

从方格A(x,y)吹向指定方向时：

1. A的所有树叶按80%到目标方格B、10%到B的垂直左侧、10%到B的垂直右侧分配，A树叶清零。
2. 吹风前B的10%树叶被吹到B的反方向（吹风方向的后方），剩余90%保留在B。

模拟代码 #

import numpy as np

def simulate_blow(grid, start, direction):
    """
    执行一次吹风操作并返回新网格状态
    :param grid: 二维numpy数组，当前树叶分布
    :param start: 吹风起点坐标(x, y)
    :param direction: 吹风方向，可选('up', 'down', 'left', 'right')
    :return: 操作后的网格数组
    """
    n = grid.shape[0]
    new_grid = grid.copy()
    x, y = start

    dir_map = {
        'up': (-1, 0),
        'down': (1, 0),
        'left': (0, -1),
        'right': (0, 1)
    }
    dx, dy = dir_map[direction]
    target = (x + dx, y + dy)

    # 跳过目标超出网格的非法操作
    if not (0 <= target[0] < n and 0 <= target[1] < n):
        return new_grid

    # 处理起点A的树叶分配
    a_leaves = grid[start]
    new_grid[target] += 0.8 * a_leaves
    # 分配到B的左侧（垂直于吹风方向）
    left_offset = (-dy, dx)
    left_pos = (target[0] + left_offset[0], target[1] + left_offset[1])
    if 0 <= left_pos[0] < n and 0 <= left_pos[1] < n:
        new_grid[left_pos] += 0.1 * a_leaves
    # 分配到B的右侧（垂直于吹风方向）
    right_offset = (dy, -dx)
    right_pos = (target[0] + right_offset[0], target[1] + right_offset[1])
    if 0 <= right_pos[0] < n and 0 <= right_pos[1] < n:
        new_grid[right_pos] += 0.1 * a_leaves
    new_grid[start] = 0

    # 处理目标B的10%树叶吹向后方
    b_initial = grid[target]
    back_offset = (-dx, -dy)
    back_pos = (target[0] + back_offset[0], target[1] + back_offset[1])
    if 0 <= back_pos[0] < n and 0 <= back_pos[1] < n:
        new_grid[back_pos] += 0.1 * b_initial
    new_grid[target] -= 0.1 * b_initial

    return new_grid

二、优化操作序列的算法方案 #

随机操作会导致树叶扩散稀释，以下是几种系统化优化策略：

1. 贪心算法（简单高效） #

每次选择能让目标方格Q树叶增量最大的操作，适合中等规模网格：

def greedy_maximize(n, target_q, max_steps=150):
    """
    用贪心算法最大化目标Q的树叶数量
    :param n: 网格大小n×n
    :param target_q: 目标方格坐标(Qx, Qy)
    :param max_steps: 最大操作次数
    :return: 最终网格状态、目标Q的树叶数量
    """
    grid = np.full((n, n), 100.0)
    qx, qy = target_q

    for _ in range(max_steps):
        best_gain = -float('inf')
        best_operation = None

        # 遍历所有合法操作
        for x in range(n):
            for y in range(n):
                if x == qx and y == qy:
                    continue  # 不对Q吹风，避免损失
                for dir in ['up', 'down', 'left', 'right']:
                    temp_grid = simulate_blow(grid, (x, y), dir)
                    current_gain = temp_grid[qx][qy] - grid[qx][qy]
                    if current_gain > best_gain:
                        best_gain = current_gain
                        best_operation = ((x, y), dir)

        # 执行最优操作，无增益则终止
        if best_operation and best_gain > 0:
            grid = simulate_blow(grid, best_operation[0], best_operation[1])
        else:
            break

    return grid, grid[qx][qy]

2. 分层收敛策略（减少扩散损失） #

将网格按与Q的曼哈顿距离分层，从最外层开始逐层推送树叶：

• 最外层格子优先选择朝向Q的吹风操作，引导树叶向内流动
• 内层格子直接吹向Q，最大化80%的直达比例
• 避免对Q周边格子反向吹风，减少树叶回流

3. 遗传算法（全局最优搜索） #

针对大规模网格或长操作序列，遗传算法可跳出局部最优：

• 染色体编码：用列表存储操作序列，每个元素为(起点坐标, 方向)
• 适应度函数：执行序列后Q的树叶数量
• 进化操作：选择高适应度序列交叉，随机变异部分操作，迭代优化

三、关键注意事项 #

• 禁止对目标Q执行吹风操作，否则会损失10%树叶到后方，回收成本远高于损失
• 优先选择朝向Q的吹风方向，减少树叶向无关区域扩散
• 当没有操作能提升Q的树叶数量时，提前终止操作，避免无效扩散

内容的提问来源于stack exchange，提问作者Wismar Günther