具有多个入口点和出口点的广度优先图搜索

Question

我试图为有向图制作一个相邻的列表，而图有多个入口和出口点。在图中，节点将是AND、OR、NO、XOR等，入口和出口点将是一个比特（0或1）。

我有以下节点：

• 条目A:1
• 条目B:1
• 条目C:0
• 出口D:
• 出口E:
• 节点1：或
• 节点2：和
• 节点3：和
• 节点4：不是
• 节点5：和
• 节点6：或
• 节点7：不是
• 节点8：不是
• 节点9：和
• 节点10:和
• 节点11：或

以及它们之间的以下联系：

• 条目A:Node1、Node2
• 条目B:Node1、Node2
• 条目C：节点3、节点7、节点10
• Node1:Node3，Node5
• 节点2:Node4，Node6
• 节点3:节点6
• Node4:Node5
• 节点5：节点8，节点9
• 节点6：退出D
• 节点7:节点9
• 节点8：节点10
• 节点9：节点11
• 节点10:Node11:
• 节点11：出口E

图片：

所以现在我需要通过遵循有向图的路径来计算D和E出口的字节。

我在这里找到了呼吸优先图搜索的一个链接，其中包含单个入口点和出口点：
用于查找两个任意顶点之间所有连接的图形算法。

我如何在链接中调整这个呼吸优先图搜索，这样我就可以有多个入口点和出口点，同时删除/更改递归部分（因为在使用上面链接中的代码时，我得到了stackoverflowerrrors，即使我只有一个入口点和出口点）。

Answer 1

首先要注意的是，依赖性只沿着每个链接单向流动，而您所称的“节点”则完全不同。通用图搜索不适合此问题。

如果观察到节点列表和节点之间的链接实际上并没有唯一指定所绘制的图形，则可以轻松确定原因。我可以翻转所有的门，将它们的输出连接到它们的左输入，将左输入连接到右输入，将右输入连接到输出，或者反转所有非门的方向，您拥有的节点和链接列表仍然是正确的。

如果我开始做这个模型，我会做一些完全不同的事情：

interface Component {
    boolean value();
}

class And implements Component {
    Component[] inputs;
    public And(Component ... inputs){ this.inputs = inputs; }
    boolean value(){
        for(Component c:inputs) if(!c.value()) return false;
        return true;
    }
}
class Or implements Component {
    Component[] inputs;
    public Or(Component ... inputs){ this.inputs = inputs; }
    boolean value(){
        for(Component c:inputs) if(c.value()) return true;
        return false;
    }
}
class Not implements Component {
    Component input;
    public Not(Component input){ this.input = input; }
    boolean value(){ return !input.value(); }
}
class Input implements Component {
    boolean value;
    public Input(boolean value){ set(value); }
    void set(boolean newValue){ this.value = value; }
    boolean value(){ return value; }
}

现在我们有了基本的逻辑门，我们可以使用它们构建更完整的模型：

public static void main(String ... args){
    Input a = new Input(true), b = new Input(true), c = new Input(false);
    Component n1 = new Or(a, b), n2 = new And(a, b), n3 = new And(c, n2),
              n4 = new Not(n2), n5 = new And(n1, n4), n6 = new Or(n2, n3),
              n7 = new Not(c), n8 = new Not(n5), n9 = new And(n5, n7),
              n10 = new And(c, n8), n11 = new Or(n9, n10);
    Component d = n11, e = n6;
}

结果是d.value（）和e.value（）。如果我们需要将值表示为方程的字符串，我们可以覆盖每个门的toString方法：

class And implements Component {
    //...
    public String toString(){
        StringBuilder b = new StringBuilder("(");
        for(Component c:inputs) b.append(c).append("&&");
        return b.replace(b.length()-2,b.length,")").toString();
    }
}
class Or implements Component {
    //...
    public String toString(){
        StringBuilder b = new StringBuilder("(");
        for(Component c:inputs) b.append(c).append("||");
        return b.replace(b.length()-2,b.length,")").toString();
    }
}
class Not implements Component {
    //...
    public String toString(){
        return String.format("!%1$s",input);
    }
}

现在，任何Component.toString（）都将根据其输入返回其值的逻辑表达式，这些输入本身就是根据其输入的表达式，以此类推，直到原始的Inputs。

Answer 2

你描述的问题本身不是一个图形问题。实际上，您需要的是一个布尔表达式求值器。如果您将表达式表示为二叉树，则计算很容易。

在您的图片中，D是其中一棵树的根节点。这种树的每个内部节点都有2个子节点，表达式在节点本身中。要计算，您需要对树进行后序遍历。叶子要么是A，B，C。为了评估E，只需构建一个不同的树。

如果你需要帮助建树，请告诉我（如果需要，我会尝试添加一些图片）。

在构建了表达式树之后，只需尝试叶子的所有可能的值：值（A、B、C）和所有可能的组合——值（false、false、false）、值（false、false、true）等。

如果您只对一个这样的表达式产生真值的组合感兴趣，那么这是一个已知的NP问题，所以不要期望多项式运行时：布尔可满足性问题

Answer 3

消除递归的思想如下：当一个节点的所有连接都获得已知值时，该节点将排队等待执行。在您的示例中，在开始时，这些是节点N1、N2、N7。Executor从队列中逐个获取准备执行的节点，计算输出值并将其传递给下一个连接，这可能会导致其他节点排队等。当执行队列变为空时，结果已准备就绪。

你可以自己编程执行器和节点（200-300行代码），或者拿现成的库。要搜索库，请查找“有色Petri网java实现”。有许多可用的Petri网引擎的java实现。除了我自己的df4h-core，我没有使用任何一个。从公式开始est.java计算各种数学公式。您必须实现自己的计算布尔运算的节点。