CUDD 上的递归方法
Recursive methods on CUDD
这是对@DCTLib 在下面 post 中提出的建议的跟进。
我一直在追求建议的 (b) 部分，并将在单独的 post.
中分享一些伪代码
与此同时，在他的 (b) 部分建议中，@DCTLib posted a link to https://github.com/VerifiableRobotics/slugs/blob/master/src/BFAbstractionLibrary/BFCudd.cpp。我一直在努力阅读这个程序。经典的 Somenzi 论文 Binary Decision Diagrams 中有一个递归函数，它描述了一种计算令人满意的分配数量的算法（下图 7）。我一直在尝试比较这两者，slugs 和图 7。但很难看出任何相似之处。但是 C 对我来说几乎是难以理解的。你知道 slugs BFCudd 是否基于 Somenze 图 7，@DCTLib？
谢谢，
桂
这不是完全相同的算法。
有两个主要区别：
首先，“SatHowMany”函数不考虑变量的立方体来进行计数。相反，该函数考虑了所有变量。 “recurse_getNofSatisfyingAssignments”支持多维数据集这一事实在函数中体现出来，如果在 BDD 中找到一个未出现在多维数据集中的变量，则该函数可能会返回 NaN（而非数字）。其余的差异似乎源于这种支持。
其次，SatHowManyreturns一个节点对alln个变量的满意赋值数。例如，这导致在第 -4 行中除以 2。 "recurse_getNofSatisfyingAssignments" 仅returns 剩余变量的赋值数
两种算法都缓存信息 - 在“SatHowMany”中，它被称为 table，在“recurse_getNofSatisfyingAssignments”中它被称为缓冲区。请注意，在“recurse_getNofSatisfyingAssignments”的第 24 行中，抛出了一个常量字符串。这意味着要么该功能不起作用，要么永远无法到达代码。很有可能是后者。
函数“SatHowMany”似乎假定它获得了一个 BDD 节点——它不能是一个指向补充 BDD 节点的指针。函数“recurse_getNofSatisfyingAssignments”可以正确处理补充节点，因为 DdNode* 可以存储指向补充节点的指针。
由于支持多维数据集，“recurse_getNofSatisfyingAssignments”支持灵活的变量排序（因此查找“cuddI”表示变量在当前 BDD 变量排序中的位置）。对于函数 SatHowMany，变量排序没有影响。
这是对@DCTLib 在下面 post 中提出的建议的跟进。
我一直在追求建议的 (b) 部分，并将在单独的 post.
中分享一些伪代码与此同时，在他的 (b) 部分建议中，@DCTLib posted a link to https://github.com/VerifiableRobotics/slugs/blob/master/src/BFAbstractionLibrary/BFCudd.cpp。我一直在努力阅读这个程序。经典的 Somenzi 论文 Binary Decision Diagrams 中有一个递归函数，它描述了一种计算令人满意的分配数量的算法（下图 7）。我一直在尝试比较这两者，slugs 和图 7。但很难看出任何相似之处。但是 C 对我来说几乎是难以理解的。你知道 slugs BFCudd 是否基于 Somenze 图 7，@DCTLib？
谢谢， 桂
这不是完全相同的算法。
有两个主要区别：
首先，“SatHowMany”函数不考虑变量的立方体来进行计数。相反，该函数考虑了所有变量。 “recurse_getNofSatisfyingAssignments”支持多维数据集这一事实在函数中体现出来，如果在 BDD 中找到一个未出现在多维数据集中的变量，则该函数可能会返回 NaN（而非数字）。其余的差异似乎源于这种支持。
其次，SatHowManyreturns一个节点对alln个变量的满意赋值数。例如，这导致在第 -4 行中除以 2。 "recurse_getNofSatisfyingAssignments" 仅returns 剩余变量的赋值数
两种算法都缓存信息 - 在“SatHowMany”中，它被称为 table，在“recurse_getNofSatisfyingAssignments”中它被称为缓冲区。请注意，在“recurse_getNofSatisfyingAssignments”的第 24 行中，抛出了一个常量字符串。这意味着要么该功能不起作用，要么永远无法到达代码。很有可能是后者。
函数“SatHowMany”似乎假定它获得了一个 BDD 节点——它不能是一个指向补充 BDD 节点的指针。函数“recurse_getNofSatisfyingAssignments”可以正确处理补充节点，因为 DdNode* 可以存储指向补充节点的指针。
由于支持多维数据集，“recurse_getNofSatisfyingAssignments”支持灵活的变量排序（因此查找“cuddI”表示变量在当前 BDD 变量排序中的位置）。对于函数 SatHowMany，变量排序没有影响。