空间网络与路网

把距离惩罚 α 拖到 0，就是一张普通的随机图。平均边长 282.55，而任意两点的平均距离是 283.95——几乎一样，说明连边完全不看距离。聚集系数 0.0295，和随机图的 0.0449 同一量级；平均最短路 3.426，和随机图的理论值 log n / log k = 3.246 也吻合。现在把 α 拖到 2：所有三个数都变了。平均边长从 282.55 掉到 45.99，只有随机连线的六分之一；聚集系数从 0.0295 跳到 0.5731，是同等随机图的 12.8 倍；而平均最短路从 3.426 涨到 4.949。这三件事是同一个原因：边只连近处，于是"我的两个邻居"也彼此靠近、因此也很可能相连（聚集高），而想去远处就只能一步一步挪（路径长）。这就是空间网络的基本张力：距离约束天然给你高聚集，同时天然给你长路径。小世界要的是"高聚集 + 短路径"，所以在纯空间网络里，小世界不会自己出现——必须额外插入少量不管距离的长边。现实中这些长边就是高铁、航线、跨洋光缆、以及社交网络里那些"在外地的老同学"。再看第四行：度数 4.00 ± 2.20。标准差只有均值的一半左右，这是一个很窄的度分布，不可能有无标度的重尾。原因也很直接：一个节点周围的地方是有限的，它塞不下一万个近邻。这解释了一个长期被误用的观察——很多人报告过"公路网/电网是无标度的"，但在受空间约束的网络里，度数有物理上限，真实的公路网度分布其实非常窄（大部分路口连 3 到 4 条路）。被当成无标度的，往往是航空网那种"名义上在地图上、实际上不受距离约束"的网络。（把 α 从 2 继续拖到 4，三个数几乎不再变（45.16 / 0.5749 / 4.667）。一旦"只连最近的"这条规则占了主导，再加大惩罚也没有更近的边可连了。这提醒我们：模型参数和观测量之间往往不是单调放大的关系，存在饱和区。）

Dijkstra 的做法是"以起点为圆心，一圈一圈往外扩"——它不知道终点在哪，所以每个方向都要扩。图上蓝色的点就是被访问过的节点：把启发式权重拖到 0（即 Dijkstra），110 个点里访问了 92 个，几乎整张图都扫了一遍。A* 只加了一句话：排队时不按"已经走了多远"排，而按"已经走了多远 + 直线距离还剩多远"排。这个"还剩多远"就叫启发式。把权重拖回 1（标准 A*）：访问数从 92 掉到 40，少了 56.5%，而路径长度 701.0，和最优的 701.0 一模一样，一点都没变差。图上蓝点明显收缩成了起点到终点之间的一条走廊。为什么能保证不变差？因为直线距离永远不会高估真实距离——这叫"可采纳"（admissible）。只要启发式可采纳，A* 找到的一定是最优路径；而启发式越接近真实剩余距离，搜索就越集中、访问的点越少。现在把权重拖到 2，做一件教科书上叫"加权 A*"的事。访问数从 92 掉到 16，少了 82.6%；而路径长度变成 710.7，比最优长了 1.38%。这就是那个交换：用 1.4% 的路径质量，换到了 6 倍的速度。加权 A* 有一条漂亮的保证：权重取 w 时，找到的路径不会超过最优的 w 倍。这里 w = 2 保证不超过 2 倍，而实际只超了 1.4%——理论上界往往比实际保守得多，这也是加权 A* 在游戏和机器人里被大量使用的原因。最后把路网的距离惩罚 α 拖到 0 再看。这时路网变成了随机图，"直线距离"这个启发式基本失效——因为图上的边可以任意远，几何上很远的两点可能一步就到。读数显示访问数 10 / 66，A* 仍然快，但这靠的是随机图本身直径小，而不是启发式在起作用。实践中的教训是：A* 的加速全部来自启发式和真实距离有多接近；在没有几何结构可利用的图上（社交网络、状态空间），找到一个好的启发式本身就是问题的一大半。

