A*

Что решаем

Головоломка из игры Машинариум. На доске расположены 6 красных и 6 зеленых точек которые образуют три круга. Круги можно вращать. Цель - собрать все зеленые точки в центральный треугольник.

Видео из самой игры https://youtu.be/LbNoM_5jKXE?t=993

Пространство состояний и пути

      1  -  2  -  3     
    /     /   \    \  
   4     5  -  6    7   
    \   / \   / \  / 
      8  -  9  -  10     
       \         /     
         11  -  0

В текущей реализации состояние строка из 12-ти символов "0" или "1".

Переход (ребро графа) - 6 возможных поворотов (3 круга, каждый по часовой стрелке и против)

Каждый переход весит 1

Эвристическая функция

Эвристическая функция возвращает кол-во красных точек в центральном треугольнике. Для конечного состояния h=0

Допустимость и монотонность

Возьмем две соседние вершины A и B. Относительно центрального треугольника поворот "вытаскивает" одну точку и добавляет другую. Всего 4 варианта - убрал красную и вставил красную, убрал красную и вставил зелёную, итд. Разница в оценках всегда h(A) - h(B) <= 1

Т.к. функция монотонна, то она и допустима.

Запуск

Для запуска нужен nodejs >= 10.

Веб вариант

npm install
npm run tsc
npm run webserver

После этого можно перейти на http://localhost:8080

Консольный вариант

npm install
npm run main

Результаты

Исходное состоние

      *  -  @  -  *     
    /     /   \    \  
   @     *  -  @    *   
    \   / \   / \  / 
      @  -  *  -  @     
       \         /     
         *  -  @     

@ - зелёная точка
* - красная точка

С эвристикой

Решение находится за 26 итераций.

С всегда нулевой эвристикой (Алгоритм Дейкстры)

В таком случае происходит 511 итераций

Выбор следующей ноды при равном весе

Текущий алгоритм предпочтёт последнего добавленного соседа если у них веса одинаковые. Если предпочитать первого, то кол-во итерации будет 70 и 647 соответственно.

Общее кол-во состояний

Общее кол-во состояний подсчитано простым брутфорсом и равняется 924 состояния

TODO

не очень хорошо сделано opened (через массив). Это не очень оптимально по производительности

roginvs/test-playground-a-star

A*