PythonAI算法
全球校园人工智能算法精英大赛碳中和优化题解析
本文针对全球校园人工智能算法精英大赛中的碳中和优化问题进行分析。该问题属于带约束的多维度资源分配优化问题，核心是在满足服务器功耗和热量传导限制下最大化总收益。主要解决方案包括贪心策略、多策略混合以及模拟退火算法。文章提供了详细的输入输出格式、评分机制及代码实现示例，帮助参赛者理解题目约束并构建高效算法。
本文针对全球校园人工智能算法精英大赛中的碳中和优化问题进行分析。该问题属于带约束的多维度资源分配优化问题，核心是在满足服务器功耗和热量传导限制下最大化总收益。主要解决方案包括贪心策略、多策略混合以及模拟退火算法。文章提供了详细的输入输出格式、评分机制及代码实现示例，帮助参赛者理解题目约束并构建高效算法。
'全球校园人工智能算法精英大赛'是江苏省人工智能学会举办的面向全球具有正式学籍的全日制高等院校及以上在校学生举办的算法竞赛。其中的算法巅峰赛属于产业命题赛道，这是第 3 赛季，这次优化题的主题是'碳中和'。
给你 N 个任务和 M 台服务器，需要决定：
热量计算方式： 服务器 p 承受的热量 = 服务器 p 任务的热量总和 + 左邻热量和 × K + 右邻热量和 × K 注：左右两侧服务器的特殊情况，非环，且没有传递性。
在满足所有限制条件下，最大化总收益。
第一行
N M K
N：任务数量（1-4000） M：服务器数量（1-800） K：热量传导系数（0.0-1.0）
任务数据（N 行，每行 3 个数字）
收益 功耗 热量
服务器数据（M 行，每行 2 个数字）
功耗上限 热量阈值
a_1, a_2, a_3, …, a_n
其中 $a_i \in [0, M]$，0: 该任务 i 不执行，1-M: 该任务 i 分配到几号服务器。
输入
3 2 1.0 10 3 4 8 4 3 5 2 2 5 7 7 8
输出
1 2 0
该问题属于带约束的多维度资源分配优化问题，是组合优化问题。
该问题可以视为二维费用的 0-1 多重背包的变形问题。
# task 按收益从高到低排序
tasks.sort(key=lambda x: -x.val)
# 遍历每个任务
for task in tasks:
for server in servers:
# 如果该服务器，添加该任务后，依旧满足约束
if server.satisfy(task):
# 该 task 被赋予给 该 server
task -> server
break
保留原先的贪心策略主框架，做一些策略抽象。
sort_strategy # 排序策略
choice_strategy # 挑选策略
# task 按 策略 sort_strategy 排序
tasks.sort(key=sort_strategy)
# 遍历每个任务
for task in tasks:
candidate_list = []
for server in servers:
# 如果该服务器，添加该任务后，依旧满足约束
if server.satisfy(task):
candidate_list.append(server)
# 如果存在候选服务器列表
if candidate_list:
# 按挑选策略，选择具体的 svr
svr = choice_strategy(candidate_list)
task -> svr
这里抽象了 2 个策略，sort_strategy / choice_strategy。
任务的排序策略
服务器的挑选策略
而任务的排序策略 + 服务器的挑选策略，做一个组合搭配。 取排序策略 N 种，服务器挑选策略 M 种，做 N*M 的组合，取最优结果为最后的构造解。
如选择排序策略 3 种 * 挑选策略 FF+RF，混合策略效果较好。 这边都是以任务 task 为主导，实际上以服务器 server 为主导，也是类似的效果。
模拟退火也可以做这题，但操作因子设计就很复杂，不太好实现。
这边以最简单的任务重分配操作因子 为例（纯展示）。
import math, random
from math import inf
class Task(object):
def __init__(self, value, power, heat):
self.value = value
self.power = power
self.heat = heat
class Server(object):
def __init__(self, p_limit, h_limit):
self.p_limit = p_limit
self.h_limit = h_limit
N, M, K = input().split()
N, M, K = int(N), int(M), float(K)
tasks = []
for _ in range(N):
value, power, heat = list(map(int, input().split()))
tasks.append(Task(value, power, heat))
servers = []
for _ in range(M):
p_limit, h_limit = list(map(int, input().split()))
servers.append(Server(p_limit, h_limit))
def fitness(assigns):
ans = 0
tmp_power = [0] * M
tmp_heat = [0] * M
for i in range(N):
id = assigns[i]
if id >= :
tmp_power[] += tasks[i].power
tmp_heat[] += tasks[i].heat
ans += tasks[i].value
i (M):
tmp_power[i] > servers[i].p_limit:
-inf
heat = tmp_heat[i]
i > :
heat += tmp_heat[i - ] * K
i + < M:
heat += tmp_heat[i + ] * K
heat > servers[i].h_limit:
-inf
ans
assigns = [-] * N
current_score =
best_score =
best_ans = assigns[:]
a =
T =
T > :
idx = random.randint(, N - )
old = assigns[idx]
assigns[idx] = random.randint(-, M - )
score = fitness(assigns)
score == -inf:
assigns[idx] = old
T = T * a
delta = score - current_score
delta > random.random() < math.exp(delta / T):
current_score = score
current_score > best_score:
best_score = current_score
best_ans = assigns[:]
:
assigns[idx] = old
T = T * a
(*[v + v best_ans])
这个大概可以拿 300+ 分。 这个操作因子，效率太低了，间接反映了比赛实际的数据相对较弱，容易得分。 具体更有效率的操作因子，可参考相关 AI 大模型建议。
这个数据其实挺难构造的，如何任务和服务器的配对不对，很容易变成没有区分度的 case。
比赛的数据，感觉有些松，使得得分的差异其实并不是那么明显。
实际造的数据，是按任务数/服务器数，[1/20~1/5] 之间配比，任务数量覆盖 [10, 4000]，服务器数覆盖 [2, 800]。
考虑到这题左右侧热量限制，很容易导致 0 分。所以不知道是不是因为这个，主委会给这题特殊的打分机制，即合理解 (全 0 是个特殊的合理解）有一个基础分。
| 数据 | case 1 | case 2 | case 3 | case 4 | case 5 | case 6 | case 7 | case 8 | case 9 | case 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 权重分 | 10 | 20 | 20 | 30 | 30 | 30 | 40 | 45 | 55 | 70 |
| 基础分 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 | 13 | 14 |
$$score_i = \begin{cases} \text{结果收益}_i / \text{基准收益}_i \times \text{权重分}_i + \text{基础分}_i, & \text{构造解合理} \ 0, & \text{构造解不合理} \end{cases}$$
最后总分为 $\sum score_i$。
基准测试
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online