数理最適化（MILP）モデリング解説

『もふもふ羊の牧場囲い』の裏側：
最小点カット問題から「予算制約付き・最大重み連結領域問題」へ

対象読者：混合整数線形計画（MIP）の基礎（二値変数・線形不等式・目的関数）をご存じの方。
一見ほのぼのとした「柵でヒツジを囲うパズル」が、グラフ理論の最小点カット問題を土台にしつつ、どのように「穴ぼこ（負の重み）」や「孤立領域の排除（連結性）」を線形制約として定式化しているのかを解説します。

1. パズルのルールとグラフ表現

盤面は無向グリッドグラフ G = (V, E) として表せます。上下左右に隣接する通行可能なマスの組が辺集合 E を構成し、各頂点（マス）v ∈ V は以下の性質を持ちます。

盤面のタイル	集合・記号	柵の設置	重み（得点） `w_v`	数理モデル上の役割
🐑 ヒツジ	`S ⊂ V`	不可	`+2`	牧場の起点（湧き出し Source、常に `reach_s = 1`）
🐺 オオカミ	`W ⊂ V`	不可	`0`	侵入源（常に `reach_w = 0` を強制）
🌱 草地 / 🍓 野いちご	`V_fence ⊂ V`	可能	`+1` / `+5`	正の利得を持つ通常頂点（柵を置くと通行不可）
🕳️ 穴ぼこ	`V_fence ⊂ V`	可能	`-5`	負の重みを持つ頂点（牧場に入ると減点、真上に丸太の柵を打ち込んで塞げる）
🌉 石橋	`V_bridge ⊂ V`	不可	`+1`	通行できるがカット不能な頂点（カット容量 ∞）
💧 水辺 / 🪨 岩	`V_wall`	不可	—	最初から通行不能（グラフ `V` から除外して扱える天然の壁）

プレイヤーの目的は、最大 K 本までの柵を設置してすべてのオオカミ W からヒツジ S への経路を遮断し、その状態でヒツジ S から歩いて到達できる連結領域（まきば）の合計スコアを最大化することです。

2. もし「最小何本で守れるか」だけなら？（最小 s-t 点カット問題）

まずはスコア（いちごや穴ぼこ）を一旦忘れ、「最小何本の柵でオオカミ W とヒツジ S を分断できるか？」という部分問題だけを取り出してみます。

通常の最小カット問題はグラフの「辺（Edge）」を切りますが、このパズルでは「マス（頂点 Vertex）」の上に柵を置いて通行止めにするため、グラフ理論における最小 s-t 点カット問題（Minimum Vertex Cut）に対応します。

💡 メンガーの定理（Menger's Theorem）とパズルの難易度設計 「オオカミ W からヒツジ S へ至る頂点素な（互いに柵設置可能マスを共有しない）経路の最大本数は、両者を分断するのに必要な柵の最小本数に等しい」という定理が成り立ちます。
たとえば石橋 🌉（カット不能頂点）を介してオオカミの侵入路が3本に分岐していれば、オオカミの目の前を1本の柵で塞ぐことは原理的に不可能になります。

なぜ単なる「最小カット問題」では終わらないのか

このパズルが最小カット問題より一段深く、かつ面白い理由は次の2点にあります。

「最小本数」ではなく「上限 K 本の予算制約下での領域価値最大化」：
1本で塞げる狭い通路があっても、あえて2本の柵を使って手前の分岐を抑えた方が、その奥にある野いちご畑（🍓 +5）を牧場に取り込める場合があります。つまり「どの方向の戦線に柵予算 K を投資するか」というナップサック問題的なトレードオフが絡みます。
負の重み「🕳️ 穴ぼこ（-5 点）」の存在：
オオカミが全くいない袋小路であっても、そこに 🕳️ (-5) があれば、余った柵を1本使ってその袋小路を切り離す（あるいは 🕳️ の真上に丸太の柵を打ち込んで穴を塞ぐ）ことでスコアが +5 点改善します。逆に、🕳️ (-5) のさらに奥に 🍓×3 (+15) が眠っていれば、あえて穴ぼこを塞がず奥へ道をつなぐ方が得になります（Stage 7『穴ぼこの向こう側』）。

