按照幾個標準劃分班級的可能性

Question

我必須將一組50名學生分爲10個不同的討論組，每個討論組5個成員。理論上，這樣做有1.35363x10^37種可能的方式，這只是{50！}/{（5！^ 10）* 10！}}的結果，如果已經確定這些組將由5.

但是，每個小組由一個協調員領導。這大大減少了可能的組合數量，因爲每個促進者都有5個可能的專業領域中的一個專業領域，應該儘可能與學生正在寫的主題相匹配。如果有三名具有能力A的協調人，其中三人具有勝任能力B，兩人具有勝任能力C，一人具備勝任力D，一人勝任E，另外15人被分配到A，15至B，10至C，5至D和5到E，可能組合的數量降至252,505。

但是，學生和協助者一直主張使用更多標準，而不是專注於專業領域。例如，想要加入一羣相互瞭解，或與一個對特定研究方法具有特定知識的調解人的小組中。

我想說明我的直覺推理，告訴我如果目標是完全有效的解決方案，每個新標準都會增加任務的複雜性/不可能性。但我無法以令人滿意的方式分析性地表達這一點。

我的推理是否正確：添加標準會減少包含 - 排除原則後可能丟棄的可能性的數量，從而使任務更加複雜，增加可能的組合？我還認爲，如果標準不一致（例如，如果學生彼此認識的是關於不同主題的寫作，而且沒有足夠的主管協調員），則某些限制變得不可行。

Answer 1

您需要區分計算複雜性和人的複雜性。添加約束幾乎會自動增加問題的人類複雜性，因爲這意味着還有更多需要圍繞的問題。但是 - 計算複雜度增加並不是真的。至少有時會減少。

例如，假設您有一組200個項目，並且您想確定是否存在滿足某些約束的子集。根據約束條件，可能沒有可行的方法來做到這一點。畢竟2^200是太多太大而不能蠻力。現在添加子集需要的確切3個元素的約束。現在突然它是可能的蠻力（只是通過所有1,313,400 3元素的子集運行，直到你找到一個解決方案或確定沒有存在）。這足以表明，添加約束始終使問題內在地變得更加困難是不正確的。在離散情況下，新的約束可以減少搜索空間的大小，從而可以被利用。在連續的情況下，它可以減少自由度，從而降低問題的嚴重程度。這並不是說它總是使它更容易。可能根據經驗，額外的限制傾向於使問題更加困難。

您的實際問題未提供足夠的具體建議。一種可能性（以及一種處理多餘無關約束的方法）是將約束劃分爲需要滿足的硬約束和僅僅需要而非嚴格需要的軟約束。將其轉化爲一個優化問題：找到滿足軟約束條件數量最大化的解決方案，並滿足嚴格約束的條件。也許你可以將它制定爲integer programming問題，並希望找到一個確切的解決方案。或者，如果生成滿足嚴格約束條件的解決方案很容易，並且很容易使一種解決方案發生變異以獲得另一種解決方案（例如交換兩個不同組的學生），那麼evolutionary algorithm將是合理的啓發式。