具有一定依赖性/约束的算法遍历图

Question

因此，我正在建立一个操作管道，该管道允许用户在数据范围内应用某些数据操作。 操作使它们可能具有“一输入 - ＆gt;两个输出”或“一输入 - ＆gt; One-On-On-On-On-On-On-On-On-On-On-On-On-Onputs”或“两输入 - ＆gt; One-On-On-On-On-On-On-On-On-On-On-On-On-On-On-On-On-Entput”。

我需要从标记为[S1，S2，S3，S4]的起点遍历图形，并到达终点 重要的是要注意的是，要执行操作2，我们需要使操作1和操作5已经执行。类似地，与执行操作7一样，操作3和6需要已执行。

请注意，这比有向的无环图更简单，因为我们具有清晰的起点和终点，并且流量是单向的[图像中的左 - ＆gt;右]，

已知哪些操作是标记为S1，S2，S3的起点，S4。我需要执行所有操作并到达终端点。我只需要伪代码。

Answer 1

这看起来是某种任务调度问题，因为问题缺少许多重要细节，因此无法确切说出什么样或提供任何具体建议。

1. 每个任务需要多长时间。每个任务都需要同一时间吗
   在每个处理器上。 （如果任务不花时间，那么没有等待
   重新生气，问题变得微不足道）

2. 有多少个处理器可用。 （可以以合理的方式完成任务，或一个一个或仅相似的少数数字。）

3. 您要优化什么？总时间完成所有任务。最小化处理器数量。其他。

4. 您想看到的输出是什么。

有关于任务调度问题的大量文献。一个合理的起点是 https://en.wikipedia.org/wikipedia.org/wiki/wiki/scheduling_（计算）

由于您几乎没有关于问题的信息，因此您可以最好地找到可行的执行订单，假设没有副任务执行。

1. 添加一个启动节点，并带有链接到每个S节点。

2. 对树进行广度搜索，并在访问时记录节点。

Answer 2

这是您可以解决此问题的一种方式，我在下面发布了一个JavaScript snuppet，它打印出操作顺序。第一部分是表示图形，例如：

[
  [[inputs], [outputs]]  // where the index is the operation #
]

下一步将确定操作顺序以及您希望系统执行这些操作的方式。我根据图提出了以下序列：

0, 1, 5, 2, 3, 4, 6, 7, 8, 9, 10

例如，这是有意义的，因为步骤＃2要等到步骤＃5完成以下内容等，否则才能完成。由此，我们可以为我们的算法提出几个规则：

1. 按升序横穿图形，
2. 可以执行并标记为完成，如果：
3. 所有输入也标记为完整的
4. 输入，输入为null null 则指示序列的第一个操作
5. 如果输入未完成回溯操作，
6. ，直到我们击中null一旦完成所有输出操作，直到我们击中null

此方法的一个问题是上图是脱节的，因此我们确实需要运行每个s1，s2，s3，s4

// The index numbers are just for illustration
const operationsGraph = {
  0: [null, [1]],
  1: [[0], [2]],
  2: [[1, 5], [3]],
  3: [[2], [4, 7]],
  4: [[3], null],
  5: [null, [2]],
  6: [null, [7]],
  7: [[3, 6], [8]],
  8: [[7], null],
  9: [null, [10]],
  10: [[9], null],
};

// Convert the graph to an array
const operation = Object.values(operationsGraph);

// Create an array to keep track of the completed operations
const completed = Array(operation.length).fill(false);

/**
 * The algorithm works as follows:
 *
 *  1. move along path until (2 inputs needed)
 *  2. backtrack until base case
 *  3. continue in lowest completed order
 *
 *   [complete] <--- [current] ----> [complete]
 */

function traverse(pointer) {
  // if this step has been completed return
  if (completed[pointer]) return true;
  // extract the prev and next operations
  const prev = operation[pointer][0];
  const next = operation[pointer][1];
  // backtrack each previous operation
  prev?.forEach((op) => traverse(op));
  // if the previous step is complete and this operation
  // has been completed then mark as completed and print
  if (isComplete(prev) && completed[pointer] === false) {
    // update the completed flag
    completed[pointer] = true;
    // run the operation here
    console.log('running: ', pointer);
  }
  // iterate the next steps in the sequence
  next?.forEach((op) => traverse(op));
}

// helper function to check if a step is complete
function isComplete(step) {
  if (step === null) return true;
  return step.every((i) => completed[i]);
}

// run each of the sequences
function main() {
  const s1 = traverse(0);
  const s2 = traverse(5);
  const s3 = traverse(6);
  const s4 = traverse(9);
}

main()