Многопоточный решатель задач N-Puzzle

Question

Как домашнее задание в моем текущем курсе CS, нам дали указание написать программу, которая реализует алгоритм A * для задачи n-puzzle .Чтобы решить эту проблему, вы должны взять начальную конфигурацию платы nxn из StdIn.Подвох в том, что некоторые доски не могут быть решаемы.К счастью для нас, если вы создаете «двойную» доску, переворачивая любые два ненулевых квадрата и пытаясь решить эту проблему, нужно разрешить либо оригинал, либо двойника.Поэтому, чтобы реализовать алгоритм, мы эффективно пытаемся решить две доски одновременно, оригинал и двойник.

Выполнить это в одном потоке было довольно легко, и это фактическое назначение.Глядя на эту проблему, кажется, что это идеальное место для использования параллелизма.Я думал, что из основного потока я попытаюсь создать два параллельных потока, каждый из которых пытается решить свою собственную доску.Можно ли обойтись без слишком большого количества сумасшедшего кода в Java?В связи с этим, на многоядерном чипе это будет работать значительно быстрее, чем не многопоточная версия?Я пытаюсь прочитать документацию по Java для потоков, но это немного сложно для тех, кто никогда не пробовал этого раньше, и в этом отношении, я обнаружил, что учусь гораздо быстрее, написав / просмотрев примеры, чем читая больше документации.

Может кто-нибудь дать мне пример кода, который показывает структуру типов, класс, важные утверждения и т. Д.что было бы необходимо сделать это?До сих пор я думал, что хочу реализовать закрытый класс, который реализует реализуемые реализации, и чтобы основной поток выдавал прерывание, для которого когда-либо поток не заканчивает первым, чтобы выяснить, какой из них разрешим, плюс число ходов и последовательность досок дляполучить там.

РЕДАКТИРОВАТЬ: TL; ДР ЭТО НЕ ЧАСТЬ ВЫСТАВОЧНОГО НАЗНАЧЕНИЯ.Назначение должно было сделать однопоточную реализацию.Для собственного обогащения и ТОЛЬКО для собственного обогащения я хочу попробовать сделать мою реализацию многопоточной.

Answer 1

Поскольку вы не хотите, чтобы реализация выполнялась самостоятельно (что, возможно, намного сложнее; таблица транспонирования является узким местом для параллельных реализаций A *), но в практике параллельные алгоритмы IDA * легче реализовать в любом случае и имеют обычный преимущества) проблема на самом деле довольно проста.

Просто упакуйте свою реализацию в работающий класс и используйте поток. Для простоты вы можете просто использовать глобальную логическую переменную volatile, которая инициализируется как 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;
    }

}

Answer 2

Забудьте о решении двух досок, причем одна из них неразрешима. Я не понимаю, как это даже полезно, но игнорируя это, распараллеливание не должно останавливаться на двух процессорах. Если в системе их больше, алгоритм должен использовать их все. Кстати, проверить, разрешима ли плата, довольно легко. Ознакомьтесь с разделом «Разрешимость» в статье Википедии.

Чтобы распараллелить вещи, ваша реализация A * должна иметь некую приоритетную очередь, которая сортирует элементы по эвристическому значению. Расширение узла в дереве поиска включает в себя удаление узла из верхней части очереди и вставку нескольких узлов обратно в очередь, сохраняя сортировку очереди. Когда все организовано таким образом, добавление большего количества потоков для вставки и удаления материалов довольно просто. Просто сделайте доступ к очереди синхронизированным.