3

この O(n!) スケジューラの問題があるとします。

  • 期間が異なる 10 個のタスクがあり、週 5 日間にスケジュールを設定したい
  • 毎日 8 時間の作業時間があり、15 分に分けられます。スロット (1 日 = 8 時間 = 32 スロット)
  • タスクには、「許可される日と時間の範囲」に関して異なる要件があります (たとえば、あるタスクは木曜日の午前 8 時から午前 9 時までの間のみ許可され、別のタスクは月曜日、火曜日、水曜日の午前 10 時から午前 11 時までのみ許可されます)。

要求された結果: 後で追加/他のタスクを割り当てるために利用可能な「連続した空きスロット」ができるだけ多くある必要があります

現在の解決策: BFS/DFS ソリューションを介して可能なすべてのスロットを結合しようとしましたが、その後、タスクと「空きスロットの最大のチャンク」を重複させずに最適な組み合わせを見つけました。このソリューションは、O(n!) の複雑さのために、パフォーマンスおよび/またはメモリに関して私を殺します。

質問: 限られた時間内にこの問題を解決するために、コンピュータ サイエンスが提供しなければならない (または、以前にこのような問題を解決した可能性がある) 最も「合理的な」アプローチは何ですか。

4

6 に答える 6

1

タスクの制限 (許可される日と時間の範囲) のため、(再帰的な) バックトラッキングを使用します。

ウィキペディアから ( http://en.wikipedia.org/wiki/Backtracking ):

バックトラッキングは、計算上の問題のすべての (または一部の) 解を見つけるための一般的なアルゴリズムであり、解の候補を段階的に構築し、c を完全に完成させることができないと判断するとすぐに、各部分候補 c を破棄します (「バックトラック」)。有効なソリューション。

あなたの問題のために。すべてのタスクにスケジュール可能な日数を割り当てましょう。これが一般的な解決策です。

M[レベル] はサブ問題の可能な解の集合を意味します (R[レベル])

Backtracking(level = 0, result={0})
i = 0
Do
    i = i + 1 
    //With i - iterate over the possible solutions to result[level] (iterate over M[level])
    If(R[i] is a good result candidate) 
        k = 1
        While(k<level AND (R[k],R[i] are good solutions together)) k++
        If(k == level) //R[i] is a good result, it's in harmony with the results found before
            result[level] = R[i]
            If(level == N)
                bestResult = Max/Min(bestResult,result)
            Else
                Backtracking(level+1,result) //Backtracks
While(i<M[level])
于 2013-06-23T21:06:26.863 に答える
-1

私は常に、一般的な方法論に頼るよりも、問題に対するカスタム ソリューションを作成することを好みます。この特定のケースでは、問題は非常に明確に定義されており、比較的簡単に定義できる迅速で信頼性の高い反復手順があると思います。完了しました。

アルゴリズムは、利用可能な (5) 日間を反復し、割り当てられた各タスクに関連付けられた時間を合計し、その結果の加算を特定の日の残りの利用可能な時間と比較します。これは、次の 2 つの主要部分で構成されます。

  1. 最優先の割り当て。最初に、アルゴリズムは特定の日の「柔軟性」を計算します。つまり、特定の日に実行する必要があるタスクのすべての時間枠を合計します。彼らが利用可能な時間をすべて使い果たした場合、これらすべてのタスクの割り当てはすぐに行われ、翌日に直接スキップされます. 利用可能な時間がある場合、アルゴリズムは詳細な (時間/日) 定義を持つタスクのみを割り当てます。例: 指定されたスロットを含む月曜日に実行されるタスク (例: 9 時から 9 時 15 分)。詳細に定義されたすべてのタスクの割り当てが完了すると、その日に実行する残りのタスクに必要な全時間が合計されます。この値は、以下で「その日の残り」と呼ぶものです。このグループに属するタスク (つまり、

  2. デフォルトの優先ルール。上記のポイントで特定の日にすべての利用可能な時間を割り当てていない場合、すべてのタスク (特定の日にフラグが付けられた前述のタスクに属さない) の新しい反復が、一般的な優先ルールのシステムを適用することによって開始されます。 (以下の例で説明)。新しいタスクを割り当てる前に、アルゴリズムは、すべての「その日の残り」を説明するのに十分な時間が残っているかどうかを確認します。新しく割り当てられるタスクが利用可能な時間を使い果たした場合 (つまり、「その日の残りのタスク」が割り当てられるのを回避した場合)、アルゴリズムは「優先タスク」(「残りのタスク」に属さないタスク) を反復し続けます。割り当てが利用可能な時間を枯渇させないものを見つけるまで。そのようなタスクが見つからない場合は、

ポイント 2 の優先規則の例: 月曜日の 9 時から 9 時 15 分までの時間帯。まず、その日に個別に特定の時間に割り当てられたタスクを調べます (これらのケースは既にポイント 1 で管理されているため、月曜日にはなりません)。次に、月曜日に実行される可能性のある最大のタスク (より多くのスロット)。この最後の状況にある場合は、タスクのランキングを作成することもできます (たとえば、サイズによる最後の順序付けを開始する場合、タスク X は月曜日に最大の優先度を持ちます)。

上記のアルゴリズム (またはこれらの行の他のアルゴリズム) は、あなたが抱えている問題に対して私が思いつくことができる最も迅速なオプションを表しています。これは主に速度と信頼性に重​​点を置いているため、「多くの連続した空きスロット」の制約は完全には最適化されていません。それらを作成する傾向がありますが（主に週の最後の日に）。それにもかかわらず、この最後の問題は、ポイント 2 のルール (主に時間サイズによって割り当てられたタスクのルール) の詳細レベルを上げることでさらに改善される可能性があります。要約すると、これらのアプローチは、あなたが提案する問題に対して最良の解決策をもたらすと思います。

于 2013-06-23T10:20:39.423 に答える