類布爾到布爾可滿足性[多項式時間減少]第2部分

Question

我問幾天前，一個關於如何將大學課堂排序問題轉換爲布爾可滿足性問題的問題。

（Class Scheduling to Boolean satisfiability [Polynomial-time reduction]）

我通過@Amit回答誰是非常優雅，易於代碼。 基本上，他的答案是這樣的：他不考慮課程，而是考慮時間間隔。

因此，對於第i個課程，他只是指出了本課程的所有可能的時間間隔。當每個課程至少有1個真實時間間隔並且沒有時間間隔與另一個時間間隔重疊時，我們可以得到一個解決方案。

當我們只考慮課程而不考慮其他因素時，這種方法效果很好。我通過在區間內對房間進行編碼來概括它。

例如，而不是[8-10]說，課程可能發生在上午8點到上午10點之間。

我用[0.00801 - 0.01001]說一門課程可以在房間上午8時和10時之間發生1

我敢肯定，你目前徘徊「爲什麼雙用？」那麼，因爲這裏來我的問題：

爲了繼續推廣這種方法，我編碼也在這個區間的老師的n°。

我用[1.00801 - 1.01001]表示一個課程可以在房間1的早上8點到上午10點之間發生，並由老師n°1教授。

這裏是我得到了現在：

這樣[1.008XX - 1.010XX]可以在同一時間發生[2.008YY - 2.010YY]，這是真的，如果老師1在上午8點到上午10點在教室X教學，老師2也可以在上午8點到上午10點之間教授Y，當且僅當房間可用時。

問題是：使用這種方法我不能確保XX和YY會有所不同，並且YY將可用，因爲[1.008XX - 1.010XX]不會重疊[2.008XX - 2.010XX]，所以對於現在，解決者認爲這是可能的。

我仍然沒有就如何確保這一點，通過使用此區間方法任何線索...... 我需要一種方法，以便編碼{間隔，房間和老師-ID}指出：

• 老師不能在同一間隔的2個地方。
• 在相同的時間間隔內，同一個房間中不能有2位教師。
• 當然，至少有1個區間是真的。

在此先感謝您的幫助， 此致敬意！

---

後續問題：Class Scheduling to Boolean satisfiability [Polynomial-time reduction] Final Part

Answer 1

這個答案是Part 1's answe爲r的擴展，並使用在相同的標記可能。好吧，假設每個時間間隔都分配給一位教師（如果不止一位教師可以採取這個時間間隔，只是有多個實例，每個實例有不同的教師），所以表示教師t在教室p時間x到y，我們可以使用這個類給出的舊變量 - V_{i,j} - 類和間隔。

對於每個教師t，並且對於每對間隔c=(x1,y1)，d=(x2,y2)類中的（A，B）的老師可能參與，添加子句：

Q_{t,i,j} = Not(V_ac) OR Not(V_bd) OR Smaller(y1,x2) OR Smaller(y2,x1) 

直觀地說，在上述條款保證了教師不能在兩個地方同時進行 - 沒有間隔重疊，同一位老師被分配給他們。

通過鏈接每一對(i,j)每個老師t與和原來的公式，它滿足你的第一個條件 - a teacher cannot be in 2 places in the same interval. - 因爲每個老師不能在同一時間兩個地方。

你的第二個約束there cannot be 2 teachers in the same room for the same interval.也由一個事實，即不能有重疊的時間和類兩類滿足。

第3個約束there is a least 1 interval true by course.由F1子句滿足，因爲您必須爲每個課程至少選擇一個時間間隔（只分配一個教師）。