6

これらの重複しないイベントをできるだけ多くスケジュールに配置できるアルゴリズムを見つけようとしています (これらのイベントは必要に応じてスケジュールに追加または削除できます)。これらのイベントは重複できませんが、できるだけ多くのイベントを毎日のスケジュールに組み込みたいと考えています。

12:00 PM - 12:45 PM: Lunch

1:00 AM - 3:00 AM: Math class 1

3:30 PM - 5:00 PM: Math class 2

7:00 PM - 10:00 PM: History class 1

9:00 PM - 11:00 PM: History class 2

Any time of day: Grocery shopping, 40 minutes

Any time of day: Study math for 30 minutes

Any time of day between 11:00 AM and 4:00 PM: Basketball practice for 2 hours

私はしばらくこの問題について考えてきましたが、どうすれば解決できるのかまだわかりません。この場合、どのタイプのカレンダー スケジューリング アルゴリズムが最も効果的でしょうか?

4

4 に答える 4

2

整数範囲の配列を入力として取り、配列内のイベントの重複しない組み合わせをすべて生成する、generateCombination という関数を作成しました。この配列から、最大数のイベントを含む範囲である範囲の最大配列を抽出できます。

http://jsfiddle.net/nvYZ8/1/

var theArray = generateCombination([[0, 2], [2, 3], [4, 5], [0, 9], [2, 50]]);
alert(JSON.stringify(theArray));

function generateCombination(theArray) {
    var theString = "";
    var tempArray = new Array();
    for (var i = 0; i < theArray.length; i++) {
        theString += "1";
    }
    var maximumNumber = convertFromBaseToBase(theString, 2, 10);

    for (var k = 0; k <= maximumNumber; k++) {
        theString = convertFromBaseToBase(k + "", 10, 2);
        while(theString.length != theArray.length){
            theString = "0" + theString;
        }
        var theResult = getArray(theArray, theString);
        if(theResult != false){
            tempArray[tempArray.length] = JSON.stringify(theResult);
        }
    }
    return tempArray;
}

function getArray(theArray, theString){
        var tempArray = new Array();
    for(var i = 0; i < theArray.length; i++){
        if(theString[i] == 1){
            tempArray[tempArray.length] = theArray[i];
        }
    }
        for (var i = 0; i < theArray.length; i++) {
            for (var j = i; j < theArray.length; j++) {
                if ((j != i) && (theString[i] == 1) && (theString[j] == 1)) {
                    //check whether theArray[i] overlaps with theArray[j]
                    var overlaps = rangesOverlap(theArray[i][0], theArray[i][1], theArray[j][0], theArray[j][1]);
                    //if overlaps is true, break out of the current loop
                    //otherwise, add theArray[j] to tempArray
                    if(overlaps == true){
                        return false;
                    }
                }
            }
        }
        return tempArray;
}

function convertFromBaseToBase(str, fromBase, toBase) {
    var num = parseInt(str, fromBase);
    return num.toString(toBase);
}

function rangesOverlap(x1, x2, y1, y2) {
    if (x1 <= y2 && y1 <= x2) {
        return true;
    } else {
        return false;
    }
}
于 2013-05-20T05:18:54.113 に答える
2

梱包期間を 1 日の長さにビン詰めします。問題の可能な解決策を見つけて、それに詰め込むことができた期間の数に応じてそれらを評価したいと考えています。

  1. 午前 1 時から午後 10 時までは 21 * 4 フレームになるように、1 日を 15 分間隔で分割します。
  2. 制約で可能なすべての順列を生成します (フレームのオーバーラップはありません)。
  3. 有効な順列ごとに、なんとか収まった期間の数を数えます。
  4. 最高得点の [x] 個の順列を出力する
于 2013-05-20T03:52:41.680 に答える
0

動的計画法が解決策だと思います..

イベントとしての a、b の場合: f(a) > f(b) ~ duration(a) < duration(b)

スケジュールとしての x、y の場合: g(x) > g(y) ~ Number-Of-Events(x) > Number-Of-Events(y)

g(スケジュール) 上の f(イベント) を使用した動的計画法; 最適なスケジュールを見つけるために

于 2013-05-20T08:52:55.047 に答える