3. MILPによる定式化（1）：決定変数と「フラッド制約」

それでは、このパズルを混合整数線形計画（MILP）として定式化していきましょう。通行可能な各マス v ∈ V に対して、以下の2種類の二値変数を導入します。

二値決定変数（Binary Decision Variables） f_v ∈ {0, 1} (∀v ∈ V_fence) : マス v に木の柵を置くなら 1、置かないなら 0
r_v ∈ {0, 1} (∀v ∈ V) : マス v が「ヒツジの安全な牧場」に含まれるなら 1

まず、自明な境界条件と柵の本数上限（予算制約）を書きます。

基本制約（起点・侵入源・排他・予算） (1) r_s == 1            (∀s ∈ S)       : ヒツジのいるマスは必ず牧場内
(2) r_w == 0            (∀w ∈ W)       : オオカミのいるマスは絶対に牧場に入れてはならない
(3) r_v + f_v <= 1      (∀v ∈ V_fence) : 柵を置いたマス自体は牧場に含まれない
(4) Σ_{v ∈ V_fence} f_v <= K          : 置ける柵は最大 K 本まで

隣接マスへ牧場が広がる「フラッド制約（Flood / Cut Constraint）」

次に、「ヒツジの牧場 r_u = 1 の隣マス v に柵がなければ（f_v = 0）、その隣マス v も自動的に牧場と地続きになる（r_v = 1）」という物理法則を1本の線形不等式で表します。

フラッド制約（すべての隣接ペア (u, v) ∈ E について） r_u - r_v - f_v <= 0 （変形すると: r_u <= r_v + f_v）

このシンプルな不等式 r_u <= r_v + f_v は、1本で2つの重要な役割を同時に果たします。

役割A（オオカミの完全遮断）：
ヒツジ（r_s = 1）から始まる道の途中で一度も柵（f_v = 1）が置かれないままオオカミ（r_w = 0）に到達すると、1 = r_s <= … <= r_w = 0 となって制約違反（Infeasible）になります。つまり、すべての侵入経路のどこかに必ず f_v = 1 を置かなければ実行可能解になりません。
役割B（穴ぼこ 🕳️ -5 のつまみ食い防止）：
もしこの制約がなければ、ソルバーは「正の得点マス（🍓 +5）だけ r_v = 1 にし、牧場の真ん中にある穴ぼこ（🕳️ -5）は都合よく r_v = 0 にする」という抜け道を使えてしまいます。
しかしフラッド制約があるため、牧場（r_u = 1）に隣接する穴ぼこ v は、丸太の柵を打ち込んで塞ぐ（f_v = 1, r_v = 0）か、牧場に含めて -5 点を受け入れる（f_v = 0, r_v = 1）かの二択を厳密に迫られます。

4. MILPによる定式化（2）：「孤立ポケット問題」と単一品種フロー

ここで数理モデリング上の興味深い落とし穴が登場します。実は、前節のフラッド制約だけでは、まだ正しい定式化にはなりません。

❌ フラッド制約のみの場合の不整合

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

右上の 🍓 は木の柵と水辺💧でヒツジから完全に切り離されているのに、r_v = 1 にしてもフラッド制約 r_u <= r_v + f_v に違反しない。

⭕ 単一品種フロー保存則を入れた場合

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

ヒツジ🐑を水源とする水流（ネットワークフロー）が届くマスだけが r_v = 1 になれる。

なぜこの現象が起きるかというと、フラッド制約 r_u <= r_v + f_v は「ヒツジから到達できるマスはすべて 1 になる（下界）」は強制しますが、「柵や壁で囲まれた別の孤立ポケットの中身をまるごと r_v = 1 にする」ことは禁止していないからです。

解決策：単一品種ネットワークフロー（Single-Commodity Flow）

「r_v = 1 ならば、そのマス v はヒツジ S と実際にパスで繋がっていなければならない」という連結性を線形制約で表す定番の手法が、単一品種フロー保存則です。

