А* для нахождения решения «пятнашек»

в 22:38, , рубрики: java, Алгоритмы, пятнашки, метки:

Задача

Наша задача на сегодня состоит в нахождении решения игры «пятнашки». И не любое, а за наименьшее количество ходов. Надо же удивить ребенка тем, что вы умеете ее собирать за 10 ходов!

image

Правила гласят:

Пятна́шки — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.

* Википедия

Описанное здесь решение этой задачи — это реализация одного из Programming Assignments из курса по алгоритмам на coursera.org. Этот курс закончился неделю назад, так что думаю что решение можно публиковать.

Схема решения

Задача годится для учебника по А*. Про сам алгоритм писать не буду, все уже описано в википедии и даже с примерами кода.
В нашем частном случае алгоритм выглядит так:
1. Кладем в очередь с приоритетом первоначальную позицию.
2. Извлекаем из очереди позицию с наименьшим приоритетом.
3. Кладем в очередь все соседние позиции.
4. Повторяем пункты 2-4 пока в пункте 2 не вытащим конечную позицию.

Важно отметить, что в пункте 3 мы кладем не просто позиции сами по себе, а пути, которые привели к данной позиции. То есть наша очередь всегда содержит пути.

Все просто. Правда, для полной ясности надо прояснить, как мы будем определять наименьший приоритет (то есть надо определить нашу эвристическуя функцию). Обратимся опять к википедии:

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

В нашем случае возьмем g(x) равной количеству ходов, которые привели к текушей позиции x.
А h(x) возьмем равной количеству клеток, стоящих не на своем месте.
Например, для позиции
1 2 3
4 5 6
7 8

h(x) = 0, а для

1 2 3
4 5 6
7    8

h(x) = 1, так как 8 не на своем месте.
Почему опредляем так? Трудно сказать. Да и не надо — на то f(x) и эвристическая.
Но нам было важно оценить расстояние до цели (при этом мы можем его недооценить, но не наоборот). Наш способ вполне подходит, ходов в любом случае будет не меньше чем h(x).

Напомню, что А* находит кратчайший путь за полиномиальное время, но потребление памяти растет экспоненциально.

Реализация

Реализация — на джаве.
Для начала создадим класс, который является «доской». Экземпляр такого класса будет хранить одно состояние доски, то есть одну позицию:

Board

import java.util.HashSet;
import java.util.Set;

/**
 * @author Nucleotide
 */
public class Board {
    private int[][] blocks; //   Наше поле. пустое место будем обозначать нулем.
    private int zeroX;    // это нам пригодится в будущем - координаты нуля
    private int zeroY;
    private int h; //  мера

    public Board(int[][] blocks) {
        int[][] blocks2 = deepCopy(blocks);   //   копируем, так как нам нужно быть уверенными в неизменяемости
        this.blocks = blocks2;

        h = 0;
        for (int i = 0; i < blocks.length; i++) {  //  в этом цикле определяем координаты нуля и вычисляем h(x)
            for (int j = 0; j < blocks[i].length; j++) {
                if (blocks[i][j] != (i*dimension() + j + 1) && blocks[i][j] != 0) {  // если 0 не на своем месте - не считается
                    h += 1;
                }
                if (blocks[i][j] == 0) {
                    zeroX = (int) i;
                    zeroY = (int) j;
                }
            }
        }
    }


    public int dimension() {
        return blocks.length;
    }

    public int h() {
        return h;
    }

