带增益建筑的网格建筑布局优化算法及实现方案问询

核心思路 #

针对有限连通网格的建筑布局优化问题，目标是最大化指定生产类型的总产量（含增益建筑加成），核心是放弃全排列暴力枚举，采用分层优化策略：

1. 问题建模 #

• 将网格抽象为二进制矩阵：0代表空闲格，1代表已占用格
• 给每个建筑定义核心属性：
  • 常规建筑：占用矩阵（如2x2的1矩阵）、基础产量值
  • 增益建筑：占用矩阵、影响范围（曼哈顿/欧氏距离）、增益系数（上限100%）
• 目标函数：指定类型建筑的总基础产量 × (1 + 覆盖该建筑的所有增益系数之和，超过100%则按100%计算)

2. 高效优化策略 #

• 贪心预初始化：优先放置高性价比建筑（单位格子产量最高的常规建筑，或覆盖范围广、增益系数高的特殊建筑），快速生成合格初始布局
• 模拟退火局部搜索：基于初始布局，通过随机调整（移动/替换/移除建筑）跳出局部最优，用温度参数控制接受次优解的概率，逐步收敛到全局最优
• 约束前置校验：提前生成网格的可放置掩码（标记连通区域内的可用格子），放置建筑时直接校验是否落在掩码范围内，减少无效尝试

3. 不规则网格适配 #

• 预处理生成可放置区域掩码矩阵，标记所有合法的空闲格子
• 放置建筑时，仅遍历掩码内的坐标，确保建筑完全落在连通网格范围内，不越界、不重叠

代码示例（Python） #

import random
import numpy as np

# 建筑类定义
class Building:
    def __init__(self, type_tag, shape, prod_value=0, boost_range=0, boost_ratio=0):
        self.type_tag = type_tag  # 生产类型：如'A'/'Boost'
        self.shape = shape  # 建筑尺寸：(高,宽)
        self.prod_value = prod_value  # 常规建筑基础产量
        self.boost_range = boost_range  # 增益建筑影响范围（曼哈顿距离）
        self.boost_ratio = boost_ratio  # 增益比例（0~1）

# 生成网格可放置掩码（处理连通/不规则网格）
def create_grid_mask(grid_size, blocked_cells):
    mask = np.ones(grid_size, dtype=int)
    for (x, y) in blocked_cells:
        mask[x][y] = 0
    return mask

# 校验建筑是否可放置在指定位置
def is_placeable(grid, mask, building, pos):
    x, y = pos
    h, w = building.shape
    # 检查是否越界
    if x + h > grid.shape[0] or y + w > grid.shape[1]:
        return False
    # 检查是否落在可放置区域且未被占用
    for i in range(h):
        for j in range(w):
            if mask[x+i][y+j] == 0 or grid[x+i][y+j] != 0:
                return False
    return True

# 计算当前布局的总收益（针对指定生产类型）
def calculate_total_profit(grid, placed_buildings, target_type):
    total = 0
    boost_map = np.zeros(grid.shape)  # 记录每个格子的总增益比例

    # 先统计所有增益建筑的影响范围
    for pos, b in placed_buildings:
        if b.boost_ratio > 0:
            x, y = pos
            h, w = b.shape
            center_x, center_y = x + h//2, y + w//2
            # 遍历范围内所有格子
            for i in range(max(0, center_x - b.boost_range), min(grid.shape[0], center_x + b.boost_range + 1)):
                for j in range(max(0, center_y - b.boost_range), min(grid.shape[1], center_y + b.boost_range + 1)):
                    if abs(i - center_x) + abs(j - center_y) <= b.boost_range:
                        boost_map[i][j] = min(1.0, boost_map[i][j] + b.boost_ratio)

    # 统计目标类型建筑的产量
    for pos, b in placed_buildings:
        if b.type_tag == target_type:
            x, y = pos
            h, w = b.shape
            center_x, center_y = x + h//2, y + w//2
            total += b.prod_value * (1 + boost_map[center_x][center_y])

    return total