隣接する各マスの組に有向連続変数 flow_{u→v} >= 0（マス u から隣マス v へ流す「水」の量）を用意し、以下の制約を加えます（M = |V| は通行可能マスの総数）：

連結性を保証する単一品種フロー制約 (5) 0 <= flow_{u→v} <= M * r_u   (∀(u, v) ∈ E) : 牧場内のマス u からしか水を出せない
(6) 0 <= flow_{u→v} <= M * r_v   (∀(u, v) ∈ E) : 牧場内のマス v へしか水を流せない
(7) Σ_{u} flow_{u→v} - Σ_{w} flow_{v→w} == r_v   (∀v ∈ V \ S) : ヒツジ以外の各牧場マス(r_v = 1)で水をちょうど 1 単位消費する

🔍 なぜこれで連結性が厳密に保証されるのか ヒツジ以外のマス v を r_v = 1 にするためには、式(7)より「どこかから 1 単位の水が流れ込んでくる」必要があります。しかし式(5)・(6)より、水は r = 1 のマス同士の間しか流れず、かつ水を新たに生み出せる（流入超過が許される）のは式(7)の対象外であるヒツジのマス S だけです。
したがって、ヒツジ S と柵なしで繋がっていない孤立ポケットには一滴も水が届かず、必ず r_v = 0 になります。

5. 目的関数と「1手ヒント（部分固定再求解）」

最後に目的関数です。「牧場の合計スコアを最大化する（第1優先）」とともに、同じスコアなら「使う柵の本数をできるだけ少なくする（第2優先）」という辞書式順序（Lexicographic Objective）を、重み係数 100 を使って1本の線形目的関数にまとめています。

目的関数（Objective Function） maximize Σ_{v ∈ V} (100 * w_v) * r_v - Σ_{v ∈ V_fence} 1 * f_v

また、ゲーム内の「💡 1手ヒント」ボタンは、あらかじめ用意した固定の答えを見ているのではなく、プレイヤーが現在盤面に置いている柵集合 F_cur を f_v == 1 (∀v ∈ F_cur) として固定した上でリアルタイムに再求解しています：

固定した状態での最適スコアが本来の理論値 Z* に届く場合：
「現在の柵配置は正解ルートに乗っている」と判定し、残りの最適柵 f_v* = 1 (v ∉ F_cur) のうち1マスを盤面上で黄色く点滅させます。
固定した状態では Infeasible（オオカミを防げない）または Z* 未満にしかならない場合：
「現在置いている柵の中に邪魔な柵がある」と判定し、外すべき柵のマスを赤く点滅させて教えてくれます。

実際のモデル構築コード（抜粋）

// 1. フラッド制約（u が牧場内で隣 v に柵がなければ、v も必ず牧場内）
if (vFence) {
  model.constraint(expr`${uReach} - ${vReach} - ${vFence} <= 0`);
} else {
  model.constraint(expr`${uReach} - ${vReach} <= 0`);
}

// 2. 単一品種フロー（u と v の両方が牧場内のときのみフローを流せる）
const flowUV = model.continuous(`flow_${r}_${c}_to_${nr}_${nc}`, { lb: 0, ub: maxFlowM });
model.constraint(expr`${flowUV} - ${maxFlowM} * ${uReach} <= 0`);
model.constraint(expr`${flowUV} - ${maxFlowM} * ${vReach} <= 0`);

// 3. 非ヒツジ頂点でのフロー保存則（流入 - 流出 == r_v）
model.constraint(expr`${sum(inList)} - ${sum(outList)} - ${rVar} == 0`);

Mathematical Optimization (MILP) Formulation Guide

Behind "Fluffy Sheep Pasture Enclosure":
From Minimum Vertex Cut to Budgeted Maximum-Weight Connected Subgraph

Target Audience: Readers familiar with the basics of Mixed-Integer Linear Programming (binary variables, linear inequalities, and objective functions).
This article explains how a cozy puzzle about enclosing sheep with wooden fences builds upon the classic Minimum s-t Vertex Cut problem while formulating negative-weight tiles (pitfalls) and strict region connectivity using linear constraints.

