poster
2019-12-14, 20:13
我正在处理无向图。我需要在图中找到所有可能的非循环路径：
with G(V,E) find all subsets of V that are acyclic paths 我正在使用python scipy或matlab-无论哪种都合适。有什么聪明的解决方案吗？
我正在尝试通过广度优先搜索来实现它（请参阅Wiki）
我在matlab中也有此工具箱： http (http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox) : //www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox， (http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox)但看来我的问题没有简单的解决方案。
PS。实际上，该问题表示为：公交网络设计问题：找到这样一种交通网络，该交通网络可以将过客和运营商的成本降到最低（例如，市区最佳地铁网络）
在此先感谢Rafal
回答：
我认为您的PS中所述的问题可能是NP问题。如果是这样，那么仅对于具有非常有限的节点数（N〜
with G(V,E) find all subsets of V that are acyclic paths 我正在使用python scipy或matlab-无论哪种都合适。有什么聪明的解决方案吗？
我正在尝试通过广度优先搜索来实现它（请参阅Wiki）
我在matlab中也有此工具箱： http (http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox) : //www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox， (http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox)但看来我的问题没有简单的解决方案。
PS。实际上，该问题表示为：公交网络设计问题：找到这样一种交通网络，该交通网络可以将过客和运营商的成本降到最低（例如，市区最佳地铁网络）
在此先感谢Rafal
回答：
我认为您的PS中所述的问题可能是NP问题。如果是这样，那么仅对于具有非常有限的节点数（N〜