java - 如何找到满足要求的最小操作集

Question

我认为如果我先展示我的代码会更容易。

/* 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"})，以便可以处理给定的固定作业列表。作业不需要的工具可以保留在机器上(如当然，只要还有足够的位置)。

---

我有两种方法:

• 简单

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

• 启发式

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

我更愿意使用直接的方法。但我想不出另一种方法，我想这种简单的方法效率太低了。

那么我该如何解决我的问题呢？如何根据计算机科学对其进行分类？对于此类问题的通用解决方案，我也很感激，这些解决方案并不专门处理工作、机器和工具。

Answer 1

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