1. Puzzle Rules and Graph Representation

The board is modeled as an undirected grid graph G = (V, E), where orthogonally adjacent passable cells form the edge set E. Each vertex (cell) v ∈ V has the following properties:

Board Tile	Set / Symbol	Fence Allowed	Weight (Score) `w_v`	Role in the Mathematical Model
🐑 Sheep	`S ⊂ V`	No	`+2`	Pasture origin (Source; fixed to `reach_s = 1`)
🐺 Wolf	`W ⊂ V`	No	`0`	Hazard source (fixed to `reach_w = 0`)
🌱 Grass / 🍓 Strawberry	`V_fence ⊂ V`	Yes	`+1` / `+5`	Positive-reward vertices (impassable when a fence is placed)
🕳️ Pitfall	`V_fence ⊂ V`	Yes	`-5`	Negative-weight vertex (penalizes score if enclosed; can be plugged by driving a fence post into it)
🌉 Stone Bridge	`V_bridge ⊂ V`	No	`+1`	Passable but uncuttable vertex (infinite cut capacity)
💧 Water / 🪨 Rock	`V_wall`	No	—	Impassable natural walls (excluded from `V`)

The player's goal is to place at most K fences so that all paths between the wolves W and the sheep S are blocked, while maximizing the total score of the connected pasture reachable from the sheep S.

2. What If We Only Minimized Fence Count? (Minimum s-t Vertex Cut)

Suppose we temporarily ignore tile scores and ask only: "What is the minimum number of fences required to separate the wolves W from the sheep S?"

Whereas the standard minimum cut problem removes graph edges, here we block grid cells (vertices) with fences. This corresponds to the Minimum s-t Vertex Cut problem in graph theory.

💡 Menger's Theorem and Level Design By Menger's Theorem, the maximum number of vertex-disjoint paths (sharing no fenceable cells) between the wolves W and the sheep S equals the minimum number of fences needed to separate them.
For example, if stone bridges 🌉 (uncuttable vertices) split a wolf's approach into three independent corridors, caging the wolf with a single fence right in front of its spawn is mathematically impossible.

Why This Puzzle Goes Beyond a Pure Minimum Cut

Two structural features make this puzzle richer than a textbook minimum cut problem:

Maximizing Enclosed Value Under a Fence Budget K:
Even when a narrow choke point can be sealed with 1 fence, spending 2 fences further forward to hold a branch junction may capture a rich strawberry patch (🍓 +5) beyond it. Deciding where to invest the fence budget K introduces a knapsack-like trade-off across multiple fronts.
Negative Weights from Pitfalls (🕳️ -5):
Even in a dead-end corridor with no wolves, if a pitfall 🕳️ (-5) lies connected to the pasture, spending a fence to seal off that corridor—or driving a fence post directly into the pit to plug it—improves the score by +5. Conversely, if three strawberries (+15) lie behind a pitfall (-5), deliberately leaving the pitfall open inside the pasture to keep the path open yields a net gain of +10 (as seen in Stage 7).

3. MILP Formulation (Part 1): Decision Variables and the Flood Constraint

To formulate the puzzle as a Mixed-Integer Linear Program (MILP), we introduce two sets of binary decision variables over the passable cells v ∈ V:

Binary Decision Variables f_v ∈ {0, 1} (∀v ∈ V_fence) : 1 if a wooden fence is placed on cell v, 0 otherwise
r_v ∈ {0, 1} (∀v ∈ V) : 1 if cell v is part of the sheep's safe pasture, 0 otherwise

First, we state the boundary conditions, mutual exclusion, and the fence budget constraint:

Base Constraints (Sources, Hazards, Exclusion, and Budget) (1) r_s == 1            (∀s ∈ S)       : Every sheep cell is always inside the pasture
(2) r_w == 0            (∀w ∈ W)       : No wolf cell may ever be inside the pasture
(3) r_v + f_v <= 1      (∀v ∈ V_fence) : A fenced cell cannot itself be part of the pasture
(4) Σ_{v ∈ V_fence} f_v <= K          : At most K fences can be placed

