生徒のランダムなグループを生成するプログラムでは、特定の生徒を強制的にグループ化するオプションと、生徒のペアリングをブロックするオプションをユーザーに提供します。これを実現するための独自のアルゴリズムを作成するために2日間試みましたが、すべての再帰で迷子になります。私はLuaでプログラムを作成していますが、あらゆる種類の擬似コードを理解することができます。生徒の並べ替え方法の例を次に示します。
students = {
Student1 = {name=Student1, force={"Student2"}, deny={}};
Student2 = {name=Student2, force={"Student1","Student3"}, deny={}};
Student3 = {name=Student3, force={"Student2"}, deny={}};
}-- A second name property is given in the case that the student table needs to be accessed by students[num] to retrieve a name
次に、一時テーブルを作成します。
forced = {}--Every student who has at least 1 entry in their force table is placed here, even if they have 1 or more in the deny table
denied = {}--Every student with 1 entry for the deny table and none in the force table is placed here
leftovers = {}--Every student that doesn't have any entries in the force nor deny tables is placed here
unsortable = {}--None are placed here yet -- this is to store students that are unable to be placed according to set rules(i.e. a student being forced to be paired with someone in a group that also contains a student that they can't be paired with
SortStudentsIntoGroups()--predefined; sorts students into above groups
すべての生徒がそれらのグループに配置された後（彼らもまだ生徒テーブルに残っていることに注意してください）、グループにペアになることを余儀なくされている生徒を挿入することから始めます（まあ、私はしようとしました）、1つある生徒を挿入します拒否テーブルの複数のエントリを配置可能なグループに入れ、残りのグループを残りで埋めるだけです。
役立つことがいくつかあります。
numGroups--predefined number of groups
maxGroupSize--automatically calculated; quick reference to largest amount of students allowed in a group
groups = {}--number of entries is equivalent to numGroups(i.e. groups = {{},{},{}} in the case of three groups). This is for storing students in so that the groups may be displayed to the end user after the algorithm is complete.
sortGroups()--predefined function that sorts the groups from smallest to largest; will sort largest to smallest if supplied a true boolean as a parameter)
前に述べたように、このための再帰的アルゴリズムを設定する方法がわかりません。強制された生徒を一緒に挿入しようとすると、同じ生徒が複数のグループに入れられたり、強制されたペアがペアになっていないなどの結果になります。形式にも注意してください。各学生の強制/拒否テーブルには、対象の学生の名前が示されています。学生への直接の参照ではありません。どのような種類のアルゴリズムを使用する必要がありますか（この場合に存在する場合）？どんな助けでも大歓迎です。
ここでNP困難な問題に直面しているように私には思えます。
これは、エッジが拒否リストである色のグラフ彩色の問題と同等kです。
グラフ彩色：
Given a graph G=(V,E), and an integer `k`, create coloring function f:V->{1,2,..,k} such that:
f(v) = f(u) -> (v,u) is NOT in E
グラフ彩色から問題への削減：
グラフ彩色の問題(G,k)が与えられたG=(V,E)場合、次のようにして問題のインスタンスを作成します。
students = V
for each student: student.denial = { student' | for each edge (student,student')}
#groups = k
直感的には、各頂点は学生によって表され、学生は、それらを表す頂点の間にエッジがあることをすべての学生に否定します。グループの数は、指定された色の数です。
さて、あなたの問題の解決策を考えるkと、学生が学生をu拒否した場合v、それらは同じグループに属していないというグループが得られますが、これは色付けuと同じでありv、異なる色であるため、元の各エッジ（u、v）についてグラフ、uおよびv異なる色です。
逆も同様です
したがって、ここでグラフ彩色問題からの多項式還元を取得しました。したがって、問題の最適な解決策を見つけることはNP困難であり、この問題に対する既知の効率的な解決策はなく、ほとんどの場合、解決策は存在しないと考えられます。
いくつかの代替案は、最適な解決策を提供しない遺伝的アルゴリズムなどのヒューリスティックを使用するか、時間のかかるブルートフォースアプローチを使用します（これは多数の学生には実行できません）。
強引な力は、kグループへのすべての可能な分割を生成し、それが実行可能な解決策であるかどうかを確認します。最後に、見つかった最良の解決策が選択されます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加