我有一种情况，我想用Python来解决这个问题，但不幸的是我对图表知之甚少。我找到了一个看起来非常适合这个相对简单的任务的库， networkx，但是我在做我想要的事情时遇到了问题，这应该是相当简单的。
我有一个节点列表，可以有不同的类型，以及两个“类”的邻居，向上和向下。任务是在两个目标节点之间找到路径，并考虑到一些约束：
- 只能遍历特定类型的节点，即如果起始节点的类型为x，则路径中的任何节点都必须来自另一组路径y或z
- 如果节点的类型为y，则只能传递一次
- 如果节点具有类型z，则可以传递两次
- 如果访问类型为z的节点，则出口必须来自不同类别的邻居，即如果从上向下访问，则出口必须从向下
所以，我尝试了一些实验，但正如我所说，我一直在努力。首先，我不确定这实际代表什么类型的图表？它不是方向性的，因为从节点1到节点2，或从节点2到节点1无关紧要（除 在最后一个场景中，所以使事情变得复杂......）。这意味着我不能只创建一个简单的多向图，因为我必须考虑到这个约束。其次，我必须遍历这些节点，但指定只有特定类型的节点必须可用于路径。此外，如果最后一个场景发生，我必须记住入口和出口类/方向，这使它处于某种有针对性的状态。
这是一些示例模型代码：
import networkx as nx
G=nx.DiGraph()
G.add_node(1, type=1)
G.add_node(2, type=2)
G.add_node(3, type=3)
G.add_edge(1,2, side="up")
G.add_edge(1,3, side="up")
G.add_edge(2,1, side="down")
G.add_edge(2,3, side="down")
for path in nx.all_simple_paths(G,1,3):
print path
输出相当不错，但我需要这些约束。那么，您是否有一些建议我如何实现这些，或者给我一些关于理解这类问题的指导，或者针对这个问题提出不同的方法或库？也许一个简单的基于字典的算法适合这种需要？
谢谢！
如果以不同方式构造图形，则可以对问题使用all_simple_paths（）函数。简单路径是没有重复节点的路径。因此，对于您的约束，这里有一些构建图形的建议，以便您可以不修改地运行该算法。
- 只能遍历特定类型的节点，即如果起始节点的类型为x，则路径中的任何节点都必须来自另一组路径y或z
给定起始节点n，在找到路径之前删除具有该类型的所有其他节点。
这是简单路径的定义，因此它会自动满足。
对于z类型的每个节点n，添加一个新节点n2，其边缘与指向n和n的节点相同。
- 如果访问类型为z的节点，则出口必须来自不同类别的邻居，即如果从上向下访问，则出口必须从向下
如果边缘是按照你的建议定向的，那么如果你确保z的边都是相同的方向，那么这可以得到满足 - 例如为了向下和向下...
我认为最好的方法是通过最多计算所有有效的长度路径 ķ 来源之间 小号 和其他每个节点，然后使用该信息计算最多长度的所有有效路径 K + 1。然后，您只需重复此操作，直到获得没有修改路径的固定点。
实际上，这意味着您应该在每个节点上设置路径列表。在每个步骤中，您将获取每个节点 ü 反过来看看在上一步中终止于某个邻居的路径 V 的 ü。如果这些路径中的任何一个可以扩展为新的，不同的路径 ü，扩展它并将其添加到 ü的清单。
如果执行步骤时没有找到新路径，那就是终止状态。然后，您可以检查目标节点上的路径列表 Ť。
伪代码（以非常松散的C＃形式）：
var paths = graph.nodes.ToDictionary(node => node, node => new List<List<node>>())
paths[S].Add(new List<node> {S}) // The trivial path that'll start us off.
bool notAFixedPoint = true;
while (notAFixedPoint)
{
notAFixedPoint = false // Assume we're not gonna find any new paths.
foreach (var node in graph)
{
var pathsToNode = paths[node]
foreach (var neighbour in node.Neighbours)
{
var pathsToNeighbour = paths[neighbour]
// ExtendPaths is where all the logic about how to recognise a valid path goes.
var newPathsToNode = ExtendPaths(pathsToNeighbour, node)
// The use of "Except" here is for expository purposes. It wouldn't actually work,
// because collections in most languages are compared by reference rather than by value.
if (newPathsToNode.Except(pathsToNode).IsNotEmpty())
{
// We've found some new paths, so we can't terminate yet.
notAFixedPoint = true
pathsToNode.AddMany(newPathsToNode)
}
}
}
}
return paths[T]
对我来说，这看起来像是一个优化问题 - 查找“旅行推销员”，找到一个与您想要做的有点接近的经典示例。
我有幸使用“模拟退火”来解决优化问题，但您也可以看看“遗传算法”。