The Flood / Cut Constraint Across Adjacent Cells

Next, we express the propagation rule: "If cell u is inside the pasture (r_u = 1) and its neighbor v has no fence (f_v = 0), then v must also be inside the pasture (r_v = 1)."

Flood Constraint (for every ordered adjacent pair (u, v) ∈ E) r_u - r_v - f_v <= 0 (equivalently: r_u <= r_v + f_v)

This single linear inequality r_u <= r_v + f_v simultaneously enforces two essential properties:

Role A (Complete Wolf Separation):
If any open path from a sheep (r_s = 1) reaches a wolf (r_w = 0) without encountering a fence (f_v = 1), chaining the inequality along the path yields 1 = r_s <= … <= r_w = 0, which is infeasible. Thus every wolf-to-sheep path must contain at least one fence.
Role B (Preventing Cherry-Picking Around Pitfalls):
Without this constraint, an optimizer could set r_v = 1 on positive tiles (🍓 +5) while arbitrarily setting r_v = 0 on an unfenced pitfall (🕳️ -5) right next to the sheep. Because of the flood constraint, any pitfall adjacent to the pasture forces a strict choice: spend a fence post to plug/block it (f_v = 1, r_v = 0) or include it in the pasture and accept the -5 penalty (f_v = 0, r_v = 1).

4. MILP Formulation (Part 2): Disconnected Pockets and Single-Commodity Flow

Here we encounter a classic mathematical modeling pitfall: the flood constraint alone is not sufficient to define the pasture accurately.

❌ Loophole Under Flood Constraints Alone

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

The top-right 🍓 is completely walled off from the sheep by a fence and water 💧, yet setting r_v = 1 there does not violate r_u <= r_v + f_v.

⭕ With Single-Commodity Flow Conservation

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

Only cells that can receive network flow originating from the sheep 🐑 can set r_v = 1.

Why does this happen? Because r_u <= r_v + f_v forces every cell reachable from the sheep to have r_v = 1 (a lower bound), but it does not forbid setting r_v = 1 inside an isolated pocket walled off by fences and water.

Solution: Single-Commodity Network Flow

To guarantee that r_v = 1 holds only if cell v is genuinely connected to at least one sheep in S, we add Single-Commodity Flow conservation constraints.

For each directed edge (u, v) ∈ E, we define a non-negative continuous variable flow_{u→v} >= 0 representing the amount of flow sent from u to v (where M = |V| is the total number of passable cells):

Single-Commodity Flow Constraints for Connectivity (5) 0 <= flow_{u→v} <= M * r_u   (∀(u, v) ∈ E) : Flow can only leave a cell u that is in the pasture
(6) 0 <= flow_{u→v} <= M * r_v   (∀(u, v) ∈ E) : Flow can only enter a cell v that is in the pasture
(7) Σ_{u} flow_{u→v} - Σ_{w} flow_{v→w} == r_v   (∀v ∈ V \ S) : Each non-sheep pasture cell (r_v = 1) consumes 1 unit of flow

🔍 Why This Strictly Guarantees Connectivity By equation (7), any non-sheep cell with r_v = 1 must consume 1 net unit of flow. By (5) and (6), flow can only travel through cells where r = 1, and the only nodes exempt from flow conservation (able to act as flow sources) are the sheep cells S. Consequently, any pocket disconnected from the sheep receives zero flow and is forced to r_v = 0.

5. Objective Function and 1-Move Hint Diagnosis (Partial Fixing)

Finally, we combine "maximizing total pasture score (primary objective)" and "using as few fences as possible among tied scores (secondary tie-breaker)" into a single linear objective using a lexicographic weight of 100:

Objective Function maximize Σ_{v ∈ V} (100 * w_v) * r_v - Σ_{v ∈ V_fence} 1 * f_v

The in-game "💡 1-Move Hint" button does not merely look up a static answer key. Instead, it fixes the player's currently placed fences F_cur (f_v == 1 for all v ∈ F_cur) and re-solves the MILP in real time:

If the restricted problem is still Feasible and achieves the optimal target score Z*:
The player's current fences are on a valid optimal path, so the game highlights one remaining unplaced fence f_v* = 1 (v ∉ F_cur) in yellow.
If the restricted problem is Infeasible or its optimal objective falls short of Z*:
At least one placed fence is blocking the optimal enclosure, so the game identifies that fence and highlights it in red for removal.

Model Construction Excerpt

// 1. Flood constraint (if u is in the pasture and v has no fence, v must also be in the pasture)
if (vFence) {
  model.constraint(expr`${uReach} - ${vReach} - ${vFence} <= 0`);
} else {
  model.constraint(expr`${uReach} - ${vReach} <= 0`);
}

// 2. Single-commodity flow (flow is active only when both u and v are in the pasture)
const flowUV = model.continuous(`flow_${r}_${c}_to_${nr}_${nc}`, { lb: 0, ub: maxFlowM });
model.constraint(expr`${flowUV} - ${maxFlowM} * ${uReach} <= 0`);
model.constraint(expr`${flowUV} - ${maxFlowM} * ${vReach} <= 0`);

// 3. Flow conservation at every non-sheep cell (inflow - outflow == r_v)
model.constraint(expr`${sum(inList)} - ${sum(outList)} - ${rVar} == 0`);

数学规划（MILP）建模解说

《毛茸茸绵羊的牧场围栏》背后的数学模型：
从最小点割问题到“带预算约束的最大权连通子图问题”

适合读者：了解混合整数线性规划（MIP）基础（0-1变量、线性不等式与目标函数）的读者。
本文将解说这款看似轻松治愈的“用木栅栏围住小羊”的益智游戏，是如何以图论中的最小点割问题为基础，将“坑洞（负权重）”与“排除孤立飞地（连通性约束）”转化为严格的线性约束的。

1. 游戏规则与网格图表示

游戏棋盘可以表示为无向网格图 G = (V, E)。上下左右相邻的可通行格构成边集 E，每个顶点（格子）v ∈ V 具有以下属性：

棋盘地形	集合与符号	可否放置栅栏	权重（得分） `w_v`	数学模型中的角色
🐑 绵羊	`S ⊂ V`	不可	`+2`	牧场起点（源点 Source，固定为 `reach_s = 1`）
🐺 野狼	`W ⊂ V`	不可	`0`	入侵源（强制要求 `reach_w = 0`）
🌱 草地 / 🍓 野草莓	`V_fence ⊂ V`	可以	`+1` / `+5`	正收益普通顶点（放置栅栏后不可通行）
🕳️ 坑洞	`V_fence ⊂ V`	可以	`-5`	负权重顶点（纳入牧场会扣分，可直接打入木桩栅栏将其填平）
🌉 石桥	`V_bridge ⊂ V`	不可	`+1`	可通行但不可割的顶点（割容量 ∞）
💧 水域 / 🪨 岩石	`V_wall`	不可	—	天然障碍物（直接从图 `V` 中排除）

玩家的目标是放置最多 K 根栅栏，阻断所有野狼 W 通往绵羊 S 的路径，并在该条件下最大化从绵羊 S 出发可步行的连通区域（安全牧场）的总得分。

2. 如果只问“最少几根栅栏能守住”？（最小 s-t 点割问题）

我们先暂时忽略草莓与坑洞的分数，只考虑子问题：“最少需要几根栅栏才能将野狼 W 与绵羊 S 完全隔开？”

标准的最小割问题切断的是图中的“边（Edge）”，而本作是在“格子（顶点 Vertex）”上放置栅栏阻断通行，因此在图论中对应最小 s-t 点割问题（Minimum Vertex Cut）。

💡 门格尔定理（Menger's Theorem）与关卡设计 根据门格尔定理，“从野狼 W 到绵羊 S 之间顶点不相交（不共用任何可放栅栏格）的最大路径条数，严格等于将两者隔开所需的最少栅栏数”。
例如，当野狼出生点旁通过石桥 🌉（不可放置栅栏的顶点）分叉出多条进攻路线时，玩家就无法用1根栅栏直接在野狼面前将其堵死。

