接上一篇新手实录(forum.php?mod=viewthread&tid=3534)。有朋友问我"从题目图里提取边集"具体怎么做的,这篇把过程展开成可复现的步骤。全部代码在本地 Python 3.13 + numpy + Pillow 上验证通过。

一、为什么要从图片提边
新手教程的题目给的是一张 PNG 示意图:10 个浅蓝色圆圈节点、黑色线段连边。平台没有给结构化的边列表,想穷举就得先把图"读"出来。手工抄容易漏,尤其是这种十来个节点、二十多条边的密图,所以值得用脚本做。

二、四步流程
第 1 步,定位节点:节点圆是浅蓝色(高 B、中 G、低 R),用颜色掩膜 + 简单聚类得到 10 个圆心坐标。
第 2 步,给节点编号:把每个圆心周围裁个小图拼成一张核对图,人工确认"坐标→编号"的映射。这一步千万别省,映射错一个,后面全错。
第 3 步,判定边:对全部 C(10,2)=45 个点对,沿两端圆心之间的线段等距采样,查 3×3 邻域内是否存在暗像素(线是深灰,阈值取 140),两端半径 24px 内的采样点跳过以避开圆环。统计暗点占比:真边都在 0.75 以上,非边都在 0.3 以下,本图没有中间地带,阈值很好取。
第 4 步,自检 + 求解:自检用度数和=2×边数(本图 46=2×23 ✓);再把检出的边画回原图叠加目视复核。最后固定顶点 0,枚举其余 9 个顶点 512 种分组,得最大割 19。

三、核心代码(约 40 行)

1. import numpy as np
   
2. from PIL import Image
   
3. 
   
4. img = np.array(Image.open('tutorial_subject.png').convert('RGB')).astype(int)
   
5. lum = img.mean(2)
   
6. nodes = {0:(584,240), 1:(534,117), 2:(402,42), 3:(238,42), 4:(106,117),
   
7.          5:(56,240), 6:(106,363), 7:(238,438), 8:(402,438), 9:(534,363)}
   
8. keys = sorted(nodes); R = 24
   
9. 
   
10. def edge_ratio(a, b):
    
11.     ax, ay = nodes[a]; bx, by = nodes[b]
    
12.     n = int(np.hypot(bx-ax, by-ay)); dark = total = 0
    
13.     for t in np.linspace(0, 1, n):
    
14.         x = ax + (bx-ax)*t; y = ay + (by-ay)*t
    
15.         if np.hypot(x-ax, y-ay) < R or np.hypot(x-bx, y-by) < R: continue
    
16.         xi, yi = int(round(x)), int(round(y))
    
17.         patch = lum[max(0,yi-1):yi+2, max(0,xi-1):xi+2]
    
18.         total += 1; dark += (patch.min() < 140)
    
19.     return dark / max(total, 1)
    
20. 
    
21. edges = [(a,b) for i,a in enumerate(keys) for b in keys[i+1:] if edge_ratio(a,b) > 0.75]
    
22. print(len(edges), edges)  # 23 条

复制代码

四、两点经验
1. 阈值检验比阈值本身重要:命中率出现"两极分化、中间空白"时,说明检测结果可靠;如果大量点对落在 0.3~0.75 之间,就要怀疑有漏检或抗锯齿干扰,先别往下走。
2. 把边画回原图叠一遍是最便宜的验证,比盯数字看靠谱得多。

五、从穷举到 Ising
穷举只是起点。同一个问题写成 Ising 形式(σi∈{±1},Z=Σ wij(1-σiσj)/2),就可以交给 Kaiwu SDK 的 SA 采样器或 CIM 真机去解——10 个节点体会不到差距,但按官方文档的说法,规模上去之后经典启发式和专用量子计算的分工就出来了。这也是我下一步打算试的:把这份边表转成 Ising 矩阵,先用 SimulatedAnnealingOptimizer 跑个基线,再对照 PrecisionReducer 降精度后的结果差异。有结果再来发帖。

