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

Граф инверсия

Итак, загвоздка в том, что не все доски разрешимы, так как же нам создать доску, чтобы игрок мог играть? Одно дело - просто собрать доску, но опять же, как решить доску? подробнее о решении доски позже, потому что мы сможем выяснить, разрешима ли данная доска, и да, даже не решая ее.

Давайте внимательно посмотрим, что делает каждый ход по отношению к изменению относительного положения плиток. Чтобы быть более конкретным в отношении этих меняющихся позиций, мы придумали концепцию инверсии. Инверсия - это пара плиток, в которой та, которая появляется первой, больше, чем следующая. Формально инверсия - это любая пара плиток i и j, где i ‹j , но i появляется после j при рассмотрении доски в строчном порядке. Под основной строкой мы подразумеваем сначала сканирование строки, а затем ее нижней части.

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

Итак, если мы можем изменить инверсию на четное число, что означает, что если мы начнем с нечетного числа инверсий, мы не сможем достичь инверсии 0, что является желательным состоянием, поскольку нечетное +/- четное является нечетным. Итак, все, что нам нужно сделать, это посчитать инверсию, если ее нечетная плата не разрешима.

Как посчитать количество инверсий? Что ж, это хороший вопрос, который поднимается в интервью. Если вы присмотритесь, инверсия тесно связана с проблемой сортировки (в модели сравнения). Простой подход - просто посмотреть на каждый элемент больше i и посмотреть, меньше ли он.

for (int i=0;i<n;i++)
  for (int j=i+1;j<n;j++)
    if (arr[i]>arr[j]) inv++

Подход O (n²), мы можем взять быстрый метод сортировки, такой как сортировка слиянием, и сделать его быстрее. Это довольно объемная статья сама по себе, поэтому я предлагаю вам немного подумать над ней, а затем погуглить для инверсии подсчета с помощью сортировки слиянием.

A * Поиск (решатель)

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

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

Алгоритм работает следующим образом: выбирается доска с наивысшим приоритетом, и он генерирует свои дочерние элементы, помещает их в очередь и повторяет до тех пор, пока очередь не станет пустой или мы не найдем правильную доску. Просто сохраните указатели, чтобы восстановить раствор. Нажмите Играть, а затем Решить, чтобы увидеть действие.

Стек технологий

Я сделал это в React, где я поддерживаю доску как состояние вот репо.

Справка: - это принстонское поручение.

другие мои проекты найди здесь