2

学生を最寄りの試験センターにグループ化するのに問題があります。条件/制約は次のとおりです。

  1. X 人の学生と Y 試験センターがあります。各センターは異なる数の学生を収容します。
  2. 試験センターの合計の最大キャパシティは、学生の数よりも大きくすることができますが、小さくすることはできません。
  3. 学生は、複数の試験センターまでの最短距離を持つことができます。
  4. 試験は、すべての試験センターで同時に開催されます。

たとえば、11500 人の学生と 15 の試験センターがあります。5 つのセンター (1 ～ 5) は 1500 人の学生を収容し、3 つのセンター (6 ～ 8) は 600 人、残りの 7 つのセンター (9 ～ 15) は 350 人の学生を収容します。

私は以下を開発しました：

  1. 各試験センターへの学生の所在地 (登録住所) を含むデータベース テーブル。以下のようなもの

    Student ID  Dist-Ex1  Dist-Ex2 ... Dist-Ex14  Dist-Ex15
1            10         70            20         50
2            25         43            5          105
...
11499        35         12             35         55
11500        5          23              5         5

  2. 各学生に最寄りの試験センターを格納する列を追加して、次のようなテーブルを作成できます。

    Ex centers           Nearest for no. of students
1                     2000
2                      500
...
14                     150
15                     500

しかし、私はさらに進む方法がわかりません。ある種のアルゴリズムの問​​題だと思います。誰かが私に何か考えを与えてくれたら、私は感謝します。

よろしくお願いします！

4

3 に答える 3

1

あなたが最適な解決策を探していることは理解しています- (すべての学生は最寄りの試験センターに割り当てられます)。このために、問題を最大フロー問題に減らします。

(すべての学生、すべての試験センター、および 2 つの余分な頂点 S と T) の ような2 部1グラフに問題を減らします。(S はすべてのセンターに接続され、すべての学生は T に接続され、CLOSESTS - これについては後で説明します)。 どこG=(V,E)V = {students} U {examination centers} U {S,T}
E = CLOSESTS U {S} X {examination centers} U {students} X {T}
CLOSESTS = { (exam,stud) | exam is the closest examination center to the student sutd}

f:E->N次のような重み関数も必要です。

f(u,v) = capcity if u=S, v=examination center
f(u,v) = 1 if u is examination center and v is student
f(u,v) = 1 if u is student and v is T

結果のグラフは、次のサンプルのようになります。

ここに画像の説明を入力次に、 edmonds-karp などの最大フロー アルゴリズムを実行します。T が #num_studets である最大フローが「入る」場合、最適解があり、アルゴリズム2によって達成されるフロー ネットワークによって示されます。max-flow アルゴリズムは、各エッジに入れるフローの量を見つけます。これは、容量制限を破ることなく、学生をセンターに割り当てる方法と同じです。

証拠：

  • #students の最大フローがある場合、すべてのエッジ (student,T) が使用され、すべての学生に着信フローがあるため、割り当てられます。また、各試験センターには最大でも 1capcity人の学生が割り当てられており、解は有効です。
  • 最大フローが #students よりも小さい場合、試験センターからフローを受け取らなかったために割り当てられていない学生が存在し、最適なソリューションはありません。

(1) S と T を追加したため、正確には二部グラフではありません。
(2)積分フロー定理によると、すべての重みは整数であるため、積分解があります。

于 2012-09-20T07:20:21.073 に答える
0

遺伝的アルゴリズムについてはこちらをご覧ください。

学生の母集団とその課題を取り上げると、フィットネス関数は重複が少なく学生により大きな価値を与えることができます。

このように大学にいる間に学生/スケジューリングの問題を実装しましたが、かなりうまくいきました。

だから私は遺伝的アルゴリズムがここに行く方法だと信じています

幸運を！

于 2012-09-20T07:08:09.563 に答える