java - N-Puzzle 问题的多线程求解器

Question

作为我当前 CS 类(class)的家庭作业，我们被指示编写一个程序，为 n-puzzle problem 实现 A* 算法。 .为了求解，您必须从 StdIn 中获取初始 nxn 板配置。问题是有些董事会可能无法解决。对我们来说值得庆幸的是，如果您通过翻转任意两个非零方 block 创建一个“双胞胎”棋盘并尝试解决该问题，则原始棋盘或孪生棋盘必须是可解的。因此，为了实现该算法，我们正在尝试同时有效地解决两 block 板，原始板和孪生板。

在单线程中执行此操作非常简单，这就是实际的分配。看看这个问题，这似乎是利用并行性的完美地方。我在想，从主线程我会尝试产生两个并发线程，每个线程都试图解决自己的问题。如果没有太多疯狂的 java 代码，这可能吗？就此而言，在多核芯片上运行速度会比非多线程版本快得多吗？我正在尝试通读线程的 java 文档，但对于以前从未尝试过此问题的人来说，它有点厚，就此而言，我发现通过编写/查看示例比阅读更多文档更快地学习。

有人能给我一些显示类型结构、类、重要语句等的示例代码吗？这样做有必要吗？到目前为止，我在想我想实现一个私有(private)类，该类实现可运行，并让主线程抛出一个中断，任何线程都没有首先完成，以确定哪个是可解决的，加上移动的次数和板的顺序到达那里。

编辑:TL;DR 这不是评分作业的一部分。任务是执行单线程实现。为了充实自己，而且仅仅是充实自己，我想尝试使我的实现多线程化。

Answer 1

因为您不希望实现自己线程化(这可以说要复杂得多；换位表是并行 A* 实现的瓶颈 - 但在实践中，并行 IDA* 算法更容易实现，并且具有通常的优点)问题其实很简单。

只需将您的实现打包到一个可运行的类中并使用一个线程。为简单起见，您可以只使用一个全局 volatile boolean 变量，该变量初始化为 false，并在一个线程找到解决方案后立即设置为 true。您现在只需检查代码中适当情况下的标志，如果其他线程已经找到解决方案则返回。您也可以使用中断，但保持简单不会有什么坏处(最终它实际上非常相似，您只需稍微检查变量即可)。

简单的例子:

public class Main implements Runnable {
    private static volatile boolean finished = false;

    public static void main(String[] args) {
        new Thread(new Main()).start();
        new Main().run();
    }

    @Override
    public void run() {
        while (!finished) {
            // do stuff
            if (solutionFound) {
                finished = true;
                // save result
            }
        }
        return;
    }

}