同一批需求点，同样建 3 个设施，只把目标函数从"平均距离最小"换成"最远距离最小"，选出来的点位就换掉了三分之二。图上橙点是当前目标选的，蓝圈是另一个目标会选的——默认参数下 3 个点位里只有 1 个重合。p-中位（平均距离最小）：平均 105.76，最远 315.13。p-中心（最远距离最小）：平均 116.61，最远 238.22。换一个目标，最远距离降了 24.4%，代价是平均距离升了 10.3%。这两个目标背后是两种完全不同的价值判断。p-中位追求总效率：它会把设施堆在人多的地方，因为这样能让最多的人少走路。商业选址（便利店、外卖前置仓、基站）几乎都用它。p-中心追求最坏情况的公平：它会为了那几个住得最偏的人，把一个设施从人堆里挪出去。消防站、急救中心、应急避难所、疫苗接种点几乎都用它——因为"平均 8 分钟到达"对那个等了 40 分钟的人毫无意义。把"需求点有多聚集"拖到 100%：两个目标选出的点位完全一样。当所有人都住在三个集群里，怎么选都是那三个集群。而拖到 0（均匀分布）时，3 个点位一个都不重合。这给出一条很实际的判断：需求分布越均匀，目标函数的选择越要紧；需求越集中，选址问题本身越不敏感。最后一行读数是最远距离与平均距离的比值。p-中位下是 2.98，p-中心下是 2.04。这个比值可以直接当成"服务的不平等程度"来读：同一套设施，有人 20 分钟到，有人 60 分钟到。现实中的公共服务规划几乎总是在这两个目标之间取折中，常见做法是加一个硬约束（"任何人不得超过 30 分钟"）再在满足约束的方案里最小化平均距离——把公平写成约束，把效率写成目标。（顺带一提：p-中位和 p-中心都是 NP-难的，这里用的是贪心加交换的局部搜索。p-中心的目标函数特别"平"——换掉一个点位常常完全不改变最大值，局部搜索会卡在高原上，所以代码里给它加了一个极小的平均距离作为次级目标来破平。这类"平坦目标函数"的处理方式，在最坏情况优化里是一个通用技巧。）

45 个城镇，预算只够修 70 条路。修哪 70 条？四种策略，四个完全不同的答案。"一律先修最短的"：造价 3613，最便宜。但全局效率只有 0.1261，毁掉 15% 的路之后最大连通片只剩 36%。原因在图上一眼能看见：最短的边全都在城镇密集的地方，钱都花在了几个小团内部，团与团之间根本没连上。这是贪心算法最典型的失败方式——每一步都最优，全局却散成了几块。"先保证全连通，再补最短的"：造价 3751，只贵了 3.8%，而效率从 0.1261 涨到 0.2418，接近翻倍。做法是先造一棵最小生成树（用最省的钱把所有点串起来），再把剩下的预算花在最短的边上。第三行读数——每单位造价买到的效率——这个策略是 0.645，最短边优先只有 0.349，差了将近一倍。"随机修"：造价 20279，是前者的 5.4 倍，效率 0.3401。效率确实更高（随机边里有很多长途连接，正是空间网络缺的那种"捷径"），鲁棒性也最好（毁掉 15% 后还剩 89%）。但性价比只有 0.168，是最小生成树方案的四分之一。"先修最长的"是最差的：造价 38989，效率 0.1417，性价比 0.036。这一页想让人看到的是"多目标"这件事的真实面貌。造价、效率、鲁棒性三个指标，没有任何一种策略在三项上全赢。最短边优先赢造价，随机赢鲁棒性和绝对效率，最小生成树赢性价比。真实的路网规划正是在这个三角里做选择，而且往往由预算之外的东西决定：战备要鲁棒性，扶贫要连通性，商业要性价比。（把预算从 70 拖到 200：效率涨到 0.4584，毁掉 15% 后仍然 100% 连通，但性价比从 0.645 掉到 0.253。这是一条很普遍的收益递减曲线——前 20% 的钱买到大部分的连通性，后面的钱买的是冗余。而冗余不是浪费：它正是鲁棒性本身。）