为什么它不只是一个简单的“最小割问题”

本作比单纯的最小割问题更有深度，主要源于以下两个机制：

不是“最小化栅栏数”，而是“在栅栏预算上限 K 下最大化区域价值”：
即使某条狭窄通道只需1根栅栏就能封死，有时主动消耗2根栅栏把防线推到前方分叉口，反而能将后方的野草莓田（🍓 +5）纳入牧场。也就是说，玩家需要在不同防线之间权衡如何分配有限的栅栏预算 K。
负权重地形“🕳️ 坑洞（-5 分）”的取舍：
即使某个死胡同里根本没有野狼，只要里面有 🕳️ (-5)，用1根富余的栅栏把死胡同隔开（或者直接在 🕳️ 上打入木桩栅栏将其填平）就能让总分提高 +5 分。反过来，如果 🕳️ (-5) 的更深处藏着 🍓×3 (+15)，那么故意保留坑洞不封死、跨过它去拿深处的草莓反而能净赚 +10 分（如第7关）。

3. MILP 建模（一）：决策变量与“漫延（Flood）约束”

下面我们将该问题建立为混合整数线性规划（MILP）。对每个可通行格 v ∈ V，引入以下两类 0-1 决策变量：

0-1 决策变量（Binary Decision Variables） f_v ∈ {0, 1} (∀v ∈ V_fence) : 在格子 v 放置栅栏则为 1，否则为 0
r_v ∈ {0, 1} (∀v ∈ V) : 格子 v 属于“绵羊的安全牧场”则为 1，否则为 0

首先写出边界条件、互斥条件与栅栏预算上限：

基础约束（起点、入侵源、互斥与预算） (1) r_s == 1            (∀s ∈ S)       : 绵羊所在格必定属于牧场
(2) r_w == 0            (∀w ∈ W)       : 野狼所在格绝对不能属于牧场
(3) r_v + f_v <= 1      (∀v ∈ V_fence) : 放置了栅栏的格子本身不属于牧场
(4) Σ_{v ∈ V_fence} f_v <= K          : 最多只能放置 K 根栅栏

向相邻格子扩展的“漫延约束（Flood / Cut Constraint）”

接着，用一条线性不等式刻画连通传播规律：“如果格子 u 在牧场内（r_u = 1），且相邻格子 v 没有放栅栏（f_v = 0），那么相邻格子 v 也必须自动属于牧场（r_v = 1）”。

漫延约束（对所有相邻有序对 (u, v) ∈ E） r_u - r_v - f_v <= 0 （等价变形为: r_u <= r_v + f_v）

这条简洁的不等式 r_u <= r_v + f_v 同时承担了两个重要作用：

作用 A（彻底阻断野狼）：
如果从绵羊（r_s = 1）出发的某条路径在到达野狼（r_w = 0）之前没有任何一格放置栅栏（f_v = 1），沿路径串联不等式就会得到 1 = r_s <= … <= r_w = 0，从而导致模型无解（Infeasible）。因此所有入侵路径上都必须至少放置1根栅栏。
作用 B（防止跳过坑洞 🕳️ -5 只捡正分格）：
如果没有这条约束，求解器就会只把草莓（🍓 +5）设为 r_v = 1，而把牧场中间没放栅栏的坑洞（🕳️ -5）偷偷设为 r_v = 0。
有了漫延约束后，任何与牧场（r_u = 1）相邻的坑洞 v 都必须二选一：要么花1根木桩栅栏填平它（f_v = 1, r_v = 0），要么将它纳入牧场并接受 -5 分（f_v = 0, r_v = 1）。

4. MILP 建模（二）：“孤立飞地问题”与单商品网络流

这里会出现一个经典的数学建模陷阱：仅靠上一节的漫延约束，还不足以正确定义连通牧场。

❌ 仅使用漫延约束时的漏洞

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

右上角的 🍓 已被栅栏和水域💧完全隔绝在绵羊不可达之处，但将其设为 r_v = 1 并不违反 r_u <= r_v + f_v。

⭕ 加入单商品流守恒约束后

🐺

