いくつかの基準を持つグループでクラスを分割する可能性

Question

5人ずつの10の異なるディスカッショングループに論文を書く50人のクラスのクラスを分割する必要があります。理論的には、これは、{50！}/{（5！^ 10）* 10！}}の結果である1.35363x10^37の可能な方法があります。 5.

ただし、各グループはファシリテーターによって指導されます。これは、可能性のある組み合わせの数を大幅に減らします。なぜなら、各ファシナは、5つの可能なファシリティの中から1つの専門分野を持ち、生徒ができるだけ書くトピックに一致させる必要があるからです。能力Aのファシリテーターが3人、能力Bの人が3人、能力Cの人が2人、能力Dの人と能力Eの人がいて、15人がA、15からB、10からC、5からD、5可能な組み合わせの数は252 505に減少します。

しかし、学生とファシリテーターは両方とも専門分野に焦点を当てるのではなく、より多くの基準の使用を提唱し続けます。たとえば、お互いを知っている学生のグループにいたい、または具体的な調査方法の特定の知識を持っているファシリテーターと一緒にいるグループにいたい。

私は直感的な推論を説明しようとしていますが、目的が完全に効率的な解決策であれば、それぞれの新しい基準がタスクの複雑さ/不可能性を高めることがわかります。しかし、私はこれを分析的に満足のいく方法で表現することに頭を下げることはできません。

私の推論は正しく、基準を追加すると包含 - 除外の原則に従って捨てられる可能性が減り、タスクが複雑になり、可能な組み合わせが追加されますか？私は、基準が適合しない場合（例えば、お互いを知っている生徒が異なる話題について書いており、十分な有能なファシリテーターがいない場合など）、一定の制約が可能になると考えています。

Answer 1

計算の複雑さと人間の複雑さを区別する必要があります。制約を追加すると、問題の人間の複雑さがほぼ自動的に増加します。というのも、あなたの心を包み込むほど多くのことがあるという意味です。しかし、計算の複雑さが増すことは事実ではありません。少なくとも時々それは減少する。

たとえば、200個のアイテムのセットがあり、いくつかの制約を満たすサブセットがあるかどうかを判断したいとします。制約に応じて、実現可能な方法がないかもしれません。結局のところ、2^200はです。は無理強いです。ここで、サブセットが正確に3つの要素を持つ必要があるという制約を追加します。今すぐ突然それはブルートフォース（あなたが解決策を見つけたり、存在しないと判断するまで、1,313,400の3要素サブセットをすべて実行すること）が可能です。これは、制約を追加することが常に問題を本質的に困難にすることは事実ではないことを示すのに十分である。離散的なケースでは、新たな制約が悪用される可能性のある方法で検索スペースのサイズを減らすことができます。連続的な場合には、自由度を減らして問題の次元を小さくすることができます。これは常により簡単になると言うわけではありません。おそらく経験則として、追加の制約はの傾向があり、問題をもっと難しくしています。

あなたの実際の問題は具体的なアドバイスをするのに十分なものではありません。 1つの可能性（および幾分外来的な制約の拡散を扱う1つの方法）は、制約を厳密に満たす必要のある硬い制約と厳密には必要でないだけの柔らかい制約とに分割することである。それを最適化問題に変えます。ハード制約を満たすという条件を満たす、満たされるソフト制約の数を最大にする解を見つけます。おそらく、あなたはinteger programmingの問題としてそれを策定し、うまくいけば正確な解を見つけることができます。あるいは、ハード制約を満たす解を生成することが容易であり、そのような解を別の解を得るために変更することが容易である（例えば、異なるグループに属する2人のスワップを交換する）場合、evolutionary algorithmは合理的なヒューリスティックである。