Каким может быть эффективный подход к решению задачи «8 головоломок»?

Я просто попытаюсь переписать предыдущий ответ с более подробной информацией о том, почему он оптимален.

Алгоритм A *, взятый непосредственно из wikipedia, является

            function A*(start,goal)
                    closedset := the empty set                 // The set of nodes already evaluated.     
                    openset := set containing the initial node // The set of tentative nodes to be evaluated.
                    came_from := the empty map                 // The map of navigated nodes.
                    g_score[start] := 0                        // Distance from start along optimal path.
            h_score[start] := heuristic_estimate_of_distance(start, goal)
                    f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
                    while openset is not empty
                    x := the node in openset having the lowest f_score[] value
                    if x = goal
            return reconstruct_path(came_from, came_from[goal])
                    remove x from openset
                    add x to closedset
            foreach y in neighbor_nodes(x)
                    if y in closedset
                    continue
            tentative_g_score := g_score[x] + dist_between(x,y)

                    if y not in openset
                    add y to openset
                    tentative_is_better := true
                    elseif tentative_g_score < g_score[y]
                    tentative_is_better := true
                    else
                    tentative_is_better := false
                    if tentative_is_better = true
                    came_from[y] := x
                    g_score[y] := tentative_g_score
            h_score[y] := heuristic_estimate_of_distance(y, goal)
                    f_score[y] := g_score[y] + h_score[y]
                    return failure

            function reconstruct_path(came_from, current_node)
                    if came_from[current_node] is set
                    p = reconstruct_path(came_from, came_from[current_node])
            return (p + current_node)
                    else
                    return current_node

Так что позвольте мне заполнить все подробности здесь.

heuristic_estimate_of_distance - это функция d (x _i), где d (.) - манхэттенское расстояние каждого квадрата x _i от его целевого состояния.

Итак, установка

            1 2 3
            4 7 6
            8 5 

будет иметь heuristic_estimate_of_distance, равное 1 + 2 + 1 = 4, поскольку каждый из 8,5 находится на расстоянии одного от своей целевой позиции с d (.) = 1, а 7 - на 2 от своего целевого состояния с d (7) = 2.

Набор узлов, по которым выполняет поиск A *, определяется как начальная позиция, за которой следуют все возможные правовые позиции. То есть, допустим, начальная позиция x такая же, как указано выше:

            x =
            1 2 3
            4 7 6
            8 5 

тогда функция neighbor_nodes(x) производит 2 возможных допустимых хода:

            1 2 3
            4 7 
            8 5 6

            or

            1 2 3
            4 7 6
            8   5

Функция dist_between(x,y) определяется как количество квадратных ходов, которые имели место для перехода из состояния x в y. Обычно это всегда будет равно 1 в A * для целей вашего алгоритма.

closedset и openset относятся к алгоритму A * и могут быть реализованы с использованием стандартных структур данных (я считаю, очереди с приоритетами). came_from - это структура данных, используемая для восстановления решения, найденного с помощью функции reconstruct_path, подробности которой можно найти в Википедии. Если вы не хотите запоминать решение, вам не нужно его реализовывать.

Наконец, я коснусь вопроса оптимальности. Рассмотрим отрывок из статьи в Википедии A *:

«Если эвристическая функция h допустима, что означает, что она никогда не переоценивает фактические минимальные затраты на достижение цели, то A * сама является допустимой (или оптимальной), если мы не используем замкнутый набор. Если используется замкнутое множество, то h также должен быть монотонным (или согласованным), чтобы A * было оптимальным. Это означает, что для любой пары смежных узлов x и y, где d (x, y) обозначает длину ребра между ними, мы должны иметь: h (x) ‹= d (x, y) + h (y)"

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

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

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

В нашем случае показать монотонность довольно просто. Любые соседние узлы x, y имеют d (x, y) = 1 по нашему определению d. Таким образом, нам нужно показать

h(x) <= h(y) + 1

что эквивалентно

h(x) - h(y) <= 1

что эквивалентно

d (x _i) - d (y _i) ‹= 1

что эквивалентно

d (x _i) - d (y _i) ‹= 1

Мы знаем из нашего определения neighbor_nodes(x), что два соседних узла x, y могут иметь не более одного различающегося положения квадрата, что означает, что в наших суммах термин

d (x _i) - d (y _i) = 0

для всех значений i, кроме 1. Без ограничения общности это верно для i = k. Кроме того, мы знаем, что для i = k узел переместился не более чем на одно место, поэтому его расстояние до целевого состояния должно быть не более чем на единицу больше, чем в предыдущем состоянии, таким образом:

d (x _i) - d (y _i) = d (x _k) - d (y _k ) ‹= 1

демонстрируя монотонность. Это показывает, что нужно показать, тем самым доказывая, что этот алгоритм будет оптимальным (в нотации большого O или асимптотическом способе).

Обратите внимание, что я продемонстрировал оптимальность с точки зрения нотации большого О, но есть еще много возможностей поиграть с точки зрения настройки эвристики. Вы можете добавить к нему дополнительные повороты, чтобы получить более точную оценку фактического расстояния до состояния цели, однако вы должны убедиться, что эвристика всегда является < em> недооценивайте, иначе вы потеряете оптимальность!