    public boolean isGoal() {  //   если все на своем месте, значит это искомая позиция
        return h == 0;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Board board = (Board) o;

        if (board.dimension() != dimension()) return false;
        for (int i = 0; i < blocks.length; i++) {
            for (int j = 0; j < blocks[i].length; j++) {
                if (blocks[i][j] != board.blocks[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }

    public Iterable<Board> neighbors() {  // все соседние позиции
        // меняем ноль с соседней клеткой, то есть всего 4 варианта
        // если соседнего нет (0 может быть с краю), chng(...) вернет null
        Set<Board> boardList = new HashSet<Board>();
        boardList.add(chng(getNewBlock(), zeroX, zeroY, zeroX, zeroY + 1));
        boardList.add(chng(getNewBlock(), zeroX, zeroY, zeroX, zeroY - 1));
        boardList.add(chng(getNewBlock(), zeroX, zeroY, zeroX - 1, zeroY));
        boardList.add(chng(getNewBlock(), zeroX, zeroY, zeroX + 1, zeroY));

        return boardList;
    }

    private int[][] getNewBlock() { //  опять же, для неизменяемости
        return deepCopy(blocks);
    }

    private Board chng(int[][] blocks2, int x1, int y1, int x2, int y2) {  //  в этом методе меняем два соседних поля

        if (x2 > -1 && x2 < dimension() && y2 > -1 && y2 < dimension()) {
            int t = blocks2[x2][y2];
            blocks2[x2][y2] = blocks2[x1][y1];
            blocks2[x1][y1] = t;
            return new Board(blocks2);
        } else
            return null;

    }


    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < blocks.length; i++) {
            for (int j = 0; j < blocks.length; j++) {
                s.append(String.format("%2d ", blocks[i][j]));
            }
            s.append("n");
        }
        return s.toString();
    }

    private static int[][] deepCopy(int[][] original) {
        if (original == null) {
            return null;
        }

        final int[][] result = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            result[i] = new int[original[i].length];
            for (int j = 0; j < original[i].length; j++) {
                result[i][j] = original[i][j];
            }
        }
        return result;
    }
}

Дальше, без лишних слов перейдем к реализации А*:

Solver

import java.util.*;

/**
 * @author Nucleotide
 */
public class Solver {  //  наш "решатель"

    private Board initial;    //
    private List<Board> result = new ArrayList<Board>();   // этот лист - цепочка ходов, приводящих к решению задачи

    private class ITEM{    // Чтобы узнать длину пути, нам нужно помнить предидущие позиции (и не только поэтому)
        private ITEM prevBoard;  // ссылка на предыдущий
        private Board board;   // сама позиция

        private ITEM(ITEM prevBoard, Board board) {
            this.prevBoard = prevBoard;
            this.board = board;
        }

        public Board getBoard() {
            return board;
        }


    }

    public Solver(Board initial) {
        this.initial = initial;

        if(!isSolvable()) return;  //  сначала можно проверить, а решаема ли задача?

        //  очередь. Для нахождения приоритетного сравниваем меры
        PriorityQueue<ITEM> priorityQueue = new PriorityQueue<ITEM>(10, new Comparator<ITEM>() {
            @Override
            public int compare(ITEM o1, ITEM o2) {
                return new Integer(measure(o1)).compareTo(new Integer(measure(o2)));
            }
        });


        // шаг 1
        priorityQueue.add(new ITEM(null, initial));

        while (true){
            ITEM board = priorityQueue.poll(); //  шаг 2

            //   если дошли до решения, сохраняем весь путь ходов в лист
            if(board.board.isGoal()) {
                itemToList(new ITEM(board, board.board));
                return;
            }

            //   шаг 3
            Iterator iterator = board.board.neighbors().iterator(); // соседи
            while (iterator.hasNext()){
                Board board1 = (Board) iterator.next();

                //оптимизация. Очевидно, что один из соседей - это позиция
                // которая была ходом раньше. Чтобы не возвращаться в состояния,
                // которые уже были делаем проверку. Экономим время и память.
                if(board1!= null && !containsInPath(board, board1))
                    priorityQueue.add(new ITEM(board, board1));
            }

        }
    }

    //  вычисляем f(x)
    private static int measure(ITEM item){
        ITEM item2 = item;
        int c= 0;   // g(x)
        int measure = item.getBoard().h();  // h(x)
        while (true){
            c++;
            item2 = item2.prevBoard;
            if(item2 == null) {
                // g(x) + h(x)
                return measure + c;
            }
        }
    }

