计算复杂生产线未来合格数量的算法
Algorithm for calculation of future good amounts with complex production lines
这篇文章很长post，但真正相关的只有前半部分。
后半部分仅描述了我试图解决的问题，但在我看来效率太低（它可能有助于了解我想要什么）。相关部分以粗体问题后的行结束。
我正在尝试在一个假想的工厂中模拟多次生产，以计算最终每种已知类型的商品数量。有几种不同的商品类型，它们都有特定的最大生产能力，只有在有足够的原料可用时才能达到。生产线的外观示例如下：
底部的货物都有一个已知的送达工厂的速度，所以对于那些，没有什么可计算的，虽然这个速度会随着时间而变化（另外，最大生产能力也可以随时更改，例如，可以通过添加工人或更多机器来增加容量）。
如图所示，其他商品看三点：
- 一些线路产生了一个好的其他线路。
- 一些线产生了另外两条线。
- 一些行有一个好的用于创造不止一个新的商品
（例如，参见插图中间的“R8”）。
我有以下信息：
- 每种商品的最大生产率（例如每小时生产 5 件）
- 对于底部货物，我们有交付给工厂的数量（例如每小时交付 5 个）
- 现在每个有多少库存（所以如果没有足够的交付，如果我们还有一些库存，我们不需要减少产量）
- 什么时候发货会发生变化（可以发生在底部的任何商品上）
- 什么时候商品的最大生产率会发生变化（可以发生在任何不在底部的商品上）
有了这些信息，我想计算出未来给定时间每种商品的数量。我希望它尽可能高效，因为我经常需要这些计算。
我试图在 Java 中对此进行实现，但我遇到了一些问题。我没有修复它们，而是再次查看了我的算法，发现它看起来并不怎么有效，所以我想知道是否有人已经看到或解决了这类问题？
我试图解决这个问题的方法如下：
- 当生产（或交付）量发生变化时，我使用已知信息为每种商品创建最大生产（和交付）间隔。
- 我把所有的资源放在最下面一个
remaining集和一个checked集（最下面的货是立马勾选的）
- 我计算每个商品实际生产的商品数量：因此，我将每个商品都放在剩余的商品中，然后检查可以生产的商品，如果只能生产的商品都是由检查的商品制成的我计算实际生产量取决于最大速率和可用商品（取决于制成物品的生产量和库存量，如果较少）。此外，在这一步中，如果由于来源商品的产量减少（但开始时有一些库存）需要减少产量，我会添加生产间隔。完成商品后，新商品将从剩余的 Set 中移除，并添加新商品，并添加到选中的 Set 中。
- 现在我们有了每种商品的所有实际商品产量，我们可以计算它了。为此，我们遍历每种商品并获取实际产量并使用时间间隔边界将其相加。我们现在有未来想要的货量。
附加信息：如果没有第 3 点，我们将无法执行第 4 点。因为我们为一件商品计算的实际数量，可以再次消耗用于生产下一件商品，所以我们需要这个介于两者之间。
如果它有助于理解我所做的（或想做的）我添加我的代码（不工作）。 class 已经用当前正在生产的每种产品的最大生产率间隔进行了初始化。由于其他商品可能有库存，对于所有未包括在内的商品，我们将它们初始化为零和一个区间的生产。
public class FactoryGoods {
private long future;
private long now;
private Map<String, Integer> availableGoods;
private Map<String, ArrayList<ProductionInterval>> hourlyGoodIncrease;
/**
*
* @param future long current time
* @param now long last time the factory's resources got updates
* @param availableGoods Map<String,Integer> of the goods in the factory
* @param hourlyGoodIncrease Map<String,ArrayList<ProductionInterval>> of the intervals of production quantities for the goods
*/
public factoryGoods(long future, long now, Map<String,Integer> availableGoods, Map<String,ArrayList<ProductionInterval>> hourlyGoodIncrease) {
this.future = future;
this.now = now;
this.availableGoods = availableGoods;
this.hourlyGoodIncrease = hourlyGoodIncrease;
}
/**
* Calculates the resources present in a factory's storage
* @return a Map of quantities mapped on the String name of the good
*/
public Map<String,Integer> getResources() {
// Make sure all goods to have all goods inside the loop, to work on goods,
// that are produced, but also those which are only in store
HashMap<String, Boolean> goodChecked = new HashMap<String,Boolean>();
Set<String> remaining = new HashSet<String>();
for (Goods good: Goods.values()) {
String g = good.get();
if (hourlyGoodIncrease.get(g) == null) {
ArrayList<ProductionInterval> prods = new ArrayList<ProductionInterval>();
ProductionInterval start = new ProductionInterval(now, 0);
prods.add(start);
hourlyGoodIncrease.put(g, prods);
}
if (availableGoods.get(g) == null) {
availableGoods.put(g, 0);
}
if (good.isPrimary()) {
goodChecked.put(g, true);
} else {
goodChecked.put(g, false);
}
remaining.add(g);
}
// As long as goods are remaining to be checked loops over the goods, and
// recalculates hourly good increases for goods, that have all its sources
// already calculated
while (remaining.size() > 0) {
Set<String> removes = new HashSet<String>();
for (String good: remaining) {
if (goodChecked.get(good)) {
Good g = GoodFactory.get(good);
Set<String> to = new HashSet<String>();
Map<String,Float> from = new HashMap<String,Float>();
setUpFromAndToGoods(g, to, from, availableGoods);
if (areGoodsAlreadyCalculated(to, goodChecked)) {
//remaining.remove(good);
removes.add(good);
} else {
if (areGoodsReadyForCalculation(to, goodChecked)) {
// Get all resources we are working on now
Map<String,Float> fromDecrease = new HashMap<String,Float>();
for (String t: to) {
for (String f: GoodFactory.get(t).isMadeFrom().keySet()) {
from.put(f, (float) availableGoods.get(f));
}
}
// Get all interval borders
ArrayList<Long> intervalBorders = new ArrayList<Long>();
for (String wGood: from.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(wGood);
for (ProductionInterval interval: intervals) {
long intervalStart = interval.getStartTime();
if (!intervalBorders.contains(intervalStart)) {
intervalBorders.add(intervalStart);
}
}
}
Collections.sort(intervalBorders);
intervalBorders.add(future);
for (String f: from.keySet()) {
hourlyGoodIncrease.put(f, createNewProductionIntervalls(intervalBorders, hourlyGoodIncrease.get(f)));
}
// For all intervals
int iLast = intervalBorders.size() - 1;
for (int i = 0; i < iLast; i++) {
long elapsedTime = intervalBorders.get(i + 1) - intervalBorders.get(i);
for (String t: to) {
Map<String, Float> source = GoodFactory.get(t).isMadeFrom();
for (String s: source.keySet()) {
Float decrease = fromDecrease.get(s);
fromDecrease.put(s, (decrease != null ? decrease : 0) + source.get(s));
}
}
// Calculate amount after normal maximum production
Set<String> negatives = new HashSet<String>();
Map<String,Float> nextFrom = new HashMap<String,Float>();
for (String f: from.keySet()) {
float delta = from.get(f) + (hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f)) * elapsedTime / (1000 * 60 * 60);
nextFrom.put(f, delta);
if (delta < 0) {
negatives.add(f);
}
}
// Check if got under zero
if (negatives.size() == 0) {
for (String f: from.keySet()) {
float newIncrease = hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f);
hourlyGoodIncrease.get(f).get(i).setHourlyIncrease(newIncrease);
from.put(f, nextFrom.get(f));
}
} else {
// TODO: handle case when more is used than exists
}
// Else calculate point where at least one from is zero and add an interval
// before its maximum, after needs to be adjusted
}
// Break to remove all calculated goods from the remaining set and rerun the loop
removes = to;
break;
}
}
}
}
for (String remove: removes) {
remaining.remove(remove);
}
}
// Final calculation of the goods amounts that are available in the factory
for (String good: goodChecked.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(good);
intervals.add(new ProductionInterval(future, 0));
float after = availableGoods.get(good);
for (int i = 0; i < (intervals.size() - 1); i++) {
after += intervals.get(i).getHourlyIncrease() * (intervals.get(i + 1).getStartTime() - intervals.get(i).getStartTime()) / (1000 * 60 * 60);
}
availableGoods.put(good, (int) after);
}
return availableGoods;
}
private static ArrayList<ProductionInterval> createNewProductionIntervalls(ArrayList<Long> intervalBorders, ArrayList<ProductionInterval> hourlyIncreases) {
System.out.print("intervalBorders\n");
System.out.print(intervalBorders + "\n");
System.out.print("hourlyIncreases\n");
System.out.print(hourlyIncreases + "\n");
ArrayList<ProductionInterval> intervalls = new ArrayList<ProductionInterval>();
int i = 0;
long iTime = 0;
long nextTime = 0;
for (long l: intervalBorders) {
float increase = 0;
iTime = hourlyIncreases.get(i).getStartTime();
if (i + 1 < hourlyIncreases.size()) {
nextTime = hourlyIncreases.get(i + 1).getStartTime();
}
if (l == iTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (iTime < l && l < nextTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (l == nextTime) {
increase = hourlyIncreases.get(++i).getHourlyIncrease();
}
intervalls.add(new ProductionInterval(l, increase));
}
return intervalls;
}
private static void setUpFromAndToGoods(Good g, Set<String> to, Map<String,Float> from, Map<String,Integer> availableGoods) {
Set<String> unchecked = g.isUsedToCreate();
while (unchecked.size() > 0) {
String good = unchecked.iterator().next();
unchecked.remove(good);
to.add(good);
Set<String> madeFrom = GoodFactory.get(good).isMadeFrom().keySet();
for (String fromGood: madeFrom) {
if (!from.containsKey(fromGood)) {
from.put(fromGood, (float) availableGoods.get(fromGood));
Set<String> additions = GoodFactory.get(fromGood).isUsedToCreate();
for (String addition: additions) {
if (!to.contains(addition) && !unchecked.contains(addition)) {
unchecked.add(addition);
}
}
}
}
}
}
private static boolean areGoodsReadyForCalculation(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
Good toGood = GoodFactory.get(t);
for (String from: toGood.isMadeFrom().keySet()) {
if (!goodChecked.get(from)) {
return false;
}
}
}
return true;
}
private static boolean areGoodsAlreadyCalculated(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
if (!goodChecked.get(t)) {
return false;
}
}
return true;
}
}
public class ProductionInterval {
private long startTime;
private float hourlyIncrease;
public ProductionInterval(long startTime, float hourlyIncrease) {
this.setStartTime(startTime);
this.setHourlyIncrease(hourlyIncrease);
}
public float getHourlyIncrease() {
return hourlyIncrease;
}
public void setHourlyIncrease(float hourlyIncrease) {
this.hourlyIncrease = hourlyIncrease;
}
public long getStartTime() {
return startTime;
}
public void setStartTime(long startTime) {
this.startTime = startTime;
}
public String toString() {
return "<starttime=" + this.startTime + ", hourlyIncrease=" + this.hourlyIncrease + ">";
}
}
有人知道可以解决我的问题的算法，或者知道如何更改我的算法以提高效率吗？（我知道它不起作用完全没有，但是有了所有这些循环，我认为它不会有效率，我想知道在我完成工作之前是否有人看到我可以做得更好的东西。
您可以应用像 Edmonds-Karp 这样的最大流算法，只需稍作修改，您需要构建图形以提供给算法：
- 为每种商品创建一个节点
- 您需要一个“源”节点和一个“汇”节点
- 对于每个交付的货物，创建一条从源到相应节点的弧，其容量等于交付率
- 对于每个最终产品，从其各自的节点到汇点创建一条弧，其容量等于生产率
- 对于商品之间的每个依赖关系，在相应节点之间创建一条容量为 1 的弧。
- 对于每种商品，创建一条从源到相应节点的弧，其容量等于库存商品的数量（对于第一次迭代，它为零）
结果将是算法完成后从最终商品节点到汇点的流量。对于您的情况，您需要进行两项修改：
- 当计算一个节点的流量时，您将流向它的 最小值 （因为您需要所有依赖项才能创建商品），然后将其限制在该商品的未交付货物的最大生产率
- 您需要考虑库存商品的变化 - 稍后将编辑答案
虽然这个算法是离线的，这意味着它不适合时间的流量变化，但它相对简单，如果你不太受性能要求的限制，它可能有效 - 调整容量后再次 运行 算法。线上最大流量可以看this,
在 C++ 中实现我对分数模拟的想法（抱歉）。请参阅下面的大量注释代码。
（我知道面对受限资源时的优先级排序不是您想要的。公平地实现 Derivative 并尽可能多地生产并不是一件容易的事，所以我想验证一下进入兔子洞之前的这种方法。）
#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
// Identifies a type of good in some Factory.
using Good = int;
// Simulates a factory. The simulation is crude, assuming continuous,
// fractional, zero-latency production. Nevertheless it may be accurate enough
// for high production volumes over long periods of time.
class Factory {
public:
// Declares a new raw material. `delivery_rate` is the amount of this good
// delivered per hour.
Good NewRawMaterial(double stock, double delivery_rate) {
assert(stock >= 0.0);
assert(delivery_rate >= 0.0);
return NewGood(stock, delivery_rate, {});
}
// Declares a new manufactured good. `max_production_rate` is the max amount
// of this good produced per hour. Producing one of this good consumes one
// `input`.
Good NewManufacturedGood(double stock, double max_production_rate,
Good input) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
return NewGood(stock, max_production_rate, {input});
}
// Declares a new manufactured good. `max_production_rate` is the max amount
// of this good produced per hour. Producing one of this good consumes one
// `input_a` and one `input_b`.
Good NewManufacturedGood(double stock, double max_production_rate,
Good input_a, Good input_b) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
return NewGood(stock, max_production_rate, {input_a, input_b});
}
// Returns the number of hours since the start of the simulation.
double Now() const { return current_time_; }
// Advances the current time to `time` hours since the start of the
// simulation.
void AdvanceTo(double time);
// Returns the amount of `good` in stock as of the current time.
double Stock(Good good) const { return stock_[good]; }
// Sets the delivery rate of `good` to `delivery_rate` as of the current time.
void SetDeliveryRate(Good good, double delivery_rate) {
assert(delivery_rate >= 0.0);
max_production_rate_[good] = delivery_rate;
}
// Sets the max production rate of `good` to `max_production_rate` as of the
// current time.
void SetMaxProductionRate(Good good, double max_production_rate) {
assert(max_production_rate >= 0.0);
max_production_rate_[good] = max_production_rate;
}
private:
// Floating-point tolerance.
static constexpr double kEpsilon = 1e-06;
// Declares a new good. We handle raw materials as goods with no inputs.
Good NewGood(double stock, double max_production_rate,
std::vector<Good> inputs) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
Good good = stock_.size();
stock_.push_back(stock);
max_production_rate_.push_back(max_production_rate);
inputs_.push_back(std::move(inputs));
return good;
}
// Returns the right-hand derivative of stock.
std::vector<double> Derivative() const;
// Returns the next time at which a good is newly out of stock, or positive
// infinity if there is no such time.
double NextStockOutTime(const std::vector<double> &derivative) const;
// The current time, in hours since the start of the simulation.
double current_time_ = 0.0;
// `stock_[good]` is the amount of `good` in stock at the current time.
std::vector<double> stock_;
// `max_production_rate_[good]` is the max production rate of `good` at the
// current time.
std::vector<double> max_production_rate_;
// `inputs_[good]` is the list of goods required to produce `good` (empty for
// raw materials).
std::vector<std::vector<Good>> inputs_;
// Derivative of `stock_`.
std::vector<double> stock_rate_;
};
void Factory::AdvanceTo(double time) {
assert(time >= current_time_);
bool caught_up = false;
while (!caught_up) {
auto derivative = Derivative();
double next_time = NextStockOutTime(derivative);
if (time <= next_time) {
next_time = time;
caught_up = true;
}
for (Good good = 0; good < stock_.size(); good++) {
stock_[good] += (next_time - current_time_) * derivative[good];
}
current_time_ = next_time;
}
}
std::vector<double> Factory::Derivative() const {
// TODO: this code prioritizes limited supply by the order in which production
// is declared. You probably want to use linear programming or something.
std::vector<double> derivative = max_production_rate_;
for (Good good = 0; good < stock_.size(); good++) {
for (Good input : inputs_[good]) {
if (stock_[input] <= kEpsilon) {
derivative[good] = std::min(derivative[good], derivative[input]);
}
}
for (Good input : inputs_[good]) {
derivative[input] -= derivative[good];
}
}
return derivative;
}
double Factory::NextStockOutTime(const std::vector<double> &derivative) const {
double duration = std::numeric_limits<double>::infinity();
for (Good good = 0; good < stock_.size(); good++) {
if (stock_[good] > kEpsilon && derivative[good] < -kEpsilon) {
duration = std::min(duration, stock_[good] / -derivative[good]);
}
}
return current_time_ + duration;
}
int main() {
Factory factory;
Good r1 = factory.NewRawMaterial(60.0, 3.0);
Good r2 = factory.NewRawMaterial(20.0, 1.0);
Good r3 = factory.NewManufacturedGood(0.0, 2.0, r1);
Good r4 = factory.NewManufacturedGood(0.0, 1.0, r1, r2);
auto print_stocks = [&]() {
std::cout << "t : " << factory.Now() << "\n";
std::cout << "r1: " << factory.Stock(r1) << "\n";
std::cout << "r2: " << factory.Stock(r2) << "\n";
std::cout << "r3: " << factory.Stock(r3) << "\n";
std::cout << "r4: " << factory.Stock(r4) << "\n";
std::cout << "\n";
};
print_stocks();
// Everything running smoothly
factory.AdvanceTo(24.0);
print_stocks();
// Uh oh, r1 supply cut off. Stock out at 44 hours.
factory.SetDeliveryRate(r1, 0.0);
factory.AdvanceTo(48.0);
print_stocks();
// r1 supply at 50%. r3 production prioritized.
factory.SetDeliveryRate(r1, 1.5);
factory.AdvanceTo(72.0);
print_stocks();
// r1 oversupplied.
factory.SetDeliveryRate(r1, 4.0);
factory.AdvanceTo(96.0);
print_stocks();
}
输出：
t : 0
r1: 60
r2: 20
r3: 0
r4: 0
t : 24
r1: 60
r2: 20
r3: 48
r4: 24
t : 48
r1: 0
r2: 24
r3: 88
r4: 44
t : 72
r1: 0
r2: 48
r3: 124
r4: 44
t : 96
r1: 24
r2: 48
r3: 172
r4: 68
这篇文章很长post，但真正相关的只有前半部分。 后半部分仅描述了我试图解决的问题，但在我看来效率太低（它可能有助于了解我想要什么）。相关部分以粗体问题后的行结束。
我正在尝试在一个假想的工厂中模拟多次生产，以计算最终每种已知类型的商品数量。有几种不同的商品类型，它们都有特定的最大生产能力，只有在有足够的原料可用时才能达到。生产线的外观示例如下：
底部的货物都有一个已知的送达工厂的速度，所以对于那些，没有什么可计算的，虽然这个速度会随着时间而变化（另外，最大生产能力也可以随时更改，例如，可以通过添加工人或更多机器来增加容量）。
如图所示，其他商品看三点：
- 一些线路产生了一个好的其他线路。
- 一些线产生了另外两条线。
- 一些行有一个好的用于创造不止一个新的商品 （例如，参见插图中间的“R8”）。
我有以下信息：
- 每种商品的最大生产率（例如每小时生产 5 件）
- 对于底部货物，我们有交付给工厂的数量（例如每小时交付 5 个）
- 现在每个有多少库存（所以如果没有足够的交付，如果我们还有一些库存，我们不需要减少产量）
- 什么时候发货会发生变化（可以发生在底部的任何商品上）
- 什么时候商品的最大生产率会发生变化（可以发生在任何不在底部的商品上）
有了这些信息，我想计算出未来给定时间每种商品的数量。我希望它尽可能高效，因为我经常需要这些计算。
我试图在 Java 中对此进行实现，但我遇到了一些问题。我没有修复它们，而是再次查看了我的算法，发现它看起来并不怎么有效，所以我想知道是否有人已经看到或解决了这类问题？
我试图解决这个问题的方法如下：
- 当生产（或交付）量发生变化时，我使用已知信息为每种商品创建最大生产（和交付）间隔。
- 我把所有的资源放在最下面一个
remaining集和一个checked集（最下面的货是立马勾选的） - 我计算每个商品实际生产的商品数量：因此，我将每个商品都放在剩余的商品中，然后检查可以生产的商品，如果只能生产的商品都是由检查的商品制成的我计算实际生产量取决于最大速率和可用商品（取决于制成物品的生产量和库存量，如果较少）。此外，在这一步中，如果由于来源商品的产量减少（但开始时有一些库存）需要减少产量，我会添加生产间隔。完成商品后，新商品将从剩余的 Set 中移除，并添加新商品，并添加到选中的 Set 中。
- 现在我们有了每种商品的所有实际商品产量，我们可以计算它了。为此，我们遍历每种商品并获取实际产量并使用时间间隔边界将其相加。我们现在有未来想要的货量。
附加信息：如果没有第 3 点，我们将无法执行第 4 点。因为我们为一件商品计算的实际数量，可以再次消耗用于生产下一件商品，所以我们需要这个介于两者之间。
如果它有助于理解我所做的（或想做的）我添加我的代码（不工作）。 class 已经用当前正在生产的每种产品的最大生产率间隔进行了初始化。由于其他商品可能有库存，对于所有未包括在内的商品，我们将它们初始化为零和一个区间的生产。
public class FactoryGoods {
private long future;
private long now;
private Map<String, Integer> availableGoods;
private Map<String, ArrayList<ProductionInterval>> hourlyGoodIncrease;
/**
*
* @param future long current time
* @param now long last time the factory's resources got updates
* @param availableGoods Map<String,Integer> of the goods in the factory
* @param hourlyGoodIncrease Map<String,ArrayList<ProductionInterval>> of the intervals of production quantities for the goods
*/
public factoryGoods(long future, long now, Map<String,Integer> availableGoods, Map<String,ArrayList<ProductionInterval>> hourlyGoodIncrease) {
this.future = future;
this.now = now;
this.availableGoods = availableGoods;
this.hourlyGoodIncrease = hourlyGoodIncrease;
}
/**
* Calculates the resources present in a factory's storage
* @return a Map of quantities mapped on the String name of the good
*/
public Map<String,Integer> getResources() {
// Make sure all goods to have all goods inside the loop, to work on goods,
// that are produced, but also those which are only in store
HashMap<String, Boolean> goodChecked = new HashMap<String,Boolean>();
Set<String> remaining = new HashSet<String>();
for (Goods good: Goods.values()) {
String g = good.get();
if (hourlyGoodIncrease.get(g) == null) {
ArrayList<ProductionInterval> prods = new ArrayList<ProductionInterval>();
ProductionInterval start = new ProductionInterval(now, 0);
prods.add(start);
hourlyGoodIncrease.put(g, prods);
}
if (availableGoods.get(g) == null) {
availableGoods.put(g, 0);
}
if (good.isPrimary()) {
goodChecked.put(g, true);
} else {
goodChecked.put(g, false);
}
remaining.add(g);
}
// As long as goods are remaining to be checked loops over the goods, and
// recalculates hourly good increases for goods, that have all its sources
// already calculated
while (remaining.size() > 0) {
Set<String> removes = new HashSet<String>();
for (String good: remaining) {
if (goodChecked.get(good)) {
Good g = GoodFactory.get(good);
Set<String> to = new HashSet<String>();
Map<String,Float> from = new HashMap<String,Float>();
setUpFromAndToGoods(g, to, from, availableGoods);
if (areGoodsAlreadyCalculated(to, goodChecked)) {
//remaining.remove(good);
removes.add(good);
} else {
if (areGoodsReadyForCalculation(to, goodChecked)) {
// Get all resources we are working on now
Map<String,Float> fromDecrease = new HashMap<String,Float>();
for (String t: to) {
for (String f: GoodFactory.get(t).isMadeFrom().keySet()) {
from.put(f, (float) availableGoods.get(f));
}
}
// Get all interval borders
ArrayList<Long> intervalBorders = new ArrayList<Long>();
for (String wGood: from.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(wGood);
for (ProductionInterval interval: intervals) {
long intervalStart = interval.getStartTime();
if (!intervalBorders.contains(intervalStart)) {
intervalBorders.add(intervalStart);
}
}
}
Collections.sort(intervalBorders);
intervalBorders.add(future);
for (String f: from.keySet()) {
hourlyGoodIncrease.put(f, createNewProductionIntervalls(intervalBorders, hourlyGoodIncrease.get(f)));
}
// For all intervals
int iLast = intervalBorders.size() - 1;
for (int i = 0; i < iLast; i++) {
long elapsedTime = intervalBorders.get(i + 1) - intervalBorders.get(i);
for (String t: to) {
Map<String, Float> source = GoodFactory.get(t).isMadeFrom();
for (String s: source.keySet()) {
Float decrease = fromDecrease.get(s);
fromDecrease.put(s, (decrease != null ? decrease : 0) + source.get(s));
}
}
// Calculate amount after normal maximum production
Set<String> negatives = new HashSet<String>();
Map<String,Float> nextFrom = new HashMap<String,Float>();
for (String f: from.keySet()) {
float delta = from.get(f) + (hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f)) * elapsedTime / (1000 * 60 * 60);
nextFrom.put(f, delta);
if (delta < 0) {
negatives.add(f);
}
}
// Check if got under zero
if (negatives.size() == 0) {
for (String f: from.keySet()) {
float newIncrease = hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f);
hourlyGoodIncrease.get(f).get(i).setHourlyIncrease(newIncrease);
from.put(f, nextFrom.get(f));
}
} else {
// TODO: handle case when more is used than exists
}
// Else calculate point where at least one from is zero and add an interval
// before its maximum, after needs to be adjusted
}
// Break to remove all calculated goods from the remaining set and rerun the loop
removes = to;
break;
}
}
}
}
for (String remove: removes) {
remaining.remove(remove);
}
}
// Final calculation of the goods amounts that are available in the factory
for (String good: goodChecked.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(good);
intervals.add(new ProductionInterval(future, 0));
float after = availableGoods.get(good);
for (int i = 0; i < (intervals.size() - 1); i++) {
after += intervals.get(i).getHourlyIncrease() * (intervals.get(i + 1).getStartTime() - intervals.get(i).getStartTime()) / (1000 * 60 * 60);
}
availableGoods.put(good, (int) after);
}
return availableGoods;
}
private static ArrayList<ProductionInterval> createNewProductionIntervalls(ArrayList<Long> intervalBorders, ArrayList<ProductionInterval> hourlyIncreases) {
System.out.print("intervalBorders\n");
System.out.print(intervalBorders + "\n");
System.out.print("hourlyIncreases\n");
System.out.print(hourlyIncreases + "\n");
ArrayList<ProductionInterval> intervalls = new ArrayList<ProductionInterval>();
int i = 0;
long iTime = 0;
long nextTime = 0;
for (long l: intervalBorders) {
float increase = 0;
iTime = hourlyIncreases.get(i).getStartTime();
if (i + 1 < hourlyIncreases.size()) {
nextTime = hourlyIncreases.get(i + 1).getStartTime();
}
if (l == iTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (iTime < l && l < nextTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (l == nextTime) {
increase = hourlyIncreases.get(++i).getHourlyIncrease();
}
intervalls.add(new ProductionInterval(l, increase));
}
return intervalls;
}
private static void setUpFromAndToGoods(Good g, Set<String> to, Map<String,Float> from, Map<String,Integer> availableGoods) {
Set<String> unchecked = g.isUsedToCreate();
while (unchecked.size() > 0) {
String good = unchecked.iterator().next();
unchecked.remove(good);
to.add(good);
Set<String> madeFrom = GoodFactory.get(good).isMadeFrom().keySet();
for (String fromGood: madeFrom) {
if (!from.containsKey(fromGood)) {
from.put(fromGood, (float) availableGoods.get(fromGood));
Set<String> additions = GoodFactory.get(fromGood).isUsedToCreate();
for (String addition: additions) {
if (!to.contains(addition) && !unchecked.contains(addition)) {
unchecked.add(addition);
}
}
}
}
}
}
private static boolean areGoodsReadyForCalculation(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
Good toGood = GoodFactory.get(t);
for (String from: toGood.isMadeFrom().keySet()) {
if (!goodChecked.get(from)) {
return false;
}
}
}
return true;
}
private static boolean areGoodsAlreadyCalculated(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
if (!goodChecked.get(t)) {
return false;
}
}
return true;
}
}
public class ProductionInterval {
private long startTime;
private float hourlyIncrease;
public ProductionInterval(long startTime, float hourlyIncrease) {
this.setStartTime(startTime);
this.setHourlyIncrease(hourlyIncrease);
}
public float getHourlyIncrease() {
return hourlyIncrease;
}
public void setHourlyIncrease(float hourlyIncrease) {
this.hourlyIncrease = hourlyIncrease;
}
public long getStartTime() {
return startTime;
}
public void setStartTime(long startTime) {
this.startTime = startTime;
}
public String toString() {
return "<starttime=" + this.startTime + ", hourlyIncrease=" + this.hourlyIncrease + ">";
}
}
有人知道可以解决我的问题的算法，或者知道如何更改我的算法以提高效率吗？（我知道它不起作用完全没有，但是有了所有这些循环，我认为它不会有效率，我想知道在我完成工作之前是否有人看到我可以做得更好的东西。
您可以应用像 Edmonds-Karp 这样的最大流算法，只需稍作修改，您需要构建图形以提供给算法：
- 为每种商品创建一个节点
- 您需要一个“源”节点和一个“汇”节点
- 对于每个交付的货物，创建一条从源到相应节点的弧，其容量等于交付率
- 对于每个最终产品，从其各自的节点到汇点创建一条弧，其容量等于生产率
- 对于商品之间的每个依赖关系，在相应节点之间创建一条容量为 1 的弧。
- 对于每种商品，创建一条从源到相应节点的弧，其容量等于库存商品的数量（对于第一次迭代，它为零）
结果将是算法完成后从最终商品节点到汇点的流量。对于您的情况，您需要进行两项修改：
- 当计算一个节点的流量时，您将流向它的 最小值 （因为您需要所有依赖项才能创建商品），然后将其限制在该商品的未交付货物的最大生产率
- 您需要考虑库存商品的变化 - 稍后将编辑答案
虽然这个算法是离线的，这意味着它不适合时间的流量变化，但它相对简单，如果你不太受性能要求的限制，它可能有效 - 调整容量后再次 运行 算法。线上最大流量可以看this,
在 C++ 中实现我对分数模拟的想法（抱歉）。请参阅下面的大量注释代码。
（我知道面对受限资源时的优先级排序不是您想要的。公平地实现 Derivative 并尽可能多地生产并不是一件容易的事，所以我想验证一下进入兔子洞之前的这种方法。）
#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
// Identifies a type of good in some Factory.
using Good = int;
// Simulates a factory. The simulation is crude, assuming continuous,
// fractional, zero-latency production. Nevertheless it may be accurate enough
// for high production volumes over long periods of time.
class Factory {
public:
// Declares a new raw material. `delivery_rate` is the amount of this good
// delivered per hour.
Good NewRawMaterial(double stock, double delivery_rate) {
assert(stock >= 0.0);
assert(delivery_rate >= 0.0);
return NewGood(stock, delivery_rate, {});
}
// Declares a new manufactured good. `max_production_rate` is the max amount
// of this good produced per hour. Producing one of this good consumes one
// `input`.
Good NewManufacturedGood(double stock, double max_production_rate,
Good input) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
return NewGood(stock, max_production_rate, {input});
}
// Declares a new manufactured good. `max_production_rate` is the max amount
// of this good produced per hour. Producing one of this good consumes one
// `input_a` and one `input_b`.
Good NewManufacturedGood(double stock, double max_production_rate,
Good input_a, Good input_b) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
return NewGood(stock, max_production_rate, {input_a, input_b});
}
// Returns the number of hours since the start of the simulation.
double Now() const { return current_time_; }
// Advances the current time to `time` hours since the start of the
// simulation.
void AdvanceTo(double time);
// Returns the amount of `good` in stock as of the current time.
double Stock(Good good) const { return stock_[good]; }
// Sets the delivery rate of `good` to `delivery_rate` as of the current time.
void SetDeliveryRate(Good good, double delivery_rate) {
assert(delivery_rate >= 0.0);
max_production_rate_[good] = delivery_rate;
}
// Sets the max production rate of `good` to `max_production_rate` as of the
// current time.
void SetMaxProductionRate(Good good, double max_production_rate) {
assert(max_production_rate >= 0.0);
max_production_rate_[good] = max_production_rate;
}
private:
// Floating-point tolerance.
static constexpr double kEpsilon = 1e-06;
// Declares a new good. We handle raw materials as goods with no inputs.
Good NewGood(double stock, double max_production_rate,
std::vector<Good> inputs) {
assert(stock >= 0.0);
assert(max_production_rate >= 0.0);
Good good = stock_.size();
stock_.push_back(stock);
max_production_rate_.push_back(max_production_rate);
inputs_.push_back(std::move(inputs));
return good;
}
// Returns the right-hand derivative of stock.
std::vector<double> Derivative() const;
// Returns the next time at which a good is newly out of stock, or positive
// infinity if there is no such time.
double NextStockOutTime(const std::vector<double> &derivative) const;
// The current time, in hours since the start of the simulation.
double current_time_ = 0.0;
// `stock_[good]` is the amount of `good` in stock at the current time.
std::vector<double> stock_;
// `max_production_rate_[good]` is the max production rate of `good` at the
// current time.
std::vector<double> max_production_rate_;
// `inputs_[good]` is the list of goods required to produce `good` (empty for
// raw materials).
std::vector<std::vector<Good>> inputs_;
// Derivative of `stock_`.
std::vector<double> stock_rate_;
};
void Factory::AdvanceTo(double time) {
assert(time >= current_time_);
bool caught_up = false;
while (!caught_up) {
auto derivative = Derivative();
double next_time = NextStockOutTime(derivative);
if (time <= next_time) {
next_time = time;
caught_up = true;
}
for (Good good = 0; good < stock_.size(); good++) {
stock_[good] += (next_time - current_time_) * derivative[good];
}
current_time_ = next_time;
}
}
std::vector<double> Factory::Derivative() const {
// TODO: this code prioritizes limited supply by the order in which production
// is declared. You probably want to use linear programming or something.
std::vector<double> derivative = max_production_rate_;
for (Good good = 0; good < stock_.size(); good++) {
for (Good input : inputs_[good]) {
if (stock_[input] <= kEpsilon) {
derivative[good] = std::min(derivative[good], derivative[input]);
}
}
for (Good input : inputs_[good]) {
derivative[input] -= derivative[good];
}
}
return derivative;
}
double Factory::NextStockOutTime(const std::vector<double> &derivative) const {
double duration = std::numeric_limits<double>::infinity();
for (Good good = 0; good < stock_.size(); good++) {
if (stock_[good] > kEpsilon && derivative[good] < -kEpsilon) {
duration = std::min(duration, stock_[good] / -derivative[good]);
}
}
return current_time_ + duration;
}
int main() {
Factory factory;
Good r1 = factory.NewRawMaterial(60.0, 3.0);
Good r2 = factory.NewRawMaterial(20.0, 1.0);
Good r3 = factory.NewManufacturedGood(0.0, 2.0, r1);
Good r4 = factory.NewManufacturedGood(0.0, 1.0, r1, r2);
auto print_stocks = [&]() {
std::cout << "t : " << factory.Now() << "\n";
std::cout << "r1: " << factory.Stock(r1) << "\n";
std::cout << "r2: " << factory.Stock(r2) << "\n";
std::cout << "r3: " << factory.Stock(r3) << "\n";
std::cout << "r4: " << factory.Stock(r4) << "\n";
std::cout << "\n";
};
print_stocks();
// Everything running smoothly
factory.AdvanceTo(24.0);
print_stocks();
// Uh oh, r1 supply cut off. Stock out at 44 hours.
factory.SetDeliveryRate(r1, 0.0);
factory.AdvanceTo(48.0);
print_stocks();
// r1 supply at 50%. r3 production prioritized.
factory.SetDeliveryRate(r1, 1.5);
factory.AdvanceTo(72.0);
print_stocks();
// r1 oversupplied.
factory.SetDeliveryRate(r1, 4.0);
factory.AdvanceTo(96.0);
print_stocks();
}
输出：
t : 0
r1: 60
r2: 20
r3: 0
r4: 0
t : 24
r1: 60
r2: 20
r3: 48
r4: 24
t : 48
r1: 0
r2: 24
r3: 88
r4: 44
t : 72
r1: 0
r2: 48
r3: 124
r4: 44
t : 96
r1: 24
r2: 48
r3: 172
r4: 68