上一篇，我們看了外送平台怎麼決定誰來送一張訂單。

乍看之下，好像只是 找距離最近的外送員，但真正的問題裡，可能同時存在：

• 路線距離
• 等待時間
• 外送員工作量
• 手上的其他訂單
• 餐點完成時間
• 配送時限

所以最後要衡量的，其實是在很多條件之下：

找到一個合理的分配

而且當條件越來越多時，我們會開始遇到另一種問題。

有時候我們甚至還沒有資格討論：哪一個答案最好？
因為更前面的問題是：

到底有沒有任何一個答案，可以同時滿足所有條件？

替實驗課安排時段與實驗室，就是非常典型的例子。

---

排實驗課不就是把課塞進空白時間嗎？

假設一間學校下學期要安排四個實驗課分組：

• 普通化學實驗 A
• 普通化學實驗 B
• 普通物理實驗 A
• 普通物理實驗 B

學校有四個時段可安排：

• 星期一上午
• 星期一下午
• 星期二上午
• 星期二下午

如果每個分組剛好排一個時段，看起來似乎很簡單：

• 普通化學實驗 A → 星期一上午
• 普通化學實驗 B → 星期一下午
• 普通物理實驗 A → 星期二上午
• 普通物理實驗 B → 星期二下午

但現實中的實驗課排程，不可能只有這些資訊。

例如突然多了一個條件：

普通化學實驗 A 與 B 都要使用同一間化學教學實驗室，所以不能排在同一時間

這還好，那再多一個：

普通化學實驗 A 與普通物理實驗 A 有許多共同修課學生，因此兩組不能撞堂

接著又有：

普通物理實驗 A 與 B 都必須使用物理教學實驗室

而那間實驗室只有星期一下午與星期二下午可以借用。

然後還可能有：

普通化學實驗 B 有 32 位學生，所以不能使用安全容量只有 24 人的實驗室

以及：

負責其中一組實驗課的教師，星期二上午沒有辦法授課

甚至：

每次實驗課都需要一段完整的連續時段，不能拆成數個零碎時段

這時候，安排實驗課就已經變成：

在很多彼此牽制的條件下，替每個實驗課分組找到合法的時段與實驗室

這類問題通常可以用一個很重要的模型來理解：

限制滿足問題（Constraint Satisfaction Problem，CSP）

---

先不要問最好，先問能不能成立

我們前面幾篇談過很多「選擇」。

例如 Knapsack 問的是：

容量有限時，怎麼取得最大的價值？

Greedy 問的是：

每一步怎麼做選擇？

Scheduling 可能會問：

怎麼安排工作，讓等待時間更少？

Matching 也可能考慮：

哪一種分配的成本比較低？

這些問題通常都有一個很明確的最佳化目標（objective）。

也就是：

我們想讓什麼變大，或讓什麼變小？

例如：

• 最大化價值
• 最小化距離
• 最小化等待時間
• 減少使用的貨車數量

但限制滿足問題的第一個問題不太一樣。

它問的是：

能不能找到一組安排，使所有條件都成立？

例如一張實驗課表，我們一開始可能完全不在意：

• 學生是不是喜歡這個時間？
• 教師是不是比較偏好早上的課？
• 實驗室利用率是不是最高？

我們只想先知道：

• 有沒有一張實驗課表
• 不會重複借用同一間實驗室
• 不會讓共同修課的學生撞堂
• 符合實驗室的安全容量
• 教師與助教可以配合
• 實驗室開放時段也符合

如果連這件事都做不到，那麼：

哪一張實驗課表最好？

根本還不是現在該問的問題。

---

Variable：我們到底要決定什麼？

要描述一個限制滿足問題，可以先從第一個元素開始當成：

變數 Variable

變數的意思是：

問題中，需要被決定的東西

例如我們現在有四個實驗課分組。

為了先把模型看清楚，我們假設每個分組使用的實驗室已經確定，目前只決定上課時段：

Chemistry_A
Chemistry_B
Physics_A
Physics_B

那麼可以把每個分組看成一個變數：

Chemistry_A = ?
Chemistry_B = ?
Physics_A = ?
Physics_B = ?

問號代表：

我們還不知道它最後會被安排到哪個時段？

所以實驗課排程的想法就是：

替每一個 variable 指定一個 value

例如：

