2

最初にコードを示した方が簡単だと思います。

/* Machine that can add and remove pools to its stack */
public class Machine {
  private final int toolQuantity = 5;
  public boolean addTool(Tool t)    { return true; }
  public boolean removeTool(Tool t) { return true; }
  public boolean processJob(Job j)  { return true; }
}

/* Tool that is needed to process jobs */
class Tool {
}

/* Job that needs specific tools to be processed on machine */
class Job {
  private final List<Tool> needs = Collections.emptyList();
}

interface Command { public void execute(); }

class AddTool implements Command {
  private Machine m;
  private Tool t;
  @Override
  public void execute() { }
  }

class RemoveTool implements Command {
  private Machine m;
  private Tool t;
  @Override
  public void execute() { }
}

シンプルなコード。目的は単にアイデアを伝えることでした

だから、私はジョブを処理するマシンを持っています。ジョブにはツールが必要です (ツールの寿命は無制限です)。私の目的は、ジョブとコマンドの最小限のリスト (つまり、AddToolandのインスタンス) を見つけて、ジョブの特定の固定リストを処理できるようにすることですRemoveTool。ジョブに必要のないツールは、マシン上に残すことができます (もちろん、十分なスペースが残っている限り)。{"AddTool(x), "job1", AddTool(y), "job2"}

私には2つのアプローチがあります：

  • 単純

ジョブからジョブへの要件を収集します。このアプローチは jobiと jobのみを考慮するためi + 1です。i + 1マシンが、ジョブには必要ないがジョブには必要なツールをアンロードする場合、最適ではない可能性がありますi + 2。これは、削除と追加の不必要なサイクルです (別の不要なツールを削除する可能性があることを考えると)。

  • ヒューリスティック

シミュレートされたアニーリングなどの発見的アルゴリズムを使用して、使用するコマンドの数を最小限に抑えます。

私は直接的なアプローチを使用することを好みます。しかし、私は別のものを考えることができず、単純なアプローチはあまりにも非効率的だと思います.

では、どうすれば問題を解決できますか？コンピュータサイエンスの観点からはどのように分類できますか? また、ジョブ、マシン、およびツールを具体的に処理しない、この種の問題に対する一般的な解決策もありがたいです。

4

1 に答える 1

3

これはハミルトニアン パス問題、または巡回セールスマン問題(問題を少し修正した場合) です。各ジョブには一定量のツールが必要であり、あるジョブから別のジョブに移動するために必要なコマンドの数を決定できます。追加/削除に関して「距離」を最小化し、すべてのノード/ジョブを訪問する、そのグラフを通るパスが必要です。

于 2013-09-11T12:00:31.657 に答える