Преобразовать метод обратного отслеживания DFS в метод, который возвращает список допустимых шагов? - PullRequest
Новая
       44

Преобразовать метод обратного отслеживания DFS в метод, который возвращает список допустимых шагов?

0 голосов
/ 20 апреля 2020

Я очень новичок в DFS и возврате, но недавно мне удалось создать метод для решения головоломки, которую я запрограммировал, используя стандартный алгоритм возврата. Прямо сейчас метод возвращает полностью решенную головоломку в виде Optional<Configuration>. Для пояснения, Configuration - это просто интерфейс с isGoal (), getSuccessors () и isValid (), то есть стандартными методами возврата.

Как я могу изменить этот алгоритм обратного отслеживания, чтобы он возвращал список допустимых шагов к полному решению, а не само решение. Я предпринял попытку сделать это ниже (отмеченную как «модифицированный метод решения»), и пока он выводит только список из множества копий решения, когда мне нужно, чтобы он содержал каждый действительный шаг вплоть до полного решения.

Оригинальный метод решения: 

public Optional<Configuration> solve(Configuration config) {
        if (config.isGoal()) {
            return Optional.of(config);
        } else {
            for (Configuration child : config.getSuccessors()) {
                if (child.isValid()) {
                    Optional<Configuration> sol = solve(child);
                    if (sol.isPresent()) {
                        return sol;
                    }
            }
        }
        return Optional.empty();
}

Модифицированный метод решения (не работает): 

private List<Configuration> solver (Configuration current, ArrayList<Configuration> moves) {
        if (current.isGoal()) {
            moves.add(current);
            return moves;
        } else {
            for (Configuration child : current.getSuccessors()) {
                if (child.isValid()) {
                    List<Configuration> sol = solver(child, moves);
                    if (!sol.isEmpty()) {
                        moves.addAll(sol);
                        return sol;
                    }
            }
        }
        return new ArrayList<>();
}

Включите мое объяснение интерфейса было сбивает с толку, вот мой класс конфигурации. Сама загадка не имеет отношения к этой проблеме, потому что этот конкретный метод следует алгоритму, который должен работать для любого типа головоломок с сеткой 2D-массивов. Кроме того, оригинальный метод решения работает отлично.

Интерфейс конфигурации: 

public interface Configuration {
    /**
     * Get the collection of successors from the current one.
     * @return All successors, valid and invalid
     */
    public Collection< Configuration > getSuccessors();

    /**
     * Is the current configuration valid or not?
     * @return true if valid; false otherwise
     */
    public boolean isValid();

    /**
     * Is the current configuration a goal?
     * @return true if goal; false otherwise
     */
    public boolean isGoal();
...