ИЗМЕНИТЬ МНОГИМИ ЛУНАМИ СПУСТЯ

Прочитав это снова (намного) позже, я понял, что то, как я это написал, как бы сбивает с толку смысл оптимальности этого алгоритма.

Я пытался здесь понять два различных значения оптимальности:

1) Алгоритм дает оптимальное решение, то есть наилучшее возможное решение с учетом объективных критериев.

2) Алгоритм расширяет наименьшее количество узлов состояния всех возможных алгоритмов, используя ту же эвристику.

Самый простой способ понять, почему вам нужна допустимость и монотонность эвристики для получения 1), - это рассматривать A * как приложение алгоритма кратчайшего пути Дейкстры на графе, где веса ребер задаются расстоянием до узлов, пройденным до сих пор, плюс эвристика расстояние. Без этих двух свойств у нас были бы отрицательные ребра в графе, поэтому отрицательные циклы были бы возможны, и алгоритм кратчайшего пути Дейкстры больше не возвращал бы правильный ответ! (Постройте простой пример, чтобы убедиться в этом сами.)

2) на самом деле довольно запутанно для понимания. Чтобы полностью понять смысл этого утверждения, в этом утверждении есть много квантификаторов, например, когда речь идет о других алгоритмах, один относится к similar алгоритмам как A *, которые расширяют узлы и осуществляют поиск без априорной информации (кроме эвристики. Очевидно, что в противном случае можно построить тривиальный контрпример, такой как оракул или джин, который сообщает вам ответ на каждом этапе пути. Чтобы глубже понять это утверждение, я настоятельно рекомендую прочитать последний абзац раздела «История» в Википедии, а также просмотр всех цитат и сносок в этом тщательно сформулированном предложении.

Я надеюсь, что это проясняет оставшуюся путаницу среди потенциальных читателей.

Вы можете использовать эвристику, основанную на позициях чисел, то есть чем выше общая сумма всех расстояний каждой буквы от ее целевого состояния, тем выше эвристическое значение. Затем вы можете реализовать поиск A *, который может оказаться оптимальным с точки зрения сложности времени и пространства (при условии, что эвристика монотонна и допустима). http://en.wikipedia.org/wiki/A*_search_algorithm

Поскольку ОП не может опубликовать изображение, он говорит об этом:

Чтобы решить эту загадку, обратите внимание на итеративный поиск с углублением в глубину алгоритм, связанный с проблемой 8 головоломок на этой странице.

Пончик получил! IDDFS сделает свое дело, учитывая относительно ограниченное пространство поиска этой головоломки. Поэтому было бы эффективно ответить на вопрос ОП. Было бы найдено оптимальное решение, но не обязательно с оптимальной сложностью.

Реализация IDDFS была бы более сложной частью этой проблемы, я просто хочу предложить простой подход к управлению доской, правилами игры и т. Д. Это, в частности, касается способа получения начальных состояний для решаемой головоломки. Намек в примечаниях к вопросу, что не все случайные наборы из 9 знаков (учитывая, что пустой слот является особой плиткой), дадут решаемую головоломку. Это вопрос математической четности ... Итак, вот предложения по моделированию игры:

Составьте список всех матриц перестановок 3x3, которые представляют действительные «ходы» игры. Такой список представляет собой подмножество 3x3s со всеми нулями и двумя единицами. Каждая матрица получает идентификатор, который будет очень удобно отслеживать ходы в дереве поиска IDDFS. Альтернативой матрицам является наличие двух кортежей номеров позиций тайлов для обмена, это может привести к более быстрой реализации.

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

Теперь давайте просто реализуем алгоритм IDDFS и [шутка] вернем назначение для A + [/ joke] ...

Это пример классического алгоритма поиска кратчайшего пути. Подробнее о кратчайшем пути вы можете узнать здесь и здесь.

Короче говоря, думайте обо всех возможных состояниях головоломки как о вершинах некоторого графа. С каждым ходом вы меняете состояния, поэтому каждое допустимое движение представляет собой край графа. Поскольку у ходов нет затрат, вы можете думать, что стоимость каждого хода равна 1. Следующий псевдокод, подобный C ++, подойдет для этой проблемы:

{
int[][] field = new int[3][3];
//  fill the input here
map<string, int> path;
queue<string> q;
put(field, 0); // we can get to the starting position in 0 turns
while (!q.empty()) {
    string v = q.poll();
    int[][] take = decode(v); 
    int time = path.get(v);
    if (isFinalPosition(take)) {
        return time;
    }
    for each valid move from take to int[][] newPosition {
        put(newPosition, time + 1);
    }
}
// no path
return -1;
}

void isFinalPosition(int[][] q) {
    return encode(q) == "123456780"; // 0 represents empty space
}
void put(int[][] position, int time) {
    string s = encode(newPosition);
    if (!path.contains(s)) {
        path.put(s, time);
    }
}

string encode(int[][] field) {
    string s = "";
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j];
    return s;
}

int[][] decode(string s) {
    int[][] ans = new int[3][3];
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j];
    return ans;
}

См. Эту ссылку для моего параллельного итеративного углубленного поиска решения головоломки из 15 , который является старшим братом 4x4 головоломки 8.