班級調度

Question

問題是這樣的：

一所學校有不同的班級。每班有一個每週的時間表（英語8小時，數學6小時，藝術2小時等）。每個老師在班級中都有一定的小時數。 （我想學校幾乎到處都是這樣的）。

一些額外constraits可以加入，例如：

1. 老師X將不會在週一上班
2. 老師的Y某一類 等需要連續兩小時。

目標是找到一個優化約束成本函數的計劃。

最後，這是一個重要的NP問題，我猜。它可以使用空間狀態搜索來解決（我們嘗試所有可能的組合，使用一些聰明的搜索方式，並且我們選擇可能的最佳解決方案）。

• 這可行嗎？ （組合是巨大的，對於10個班級和每個班級30個小時，7個科目大約10^253，即使可能有一些實質性的修剪：我想SAT解決者可以處理類似的事情）。

• 即使近似，是否有任何替代項可以完成搜索？

Answer 1

這是一個 Constraint Satisfaction Problem。如鏈接所述，解決這些問題的方法之一是使用本地搜索方法，如min-conflicts或forward checking。您無法保證獲得最佳解決方案，但您通常會在相對較短的時間內獲得「良好」的解決方案。

如果您碰巧使用Prolog，clpfd庫（有限域上的約束邏輯編程）功能非常強大。