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() { }
}

简化代码。目的只是为了传达这个想法

所以，我有一台处理工作的机器。工作需要工具（而且工具的生命周期是无限的）。我的目标是找到一个最小的作业和命令列表（即和的实例），以便可以处理给定AddTool的RemoveTool固定作业列表。工作不需要的工具可以留在机器上（当然只要有足够的空间）。{"AddTool(x), "job1", AddTool(y), "job2"}

我有两种方法：

  • 简单的

收集从工作到工作的需求。由于这种方法只考虑 jobi和 job i + 1。i + 1在机器卸载作业不需要但作业需要的工具的情况下，这可能不是最佳选择i + 2。这是一个不必要的删除和添加循环（假设有可能删除另一个不需要的工具）。

  • 启发式

使用启发式算法，例如模拟退火，最大限度地减少使用的命令数量。

我宁愿使用直截了当的方法。但我想不出另一个，我猜这个简单的方法效率太低了。

那么我该如何解决我的问题呢？它如何按照计算机科学进行分类？我也很欣赏这类问题的一般解决方案，这些问题不专门处理工作、机器和工具。

4

1 回答 1

3

这是一个哈密顿路径问题，或者可能是一个旅行商问题（如果你稍微修改一下问题）。每个工作都需要一定数量的工具，您可以确定从一个工作到另一个工作需要多少命令。您希望通过该图的路径最小化添加/删除方面的“距离”并访问所有节点/作业。

于 2013-09-11T12:00:31.657 回答