通过图形计算的路径的数量 [英] Calculating the number of paths through graph

问题描述

我要寻找独特的数量的 X 的通过图开始在一个特定的节间长的路径。

I am looking the number of unique x length paths through a graph starting at a particular node.

不过，我有没有节点被访问一次以上的任何路径的限制。

However I have a restriction that no node is visited more than once on any path.

例如采取如下图：

For example take the following graph:

如果我是后3长路径的数量从5开始。

If I am after the number of 3 length paths starting at 5.

，答案是9。

5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3

请注意我只是一致的答案（9）不特定的路径

Note I am only concerted with the answer (9) not the specific paths.

我已经使用邻接矩阵给力试过的 X 的给数的路径，但我不知道如何来解释独特的节点限制。

I have tried using an adjacency matrix to the power of x to give the number of paths, but I cannot work out how to account for unique node restriction.

我也尝试过使用一个深度优先搜索但节点的数量和大小的 X 使这不可能。

I have also tried using a depth-first search but the amount of nodes and size of x makes this infeasible.

编辑：迷茫的DFS与BFS（谢谢尼龙微笑和放大器;尼基塔Rybak的）

Confused DFS with BFS (Thank you Nylon Smile & Nikita Rybak).

推荐答案

这是NP难。

减少从哈密尔顿路径。

给定一个图的哈密尔顿路径存在，我们需要检查...

Given a graph whose Hamiltonian Path existence we need to check...

运行你的算法，每个顶点，与路径长度为n-1。任何非零返回对应于汉弥尔顿路径，反之亦然。

Run your algorithm for each vertex, with a path length n-1. Any non-zero return corresponds to Hamiltonian path and vice versa.

因此​​，基本上，如果你找到一个多项式时间算法来解决你的问题，那么你有一个多项式时间算法来解决汉弥尔顿路径问题，有效地证明了P = NP！

So basically, if you find a polynomial time algorithm to solve your problem, then you have a polynomial time algorithm to solve the Hamiltonian Path problem, effectively proving P=NP!

请注意：这里假设x是输入

Note: This assumes x is an input.

如果您x为固定的（即独立于图中的顶点数量），那么你必须为O（n ^ x）的时间算法，这是在P，但仍然pretty的不切实际的中等规模的X.

If you x was fixed (i.e. independent of the number of vertices in the graph), then you have O(n^x) time algorithms, which is in P, but still pretty impractical for medium sized x.

这篇关于通过图形计算的路径的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！