未加权无向图中的最长路径 - java

将此图作为参考，假设我想要0到5之间的最长路径。

那将是:0-> 1-> 3-> 2-> 4-> 6-> 5

有什么好的算法吗？我已经搜索过，却没有发现我能理解的任何东西。
我已经找到了最短路径(0-> 1-> 2-> 4-> 6-> 5)的大量算法，并且已经成功实现了它们。
也许我是问题所在，但我想另外考虑一下:)

任何帮助都将受到欢迎

参考方案

这个问题是NP-Hard(从哈密顿路径到您的问题有一个简单的减少，而哈密顿路径搜索被称为NP-哈德)。这意味着没有针对此问题的多项式解(除非P = NP)。

如果需要精确的解决方案，则可以使用动态编程(状态的指数数量):状态为(mask of visited vertices, last_vertex)，值为true或false。如果mask和新顶点之间存在边，则过渡将添加不在last_vertex中的新顶点。它具有O(2^n * n^2)时间复杂度，仍然比O(n!)回溯更好。

这是动态编程解决方案的伪代码:

f = array of (2 ^ n) * n size filled with false values
f(1 << start, start) = true
for mask = 0 ... (1 << n) - 1:
    for last = 0 ... n - 1:
        for new = 0 ... n - 1:
            if there is an edge between last and new and mask & (1 << new) == 0:
                f(mask | (1 << new), new) |= f(mask, last)
res = 0
for mask = 0 ... (1 << n) - 1:
    if f(mask, end):
        res = max(res, countBits(mask))
return res

还有更多关于从哈密顿路径到此问题的约简:

def hamiltonianPathExists():
    found = false
    for i = 0 ... n - 1:
        for j = 0 ... n - 1:
            if i != j:
                path = getLongestPath(i, j) // calls a function that solves this problem
                if length(path) == n:
                    found = true
    return found

这是一个Java实现(我没有正确测试，因此可能包含错误):

/**
 * Finds the longest path between two specified vertices in a specified graph.
 * @param from The start vertex.
 * @param to The end vertex.
 * @param graph The graph represented as an adjacency matrix.
 * @return The length of the longest path between from and to.
 */
public int getLongestPath(int from, int to, boolean[][] graph) {
    int n = graph.length;
    boolean[][] hasPath = new boolean[1 << n][n];
    hasPath[1 << from][from] = true;
    for (int mask = 0; mask < (1 << n); mask++)
        for (int last = 0; last < n; last++)
            for (int curr = 0; curr < n; curr++)
                if (graph[last][curr] && (mask & (1 << curr)) == 0)
                    hasPath[mask | (1 << curr)][curr] |= hasPath[mask][last];
    int result = 0;
    for (int mask = 0; mask < (1 << n); mask++)
        if (hasPath[mask][to])
            result = Math.max(result, Integer.bitCount(mask));
    return result;
}

Java中的“ <<”运算符 - java

最喜欢的语句来自Java的Character类：(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节，type是整数。这句话中的操作员，他们做什么？如何以及在哪里可以使用这些运算符？这是oracles java.lang.Character文档。该类中…

Java:正则表达式模式匹配器是否有大小限制？ - java

我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗？ 参考方案 您仅受记忆和理智的限制。 :)

Java:线程池如何将线程映射到可运行对象 - java

试图绕过Java并发问题，并且很难理解线程池，线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池，那么我是否必须将相同的任务传递给池中的每个线程，或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务？无论哪种方式，Executor / ExecutorService如何将正确的任务分配给正确的线程？ 参考方案 …

JAVA:字节码和二进制有什么区别？ - java

java字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。 参考方案 字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…

java:继承 - java

有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…