Chemistry_A = Mon_AM
Chemistry_B = Mon_PM
Physics_A = Tue_AM
Physics_B = Tue_PM

這是一組完整的分配。
如果同一門課可以借用不同實驗室，這個 value 也可以擴充成「時段與實驗室」的組合。

但是：

不是每一種分配方法都可以接受

因為還有很多限制。

---

Domain：每一個變數可以有哪些選擇？

變數不會什麼值都能放。
例如實驗課可以選擇的時段可能只有：

Mon_AM
Mon_PM
Tue_AM
Tue_PM

這一組「可能的值」，就是：

領域 Domain

因此可以想成：

Chemistry_A
Domain:
Mon_AM
Mon_PM
Tue_AM
Tue_PM

如果負責 Chemistry_A 的教師星期二不能授課，它的領域就可能縮小成：

Chemistry_A
Domain:
Mon_AM
Mon_PM

而 Physics_B 必須使用物理教學實驗室，那間實驗室只有下午可以借用，因此：

Physics_B
Domain:
Mon_PM
Tue_PM

你可以把領域理解成：

這個變數目前有哪些候選答案？

這個概念很重要。
因為很多現實問題並不是任何人、任何時間、任何地點，都可以自由組合，而是每一個選項本身就有不同的可行範圍。

---

Constraint：不是所有組合都合法

現在我們有：

• 變數 Variable
• 領域 Domain

接下來真正讓問題變困難的，就是：

限制條件 Constraint

限制條件就是：

這些選擇必須遵守的限制

例如同一間實驗室不能在同一時間借給兩個分組。

假設：

Chemistry_A
Chemistry_B

都需要使用化學教學實驗室。

那麼：

Chemistry_A != Chemistry_B

這裡的 != 不是在比較兩門課本身，而是表示：

它們不能被安排在同一個時段

如果很多學生同時修：

Chemistry_A
Physics_A

那也可能有：

Chemistry_A != Physics_A

再例如 Physics_B 必須使用物理教學實驗室：

Physics_B.room = Physics_Lab

而 Physics_Lab 只能在 Mon_PM 和 Tue_PM 使用。
另一組有 32 位學生的實驗課則可能要求：

room.safety_capacity >= 32

這些全部都是限制條件。

---

真正麻煩的是限制條件會互相影響

單獨看每一個條件，好像都沒有很困難。
例如：

• 同一間實驗室不能重複借用
• 共同修課的學生不能撞堂
• 實驗室安全容量必須足夠
• 特定實驗室只能在開放時段借用

你再考量的時候會發現：

它們是不能分開處理的

假設 Physics_B 只能在 Mon_PM 和 Tue_PM，而負責教師星期二下午不能授課。
那 Physics_B 實際上只剩 Mon_PM。
如果 Physics_A 又因為其他限制，只能排 Mon_PM。
而兩組都需要使用同一間物理教學實驗室。

現在就出現問題了：

Physics_B 只能 Mon_PM
Physics_A 只能 Mon_PM

但：

Physics_B != Physics_A

你會發現：

每一個條件單獨看都合理，但放在一起之後，可能根本不存在答案

---

有些問題真的沒有答案

我們很容易有一個直覺：

只要演算法夠厲害，最後一定能算出答案

但其實不是，有些問題根本不存在合法安排。

例如三個實驗課分組：A、B、C。

全部都必須使用同一間教學實驗室。

但現在只有兩個時段：

• Mon_AM
• Mon_PM

而且三組都必須安排在星期一。

那麼：

A != B
A != C
B != C

可是可以使用的值只有：

Mon_AM
Mon_PM

不管怎麼排，都至少會有兩組同時占用那間實驗室。

這個問題不是：

我們還沒找到答案

而是：

根本不存在滿足所有限制條件的答案

這也是建模時非常重要的一件事。
有些需求同時放在一起，本身就互相矛盾。
這時候一直要求演算法再聰明一點，並不能解決問題。

真正應該做的可能是：

• 增加時段
• 開放另一間合適的實驗室
• 調整教師或助教安排
• 放寬限制
• 調整實驗課分組

也就是：

改變問題本身

---

Valid Solution：所有限制條件都成立

如果我們找到一組安排：

Chemistry_A  → Mon_AM @ Chemistry_Lab
Chemistry_B  → Tue_AM @ Chemistry_Lab
Physics_A    → Mon_PM @ Physics_Lab
Physics_B    → Tue_PM @ Physics_Lab

