先找独立集，再选择算法¶
从三个节点组成的路径图 a — b — c 开始。独立集中，任意两个节点之间都没有边；最大独立集（MIS）则是在所有独立集中节点数最多的集合。这节课先定义图、解读候选位串，再穷举全部八个位串，得到一个经典参考答案。
需要完成安装，并能阅读 Python 字典。本课不运行量子模拟或变分优化器。读候选位串时，可以参照位序基础。
明确每一位表示什么¶
图中明确给出了 (a, b) 和 (b, c) 两条边，记录的变量顺序为 ["a", "b", "c"]。按这个顺序，101 选择 a 和 c，110 选择 a 和 b，只有前者是独立集。
位置 0、5、10 um 是几何信息。GraphProblemIR.from_edges 使用传入的边，不会另外推断一组边，也不能据此判断某个物理相互作用能否精确实现这张图。先明确优化问题，再研究物理映射。
运行前预测最大的可行集合，以及答案是否唯一。再找一个“极大但非最大”的独立集：极大表示不能再加入节点而保持可行，最大表示节点数已经达到全局最优。
解读候选并穷举¶
"""描述一个小型图优化问题，并解码候选 bitstring。
程序先固定图的节点顺序、位置和边，再解码一个独立集候选；此时不会运行变分
优化器。把问题数据单独列出，后续解释 QAOA 结果时才不会混入硬件 placement 假设。
"""
from __future__ import annotations
import json
from cascaqit.problems import GraphProblemIR, decode_graph_bitstring
def main() -> None:
"""创建一个路径图并解码一个独立集候选。"""
# Positions 是显式的问题事实，不能把它们当作自动推导的硬件 placement。
graph = GraphProblemIR.from_edges(
problem_id="lesson.optimization.beginner",
positions={"a": (0.0, 0.0), "b": (5.0, 0.0), "c": (10.0, 0.0)},
edges=(("a", "b"), ("b", "c")),
)
# 候选解必须使用 graph 冻结后的变量顺序。
decoded = decode_graph_bitstring(graph, "101")
candidates = [decode_graph_bitstring(graph, f"{value:03b}") for value in range(8)]
feasible = [item for item in candidates if item["is_independent"]]
maximum_size = max(item["selection_size"] for item in feasible)
payload = {
"track": "optimization_researcher",
"level": "beginner",
"lesson": "graph_problem",
"facts": {
"node_order": list(graph.nodes),
"edges": [list(edge) for edge in graph.edges],
"bitstring": decoded["bitstring"],
"selected_nodes": list(decoded["selected_nodes"]),
"feasible": decoded["is_independent"],
"candidates": [
{
"bitstring": item["bitstring"],
"size": item["selection_size"],
"feasible": item["is_independent"],
"violating_edges": item["violating_edges"],
}
for item in candidates
],
"maximum_independent_set_size": maximum_size,
"optimal_bitstrings": [
item["bitstring"]
for item in feasible
if item["selection_size"] == maximum_size
],
},
"boundaries": {
"hardware_execution": False,
"cloud_execution": False,
"network_accessed": False,
"credentials_loaded": False,
},
}
print(json.dumps(payload, sort_keys=True))
if __name__ == "__main__":
main()
python3 examples/user/tracks/optimization_researcher/01_beginner_graph_problem_zh.py
{
"boundaries": {
"cloud_execution": false,
"credentials_loaded": false,
"hardware_execution": false,
"network_accessed": false
},
"facts": {
"bitstring": "101",
"candidates": [
{
"bitstring": "000",
"feasible": true,
"size": 0,
"violating_edges": []
},
{
"bitstring": "001",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "010",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "011",
"feasible": false,
"size": 2,
"violating_edges": [
[
"b",
"c"
]
]
},
{
"bitstring": "100",
"feasible": true,
"size": 1,
"violating_edges": []
},
{
"bitstring": "101",
"feasible": true,
"size": 2,
"violating_edges": []
},
{
"bitstring": "110",
"feasible": false,
"size": 2,
"violating_edges": [
[
"a",
"b"
]
]
},
{
"bitstring": "111",
"feasible": false,
"size": 3,
"violating_edges": [
[
"a",
"b"
],
[
"b",
"c"
]
]
}
],
"edges": [
[
"a",
"b"
],
[
"b",
"c"
]
],
"feasible": true,
"maximum_independent_set_size": 2,
"node_order": [
"a",
"b",
"c"
],
"optimal_bitstrings": [
"101"
],
"selected_nodes": [
"a",
"c"
]
},
"lesson": "graph_problem",
"level": "beginner",
"track": "optimization_researcher"
}
把 candidates 当作候选解表来读。八个位串中，五个对应独立集。101 是唯一大小为 2 的可行集合，因此 maximum_independent_set_size 为 2，optimal_bitstrings 为 ["101"]。010 是极大独立集，因为剩下两个节点都与 b 相邻，但它不是最大独立集。
111 虽然选择了三个节点，却违反两条边约束。只数节点、不检查 feasible，就会把无效解当成最优解。解码函数负责说明一个位串的含义，不负责搜索最优解；这里的穷举循环才给出了完整参考。
写清要比较的目标函数¶
一种最小化代价可以写成 E(x) = −(x_a + x_b + x_c) + λ(x_a x_b + x_b x_c)。第一项鼓励选择节点，第二项惩罚相邻节点同时被选中。本练习取 λ = 2，可算得 E(101) = −2、E(110) = 0、E(111) = 1。
这个式子是手算练习，不是脚本额外返回的字段，也不代表所有编译器的默认罚系数。后续使用编译器时，要读取它实际采用的目标、权重和符号约定。期望能量、可行解比例、采样中最佳可行解的大小，分别回答不同的问题。
修改问题¶
- 加入
(a, c)，把路径变成三角形。重新运行，列出全部最优位串。 - 只保留
(a, b)一条边。最大独立集有几个节点？有多少个答案？ - 保持原路径图，手算时改用
λ = 0.5。最小化这个代价，还能将有效的最大独立集与所有无效候选区分开吗？
核对思路
三角形的最大独立集大小为 1，对应 001、010 和 100。只保留 (a, b) 时，可以选 c 再加任一端点，011 和 101 都有两个节点。若 λ = 0.5，则 E(111) = −2，与有效的 101 并列；仅凭这个代价无法保证选出可行解。即使目标值看起来很好，也要检查约束违反情况。
位串长度不匹配会抛出 ValueError。解码前核对变量顺序，不要假设图上的显示顺序或后续线路顺序与它相同。穷举需要检查 2^n 个候选，因此这里只用三个节点建立参考，不能据此判断算法的规模优势。
沿优化路线继续学习 QUBO、Ising 代价映射，以及 QAOA 和 VQE。学习新算法时，可以保留这张图和精确答案作为测试问题。