🌱

💧

🍓

💧

🌱

💧

🌱

🐑

🌱

🍓

只有从绵羊🐑出发的“水流（网络流）”能够送达的格子，才能设为 r_v = 1。

原因在于：漫延约束 r_u <= r_v + f_v 只规定了“绵羊能走到的格子必须为 1（下界）”，却没有禁止求解器把被栅栏和墙壁围起来的另一块孤立口袋整体设为 r_v = 1 来白拿里面的草莓分数。

解决方案：单商品网络流（Single-Commodity Flow）

为了用线性约束严格表达“若 r_v = 1，则格子 v 必须与某只绵羊 S 存在真实连通路径”，标准做法是引入单商品流守恒约束。

对每对相邻有向边 (u, v) ∈ E 引入非负连续变量 flow_{u→v} >= 0（表示从格子 u 流向相邻格子 v 的“水量”，其中 M = |V| 为可通行格总数）：

保证连通性的单商品流约束 (5) 0 <= flow_{u→v} <= M * r_u   (∀(u, v) ∈ E) : 只有牧场内的格子 u 才能流出水
(6) 0 <= flow_{u→v} <= M * r_v   (∀(u, v) ∈ E) : 只有牧场内的格子 v 才能流入水
(7) Σ_{u} flow_{u→v} - Σ_{w} flow_{v→w} == r_v   (∀v ∈ V \ S) : 除绵羊外的每个牧场格(r_v = 1)恰好消耗 1 单位水

🔍 为什么这能严格保证连通性 由式(7)可知，任何非绵羊格若想设为 r_v = 1，就必须有 1 单位的净水流注入该格。而由式(5)・(6)可知，水流只能在 r = 1 的格子之间传递，且全图中唯一不受式(7)约束、能够凭空产生水流的源点只有绵羊所在格 S。
因此，任何与绵羊被栅栏隔开的孤立区域都无法获得水流，其 r_v 必然被强制为 0。

5. 目标函数与“一步提示（部分固定重求解）”

最后是目标函数。我们将“最大化牧场总得分（第一优先级）”与“同分时尽量少用栅栏（第二优先级）”通过字典序权重系数 100 合并为一条线性目标函数：

目标函数（Objective Function） maximize Σ_{v ∈ V} (100 * w_v) * r_v - Σ_{v ∈ V_fence} 1 * f_v

此外，游戏中的“💡 一步提示”按钮并不是简单读取预设答案，而是将玩家当前已在棋盘上放置的栅栏集合 F_cur 作为固定约束 f_v == 1 (∀v ∈ F_cur) 加入模型并实时重求解：

若固定当前栅栏后的最优得分仍能达到理论最优值 Z*：
说明玩家当前的摆法走在正确的最优路线上，系统会从剩余未放的最优栅栏 f_v* = 1 (v ∉ F_cur) 中挑出1格在棋盘上以黄色高亮提示。
若固定当前栅栏后无解（无法挡住野狼）或最优得分低于 Z*：
说明玩家已放置的栅栏中存在阻碍最优解的错误栅栏，系统会找出该栅栏并以红色高亮提示玩家将其移除。

模型构建代码摘录

// 1. 漫延约束（若 u 在牧场内且相邻 v 未放栅栏，则 v 也必定在牧场内）
if (vFence) {
  model.constraint(expr`${uReach} - ${vReach} - ${vFence} <= 0`);
} else {
  model.constraint(expr`${uReach} - ${vReach} <= 0`);
}

// 2. 单商品流（仅当 u 与 v 均在牧场内时才允许流量通过）
const flowUV = model.continuous(`flow_${r}_${c}_to_${nr}_${nc}`, { lb: 0, ub: maxFlowM });
model.constraint(expr`${flowUV} - ${maxFlowM} * ${uReach} <= 0`);
model.constraint(expr`${flowUV} - ${maxFlowM} * ${vReach} <= 0`);

// 3. 非绵羊顶点的流量守恒（流入 - 流出 == r_v）
model.constraint(expr`${sum(inList)} - ${sum(outList)} - ${rVar} == 0`);