我正在尝试优化图形遍历问题，但无法找出解决它的最佳方法。它看起来既不是 A* 搜索问题（因为我们想要最大化路径而不是最小化它），也不是旅行商问题（因为我们不必访问所有城市）。它的简化版本是这样的：
我们有一组节点和连接/边。连接是任意的，节点可以有一个或多个。连接也有与之关联的接口/类型，并且接口不能支持多个连接。因此，例如，如果 nodeA可以连接到节点B或C通过 interface alpha，并且我们决定将其连接到 node B，则 node 上的接口A不再支持其他连接，因此C无法再连接A。但是，如果节点碰巧具有相同的接口，我们可以将节点连接C到节点。Dalpha
我还应该提到，这些接口就像锁和钥匙一样工作，所以A可以连接到B或，C但不能相互连接（接口就像一面镜子）。此外，虽然不能再通过接口连接到任何东西，因为它被 使用，如果它碰巧有另一个接口（）并且其他东西可以连接到，那么我们可以将多个节点连接到。目标是获得最大的连接节点组（丢弃所有较小的组）。BCAalphaBbravobravoA
我正在考虑一些启发式方法：
- 更喜欢具有更多接口的节点（我已经丢弃了没有对的接口）
- 更喜欢更流行的界面
上述两个规则可用于优先尝试连接到下一个节点（现在我天真地将它们分组为一个等级 - 可连接节点的总数），但我的直觉告诉我我可以做得更好。此外，我认为这不会有利于最佳解决方案。
我试图弄清楚我是否可以以某种方式反转启发式以创建一个变体，A* Search使得 A*“乐观启发式成本”规则仍然适用（即启发式成本 = 丢弃的节点数，但是，这破坏了实际成本计算 -因为我们将从丢弃除一个节点之外的所有节点开始）。
我的另一个想法是计算从起始节点到每个节点的距离（中间节点的数量），并将其平均值用作启发式方法，目标是连接所有节点。但是，我不能保证所有节点都会连接。
编辑： 这是一个例子
- 虚线表示允许（但未激活/经过）的连接
- 接口不允许连接同名的接口，但可以连接自己的
'版本 - 接口只能使用一次（如果我们连接
A到Bviaα，我们将无法再连接A，C因为A不再有α可用的接口） - 节点的数量是任意的（但在算法执行期间是恒定的），并且应该假设非常大
- 每个节点的接口数将至少为一个，如果它使问题更容易，我们可以假设一个上限 - 即 3
- 可能的连接数只是接口兼容性的函数，接口定义节点可以连接的内容，是否/如何使用该接口取决于您
- 激活连接的方向/顺序无关紧要
- 目标是生成最大的连接节点集（我们不关心使用的连接或接口的数量）