# 模拟退火优化布局
def optimize_layout(grid_mask, target_type, building_pool, max_iter=1000, init_temp=100.0, cool_rate=0.95):
    grid = np.zeros(grid_mask.shape, dtype=int)
    placed = []
    temp = init_temp

    # 贪心生成初始布局：优先放高性价比建筑
    sorted_buildings = sorted(
        building_pool,
        key=lambda b: (b.prod_value / (b.shape[0]*b.shape[1])) if b.prod_value > 0 else (b.boost_ratio * b.boost_range),
        reverse=True
    )
    for b in sorted_buildings:
        valid_pos = []
        for x in range(grid_mask.shape[0] - b.shape[0] + 1):
            for y in range(grid_mask.shape[1] - b.shape[1] + 1):
                if is_placeable(grid, grid_mask, b, (x, y)):
                    valid_pos.append((x, y))
        if valid_pos:
            pos = random.choice(valid_pos)
            placed.append((pos, b))
            x, y = pos
            h, w = b.shape
            grid[x:x+h, y:y+w] = 1

    current_profit = calculate_total_profit(grid, placed, target_type)

    for _ in range(max_iter):
        if temp < 1e-3:
            break

        # 随机选择调整操作
        op = random.choice(['move', 'replace', 'remove'])
        new_placed = placed.copy()
        new_grid = grid.copy()

        if op == 'move' and placed:
            idx = random.randint(0, len(placed)-1)
            old_pos, b = placed[idx]
            # 清除旧位置占用
            x, y = old_pos
            h, w = b.shape
            new_grid[x:x+h, y:y+w] = 0
            # 寻找新的合法位置
            valid_pos = []
            for nx in range(grid_mask.shape[0] - b.shape[0] + 1):
                for ny in range(grid_mask.shape[1] - b.shape[1] + 1):
                    if is_placeable(new_grid, grid_mask, b, (nx, ny)):
                        valid_pos.append((nx, ny))
            if valid_pos:
                new_pos = random.choice(valid_pos)
                new_placed[idx] = (new_pos, b)
                nx, ny = new_pos
                new_grid[nx:nx+h, ny:ny+w] = 1

        elif op == 'replace' and placed and len(building_pool) > 1:
            idx = random.randint(0, len(placed)-1)
            old_pos, old_b = placed[idx]
            x, y = old_pos
            h, w = old_b.shape
            new_grid[x:x+h, y:y+w] = 0
            # 选择同尺寸的其他建筑替换
            candidates = [b for b in building_pool if b.shape == old_b.shape]
            if candidates:
                new_b = random.choice(candidates)
                if is_placeable(new_grid, grid_mask, new_b, (x, y)):
                    new_placed[idx] = ((x, y), new_b)
                    new_grid[x:x+h, y:y+w] = 1

        elif op == 'remove' and placed:
            idx = random.randint(0, len(placed)-1)
            old_pos, old_b = placed[idx]
            x, y = old_pos
            h, w = old_b.shape
            new_grid[x:x+h, y:y+w] = 0
            del new_placed[idx]

        # 计算新收益并决定是否接受
        new_profit = calculate_total_profit(new_grid, new_placed, target_type)
        delta = new_profit - current_profit
        if delta > 0 or random.random() < np.exp(delta / temp):
            grid = new_grid
            placed = new_placed
            current_profit = new_profit

        temp *= cool_rate

    return placed, current_profit

# 示例调用
if __name__ == "__main__":
    # 5x5网格，中间(2,2)不可用（模拟非矩形连通网格）
    grid_mask = create_grid_mask((5,5), [(2,2)])
    # 建筑池：2个A类生产建筑，2个增益建筑
    building_pool = [
        Building('A', (2,2), prod_value=10),
        Building('A', (2,2), prod_value=10),
        Building('Boost', (1,1), boost_range=2, boost_ratio=0.3),
        Building('Boost', (1,1), boost_range=2, boost_ratio=0.3)
    ]
    # 优化A类建筑的布局收益
    best_layout, best_profit = optimize_layout(grid_mask, 'A', building_pool)
    print(f"最优收益: {best_profit:.2f}")
    print("布局详情:")
    for pos, b in best_layout:
        print(f"[{b.type_tag}] 位置: {pos}")

关键优化说明 #

• 规避全排列低效：通过贪心初始化+模拟退火，将时间复杂度从阶乘级降到线性迭代级，大幅减少计算量
• 网格适配性：用掩码矩阵兼容任意连通网格，放置前的合法性校验确保布局符合网格边界约束
• 增益计算优化：预先生成全局增益地图，避免重复遍历建筑，提升收益计算效率

内容的提问来源于stack exchange，提问作者Jakub Sapko