可能な限り多くのイベントに対応するアルゴリズム

Question

これらの重複しないイベントを可能な限りスケジュールに配置できるアルゴリズムを見つけることを考えています（これらのイベントのいずれかを追加したり削除したりすることができます必要に応じてスケジュール）。これらの事象はいずれも重複することはできませんが、私は可能な限り毎日のスケジュールにそれらの多くに合うようにしたい：

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 

私はしばらくの間、この問題について考えてきた、と私はまだ方法について見当がつかない私はそれを解決する必要があります。どのようなタイプのカレンダースケジューリングアルゴリズムがこの場合最も効果的でしょうか？

Answer 1

を獲得した[X]順列配列のイベントの可能な重複しない組み合わせをすべて生成します。この配列から、可能な限り多くのイベントを含む範囲である範囲の最大の配列を抽出できます。

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; 
    } 
} 

Answer 2

梱包期間は1日の長さになります。あなたはあなたの問題の可能な解決策を見つけ出し、あなたがそれを詰め込んで管理する期間の数に応じてそれを評価したいと考えています。

1. 午前1時から午後10時までは21 * 4フレームになるように1日を15分間隔で分割します。
2. 制約で可能なすべての置換を生成します（フレームの重複はありません）。有効な各順列に対して
3. 、あなたに合うように、管理期間の数を数える。
4. 印刷私は配列を受け取りgenerateCombinationと呼ばれる関数を書いて、最高

Answer 3

私は、動的プログラミングソリューションだと思います。..については

、イベントなどのB：F（A）>（B）〜期間（a）の<期間F（B G Fと（X）> G（Y）〜ナンバー・オブ・イベント（X）>ナンバー・オブ・イベント（Y）

ダイナミックプログラミング（イベント）：スケジュールとしてY X用）

、 g（予定）以上。最適なスケジュールを見つけるには

Answer 4

OTOH私は2つの適切な解決策、計画アルゴリズム、PopPlanまたはGraphPlanを考えることができます。もう1つは、シミュレーテッドアニーリングを使用することができます。