接著檢查：

實驗室是否重複借用？
No

學生是否有必要避免的衝堂？
No

實驗室安全容量是否足夠？
Yes

指定實驗室是否開放？
Yes

教師與助教時間是否允許？
Yes

如果所有限制條件都成立，那這組安排就是一個：

可行解 Valid Solution

注意這裡我們沒有說：

這是最好的實驗課表

我們只說：

這張實驗課表可以運作

這兩件事情差很多。

---

可行，不代表理想

假設我們現在找到兩個可行解。
為了比較不同安排的便利性，這裡把候選時段擴大到星期一至星期五，並假設接下來使用的時段都符合實驗室與人員的必要限制。

第一張：

需要協調的課程分散在不同日期
學生與教師必須多次往返校園

例如：

Mon AM  Chemistry_A
Tue PM  Chemistry_B
Thu AM  Physics_A
Fri PM  Physics_B

所有限制條件都符合。
沒有撞堂，實驗室也都有，教師與助教也有空。

所以：

它是一個可行解

但學生可能會說：

這張實驗課表也太爛了吧

另一張實驗課表則是：

Mon AM  Chemistry_A
Mon PM  Chemistry_B
Tue AM  Physics_A
Tue PM  Physics_B

同樣沒有違反任何限制條件。
但是需要協調的人員只需要集中兩天到校。

那大家可能會覺得：

第二張比較好

這時候問題才開始從 限制滿足問題，往最佳化的方向前進。

因為我們現在不只問：

有沒有合法答案？

而開始問：

合法答案裡，哪一個比較好？

---

限制條件和偏好（Preference）不完全一樣

假設負責教師說：

我不能星期五下午上課

這通常是一個：限制條件。
因為違反它，答案就不能接受。

但如果負責教師說：

如果可以的話，我比較喜歡星期二上午

這比較像：偏好 Preference。
星期二上午當然很好，但如果排不到，也不代表整張實驗課表就無效。

所以現實系統裡常常會同時存在：

硬性限制（Hard Constraint）
軟性限制（Soft Constraint）／偏好（Preference）

硬性限制代表：

一定不能違反

例如：

• 一間實驗室不能同時借給兩個分組
• 教師或助教不能同時出現在兩間實驗室
• 32 人不能進入安全容量只有 24 人的實驗室

而 Preference 則比較像：

如果可以，希望盡量做到

例如：

• 避免早上八點
• 實驗課不要分散到太多天
• 避免同一組學生連上兩門長時間實驗課
• 教師或助教偏好星期三不排課

這時候問題就會慢慢變成：

先滿足必要條件，再在合法答案中盡量滿足偏好

這也是很多真實系統實際上在做的事情。

---

為什麼不能把所有組合都試一次？

假設我們有：

• 4 個實驗課分組
• 4 個時段

每個分組都有 4 種選擇。

可能的組合大約是：

4 × 4 × 4 × 4
= 256

256 看起來還好。

但如果變成：

20 個實驗課分組
10 個時段

單純只看時段分配，就已經可能有 10^20 種組合。
而現實中還不只時段，可能還要選：

time
laboratory
teacher / teaching assistant
student group

然後每選一次，又要檢查很多限制條件。

於是最單純的方法：

把所有可能全部列出來，再逐一檢查

很快就會變得不切實際。

---

不一定要等到全部排完才發現錯了

我們可以想像一種非常直覺的搜尋方式。
先替 Chemistry_A 選：

Chemistry_A = Mon_AM

接著替 Chemistry_B 選：

Chemistry_B = Mon_AM

結果馬上發現：

Chemistry_A 和 Chemistry_B
需要同一間化學教學實驗室

所以這組安排已經違反限制條件。

那麼我們其實沒有必要繼續安排：

Physics_A
Physics_B
...

因為無論後面怎麼排：

這條路都不可能變成可行解

所以我們可以立刻回頭：

Chemistry_A = Mon_AM
Chemistry_B = Mon_AM   ❌

改成：

Chemistry_A = Mon_AM
Chemistry_B = Mon_PM

如果這次沒有違反條件，就繼續往下。

這種：

選一個
檢查
不行就回頭
再試另一個

的直覺，其實就是一種我們前面已經碰過的搜尋思想：

回溯 Backtracking

它不是盲目地把所有完整答案都產生出來之後才檢查。

而是：