    //  сохранение
    private void itemToList(ITEM item){
        ITEM item2 = item;
        while (true){
            item2 = item2.prevBoard;
            if(item2 == null) {
                Collections.reverse(result);
                return;
            }
            result.add(item2.board);
        }
    }

    // была ли уже такая позиция в пути
    private boolean containsInPath(ITEM item, Board board){
      ITEM item2 = item;
       while (true){
           if(item2.board.equals(board)) return true;
           item2 = item2.prevBoard;
           if(item2 == null) return false;
       }
    }


    public boolean isSolvable() {
       return true;
    }

    public int moves() { 
        if(!isSolvable()) return -1;
        return result.size() - 1;
    }


    // все ради этого метода - чтобы вернуть result
    public Iterable<Board> solution() {
        return result;
    }


}

Тут еще можно сказать несколько слов о методе isSolvable(). В википедии и даже на хабре описана формула, по которой можно легко посчитать — существует решение или нет.

Заключение

Взяв два вышеописанных класса, вы легко сможете находить решение «пятняшек» за минимальное количество ходов. Для этого необходимо создать изначальную позицию и создать Solver:

int[][] blocks = new int[][]{{1, 2, 3}, {4, 0, 5}, {7, 8, 6}};
        Board initial = new Board(blocks);
        Solver solver = new Solver(initial);

после чего, можно просто выводить решение:

        System.out.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                System.out.println(board);

В данном случае получится так:

Minimum number of moves = 2
 1  2  3 
 4  0  5 
 7  8  6 

 1  2  3 
 4  5  0 
 7  8  6 

 1  2  3 
 4  5  6 
 7  8  0 

Или можно чуть иначе:

   int[][] blocks = new int[][]{{1, 2, 3, 0}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 4}};
        Board initial = new Board(blocks);
        Solver solver = new Solver(initial);

Тогда решение будет выглядеть подлиннее…

Minimum number of moves = 19

1 2 3 0
5 6 7 8
9 10 11 12
13 14 15 4

1 2 0 3
5 6 7 8
9 10 11 12
13 14 15 4

1 2 7 3
5 6 0 8
9 10 11 12
13 14 15 4

1 2 7 3
5 6 8 0
9 10 11 12
13 14 15 4

1 2 7 3
5 6 8 12
9 10 11 0
13 14 15 4

1 2 7 3
5 6 8 12
9 10 11 4
13 14 15 0

1 2 7 3
5 6 8 12
9 10 11 4
13 14 0 15

1 2 7 3
5 6 8 12
9 10 0 4
13 14 11 15

1 2 7 3
5 6 0 12
9 10 8 4
13 14 11 15

1 2 7 3
5 6 12 0
9 10 8 4
13 14 11 15

1 2 7 3
5 6 12 4
9 10 8 0
13 14 11 15

1 2 7 3
5 6 12 4
9 10 0 8
13 14 11 15

1 2 7 3
5 6 0 4
9 10 12 8
13 14 11 15

1 2 0 3
5 6 7 4
9 10 12 8
13 14 11 15

1 2 3 0
5 6 7 4
9 10 12 8
13 14 11 15

1 2 3 4
5 6 7 0
9 10 12 8
13 14 11 15

1 2 3 4
5 6 7 8
9 10 12 0
13 14 11 15

1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15

1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

Приятных игр!

Автор: Nucleotide

Поделиться

  1. Bojan:

    Не совсем рабочий пример.
    Беру {{2, 9, 11, 13}, {7, 8, 6, 5}, {12, 14, 1, 4}, {15, 10, 0, 3}}
    и программа перестает работать, и я не совсем понимаю почему.
    Перестает работать на: return new Integer(measure(o1)).compareTo(new Integer(measure(o2)));

    Можете объяснить в чем проблема и как ее решить?

  2. Zek:

    Поддерживаю Bojan-a. При изменении расстановки, не работает. Ошибки не выдает.

* - обязательные к заполнению поля