接上一篇新手实录(forum.php?mod=viewthread&tid=3534)。有朋友问我"从题目图里提取边集"具体怎么做的,这篇把过程展开成可复现的步骤。全部代码在本地 Python 3.13 + numpy + Pillow 上验证通过。

一、为什么要从图片提边
新手教程的题目给的是一张 PNG 示意图:10 个浅蓝色圆圈节点、黑色线段连边。平台没有给结构化的边列表,想穷举就得先把图"读"出来。手工抄容易漏,尤其是这种十来个节点、二十多条边的密图,所以值得用脚本做。

二、四步流程
第 1 步,定位节点:节点圆是浅蓝色(高 B、中 G、低 R),用颜色掩膜 + 简单聚类得到 10 个圆心坐标。
第 2 步,给节点编号:把每个圆心周围裁个小图拼成一张核对图,人工确认"坐标→编号"的映射。这一步千万别省,映射错一个,后面全错。
第 3 步,判定边:对全部 C(10,2)=45 个点对,沿两端圆心之间的线段等距采样,查 3×3 邻域内是否存在暗像素(线是深灰,阈值取 140),两端半径 24px 内的采样点跳过以避开圆环。统计暗点占比:真边都在 0.75 以上,非边都在 0.3 以下,本图没有中间地带,阈值很好取。
第 4 步,自检 + 求解:自检用度数和=2×边数(本图 46=2×23 ✓);再把检出的边画回原图叠加目视复核。最后固定顶点 0,枚举其余 9 个顶点 512 种分组,得最大割 19。

三、核心代码(约 40 行)

1. import numpy as np
   
2. from PIL import Image
   
3. 
   
4. img = np.array(Image.open('tutorial_subject.png').convert('RGB')).astype(int)
   
5. lum = img.mean(2)
   
6. nodes = {0:(584,240), 1:(534,117), 2:(402,42), 3:(238,42), 4:(106,117),
   
7.          5:(56,240), 6:(106,363), 7:(238,438), 8:(402,438), 9:(534,363)}
   
8. keys = sorted(nodes); R = 24
   
9. 
   
10. def edge_ratio(a, b):
    
11.     ax, ay = nodes[a]; bx, by = nodes[b]
    
12.     n = int(np.hypot(bx-ax, by-ay)); dark = total = 0
    
13.     for t in np.linspace(0, 1, n):
    
14.         x = ax + (bx-ax)*t; y = ay + (by-ay)*t
    
15.         if np.hypot(x-ax, y-ay) < R or np.hypot(x-bx, y-by) < R: continue
    
16.         xi, yi = int(round(x)), int(round(y))
    
17.         patch = lum[max(0,yi-1):yi+2, max(0,xi-1):xi+2]
    
18.         total += 1; dark += (patch.min() < 140)
    
19.     return dark / max(total, 1)
    
20. 
    
21. edges = [(a,b) for i,a in enumerate(keys) for b in keys[i+1:] if edge_ratio(a,b) > 0.75]
    
22. print(len(edges), edges)  # 23 条

复制代码

四、两点经验
1. 阈值检验比阈值本身重要:命中率出现"两极分化、中间空白"时,说明检测结果可靠;如果大量点对落在 0.3~0.75 之间,就要怀疑有漏检或抗锯齿干扰,先别往下走。
2. 把边画回原图叠一遍是最便宜的验证,比盯数字看靠谱得多。

五、从穷举到 Ising
穷举只是起点。同一个问题写成 Ising 形式(σi∈{±1},Z=Σ wij(1-σiσj)/2),就可以交给 Kaiwu SDK 的 SA 采样器或 CIM 真机去解——10 个节点体会不到差距,但按官方文档的说法,规模上去之后经典启发式和专用量子计算的分工就出来了。这也是我下一步打算试的:把这份边表转成 Ising 矩阵,先用 SimulatedAnnealingOptimizer 跑个基线,再对照 PrecisionReducer 降精度后的结果差异。有结果再来发帖。