algorithm - 帮助确定特定问题是否是经典计算机科学问题

Question

我有一个很久以前在 VBA 中解决的制造过程问题，虽然随着越来越多的数据进入文件，它的运行速度越来越慢，但它现在已经搁置了一段时间。我认为现在是时候用 VBA 之外的另一种语言重写一个更优雅的解决方案了，但我很好奇是否有人知道这是一个经典的计算机科学问题，并且是否已给它一个学术名称以便我可以研究更快的算法.

我将在下面以点的形式概述它:

假设存在不同类型的小部件....调用它们...

Widget-Type A

Widget-Type B

Widget-Type A has various serial numbers

Widget-Type B has various serial numbers

此外，

You can tell what Type a Widget is (A or B) based on the serial number alone. Serial Numbers are appended a build-date (i.e. 2010-08-10)... if the serial exists but the date is missing, the Widget exists but isn't finished being built.

Widget-Type B can contain (one or more of) the parts from a Widget-Type A; therefore, Widget-Type B's serial number can have a list of sub-serial numbers from that of A.

Similarily, Widget-Type A can contain (one or more of) the parts from a Widget-Type B; therefore, Widget-Type A's serial number can have a list of sub-serial numbers from that of B.

最后，

There exists a Widget-Type C

Widget-Type C can only exist (be built) if given a Widget-Type A, that Widget-Type A has a build-date appended to the serial, AND all it's corresponding sub-serial numbers (from Widget-Type Bs) have build-dates appended to the serial.

Again, you can have the other case that Widget-Type C can only exist (be built) if given a Widget-Type B, that Widget-Type B has a build-date appended to the serial, AND all it's corresponding sub-serial numbers (from Widget-Type As) have build-dates appended to the serial.

如您所见，如果 Widget A 和 B 有许多子序列，则需要进行大量交叉检查和引用以确保 Widget C 可生产。

我知道这是一个冗长的描述，但如果这是任何常见计算机科学问题的变体，您有什么想法吗？

Answer 1

我不认为这是解决方案，而是关于如何解决此问题的想法。假设问题是有序依赖是否公平？要生成Widget C，需要生成Widget A和Widget B。而要生产的Widget A，可能对Widget B有依赖(也有可能也有循环，当然序号的值不同)。

鉴于上述情况，您可以将小部件表示为无环有向图，不是吗？两个节点(小部件)之间的有向边定义了依赖关系。例如，Wdget C <- {Widget A , Widget B}。然后你可以使用 topological traversal获得正确的生产顺序。

同样，我不确定这是否是您正在寻找的答案，但根据我从问题定义中了解到的情况，我认为这是一种可能性。