一旦知道目前這條路已經不可能成功，就提早放棄

---

限制條件其實也在幫我們縮小搜尋範圍

限制條件聽起來好像只是：

一堆很麻煩的限制

但換一個角度看，它們其實也提供了資訊。

例如：

Physics_B 只能使用 Physics_Lab
Physics_Lab 只有下午開放

那麼原本：

Physics_B:
Mon_AM
Mon_PM
Tue_AM
Tue_PM

就可以縮小成：

Physics_B:
Mon_PM
Tue_PM

如果負責教師星期二下午又沒空：

Physics_B:
Mon_PM

甚至都不用搜尋了，答案已經被限制條件推導出來。

所以好的解題方式不只是 更快地試答案，有時候更重要的是：

先利用限制條件，把根本不可能的候選答案排除掉

這跟我們這個系列一直在做的事情其實非常接近。
演算法不是突然變出一個答案，而是：

理解問題結構
↓
利用已知條件
↓
縮小可能範圍
↓
再搜尋剩下的答案

---

限制滿足問題的核心模型

所以今天的概念其實可以整理得非常簡單。

一個限制滿足問題，通常可以先想成三件事情：

• 變數 Variable
• 領域 Domain
• 限制條件 Constraint

例如實驗課排程：

Variable
→ 每一個實驗課分組

Domain
→ 每個分組可以選擇的時段、實驗室

限制條件
→ 同一間實驗室不能重複借用
→ 實驗室安全容量必須足夠
→ 共同修課的學生不能撞堂
→ 教師與助教的時間必須允許
→ 特定課程需要特定類型的實驗室

我們要做的就是：

替所有 Variable 從各自的 Domain 中選一個值，使所有限制條件都成立

如果成功，就得到可行解。
如果怎麼選都無法成立，無可行解。
而這本身也是一個答案。

---

有時候「找不到答案」才是最重要的結果

這個觀念其實不只適用於實驗課表。

例如員工排班：

• 每個班次至少需要三個人
• 某些員工不能上夜班
• 每人每週不能超過 40 小時
• 特定職位至少要有一位值班

機器排程：

• Machine A 不能處理 Product X
• Maintenance 時間不能工作
• 同一批工作有先後順序
• 工作必須在 deadline 前完成

會議安排：

• 所有人都要參加
• 會議室要容納 20 人
• 只能星期三
• 某人星期三上午沒空
• 另一人星期三下午沒空

最後系統可能得到的結果是沒有任何可行時段。
這不是演算法失敗，反而是演算法幫我們證明：

目前這組條件無法同時成立

這時候真正該做的事情，是決定：

哪一個限制條件可以被放寬？

---

先可行，再談最好

今天的問題和前幾篇有一個重要差別：我們暫時不問哪一個答案最好，而是先確認哪些答案能夠成立。

因為如果不存在可行解，也就沒有最佳解可以比較。實際系統通常會先排除不合法答案、找到可行解，再比較哪些安排更好。

例如實驗課表可以先滿足：

• 實驗室不能重複借用
• 實驗室安全容量足夠
• 共同修課學生不能衝堂

接著才考慮：

• 學生等待時間更少
• 教師與助教偏好
• 實驗室利用率
• 課程分布

也就是：

限制條件
↓
可行解
↓
最佳化目標
↓
較佳解

這也是許多真實工程問題共有的兩層結構：

先滿足不能違反的條件，再從可行解中尋找更好的安排

---

從排課問題帶走的模型

今天沒有深入某一種完整的實驗課排程演算法，重點是學會辨認這類問題的共同結構：

• 很多東西需要被決定
• 每個東西都有一些可能選項
• 這些選擇之間又存在很多限制

你可以開始想到：

• 變數 Variable
• 領域 Domain
• 限制條件 Constraint

把這三個部分釐清之後，我們就能進一步判斷：

是否存在一組安排，可以讓所有必要條件同時成立

---

下一篇，我們會再把問題往前推一步。
假設我們已經找到了很多可行答案，但現在我們要做的是推薦內容。
我們可能希望推薦結果和使用者興趣相關，但又不能全部太相似。
還希望保有一定的多樣性，同時平台可能還有自己的商業目標。
這時候，「最好」突然就不再只有一個方向。
下一個問題會變成：

找到可行解之後，如果「好」同時包含相關性、多樣性與商業目標，我們又要如何定義最好？