我认为如果我先展示我的代码会更容易。
/* 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。模拟退火,最大限度地减少使用的命令数量。
我更喜欢使用直接的方法。但我想不出其他的办法,而且我猜这种简单的方法效率太低了。
那么我该如何解决我的问题呢?从计算机科学的角度如何分类?我也希望能得到针对此类问题的通用解决方案,这些问题并不专门处理工作、机器和工具。
最佳答案
这是一个hamiltonian path problem ,或者可能是 Traveling Salesman Problem (如果你稍微修改一下问题)。每项工作都需要一定数量的工具,您可以确定从一项工作转移到另一项工作需要多少命令。您需要一条穿过该图的路径,以最小化添加/删除方面的“距离”并访问所有节点/作业。
关于java - 如何找到满足要求的最小操作集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18740265/