Sokoban: оптимальные решения

[B@R5uk]

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

Цитата:

CellsAdjacency.java
CellVector.java
MapHandler.java
MapLoader.java
State_Space_Explorer_2.java
State.java
StateProcessor.java

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

Технически эта часть программы (функция findActiveCells () в файле MapHandler.java) реализована как два поиска в ширину: в одном грузчик толкает ящик из каждой начальной позиции, в другом — он тащит его из каждой конечной позиции. В каждом случае каждая ячейка, в которой побывал ящик помечается, а в конце выполняется конъюнкция двух получившихся карт. Результаты расчётов выглядят приблизительно так (запятыми на второй карте помечены активные ячейки лабиринта):

Используется синтаксис Text

Microban L05

 #######
 #     #
 # .$. #
## $@$ #
#  .$. #
#      #
########

 #######
 #.....#
 #,,,,.#
##,,,,.#
#.,,,,.#
#......#
########

Cells:     27
Active:    12
Boxes:      4
                   Placements    States
Theoretical:           17 550   403 650
Reduced:                  495    11 385

Forward total:         17 550   399 910
Forward dead:          17 106   389 706
Matched:                  444    10 204
Backward dead:              8         8
Backward total:           445    10 212

Forward total:            495    11 376
Forward dead:              52     1 173
Matched:                  444    10 203
Backward dead:              9         9
Backward total:           445    10 212



Yoshio Hand-Made L06

  #####  
  #   ## 
###$   ##
#  .$.$ #
# #.#.# #
#  *$*  #
###   ###
  # @ #  
  #####  

  #####  
  #...## 
###,,,.##
#.,,,,,.#
#.#,#,#.#
#.,,,,,.#
###,.,###
  #...#  
  #####  

Cells:     31
Active:    17
Boxes:      6
                   Placements       States
Theoretical:          736 281   18 407 025
Reduced:               12 376      309 400

Forward total:        272 429    6 082 562
Forward dead:         270 208    6 035 122
Matched:                2 357       47 440
Backward dead:         10 559      104 378
Backward total:        11 748      151 818

Forward total:         11 403      220 720
Forward dead:           9 182      173 280
Matched:                2 357       47 440
Backward dead:          5 869       37 131
Backward total:         7 058       84 571



Nabokosmos L40

   #####
 ###   #
##     #
# *** ##
#  *@ #
# .*$##
##   #
 ##  #
  ####

   #####
 ###...#
##.,,,.#
#.,,,,##
#.,,,.# 
#.,,,## 
##.,,#  
 ##..#  
  ####  

Cells:     27
Active:    15
Boxes:      6
                   Placements      States
Theoretical:          296 010   6 216 210
Reduced:                5 005     105 105

Forward total:        295 729   5 807 533
Forward dead:         294 967   5 793 018
Matched:                  865      14 515
Backward dead:          2 583      12 442
Backward total:         2 976      26 957

Forward total:          4 822      80 938
Forward dead:           4 060      66 423
Matched:                  865      14 515
Backward dead:          2 583      12 442
Backward total:         2 976      26 957



SokWhole L24

 ######  
##  . ## 
#@$ *$ ##
## $.$  #
 ###.*  #
   #.  ##
   ##### 

 ######  
##.,,.## 
#.,,,,.##
##.,,,,.#
 ###,,,.#
   #,,.##
   ##### 

Cells:     23
Active:    15
Boxes:      6
                   Placements      States
Theoretical:          100 947   1 716 099
Reduced:                5 005      85 085

Forward total:         43 258     672 200
Forward dead:          43 237     671 943
Matched:                   21         257
Backward dead:            721       3 221
Backward total:           734       3 478

Forward total:          1 396      18 502
Forward dead:           1 375      18 245
Matched:                   21         257
Backward dead:            721       3 221
Backward total:           734       3 478
 

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

Используется синтаксис Text

Yoshio52 L09

#####
#. .###
#.#$$ #
#   @ #
# $#  #
##   ##
 #####

#####  
#,!,###
#,#,,.#
#,,,,.#
#.,#,.#
##...##
 ##### 

Cells:     19
Active:    11
Boxes:      3
                   Placements   States
Theoretical:              969   15 504
Reduced:                  165    2 640

Forward total:            190    2 762
Forward dead:             153    2 268
Matched:                   37      494
Backward dead:            130    1 584
Backward total:           157    2 078

Forward total:             62      852
Forward dead:              25      358
Matched:                   37      494
Backward dead:             99    1 196
Backward total:           126    1 690
 

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

[B@R5uk]

Нашёл косяк: в файле StateProcessor.java в методе private void matchStates () в последнем внешнем условии в обоих его ветках код

Используется синтаксис Java

            } else {
                uniqueForwardStates   .add (forwardState);
                uniqueBackwardStates  .add (backwardState);
            }

надо заменить на

Используется синтаксис Java

            } else {
                if (0 == forwardState .compareTo (backwardState)) {
                    matchedForwardStates  .add (forwardState);
                    matchedBackwardStates .add (backwardState);
                } else {
                    uniqueForwardStates   .add (forwardState);
                    uniqueBackwardStates  .add (backwardState);
                }
            }

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

Правильная статистика для Microban L05 выглядит так:

Используется синтаксис Text

Forward total:         17 550   399 910
Forward dead:          17 106   389 706
Matched:                  444    10 204
Backward dead:              8         8
Backward total:           445    10 212

Forward total:            495    11 376
Forward dead:              51     1 172
Matched:                  444    10 204
Backward dead:              8         8
Backward total:           445    10 212

Последние три строчки в обоих случаях (с использованием данных о мёртвых ячейках и без использования) должны быть одинаковыми.

-- 16.05.2021, 11:08 --

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

Используется синтаксис Text

    #####             
    #...#             
    #,.,#             
  ###,.,###           
  #.,,,,,.#           
###.#,###.#     ######
#...#,###.#######.,,,#
#.,,,,,,,,,,,,,,,,,,,#
#####,####.#.####.,,,#
    #......###  ######
    ########          
Cells:     61
Active:    37
Boxes:      6
Reduced:            2 324 784     127 863 120

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

[B@R5uk]

Накатал тут честный брутфорсер для сокобана на коленке за два дня (большая часть кода — копипаст с предыдущего проекта, но тем не менее). Он добросовестно измеряет композитное расстояние между нодами в графе решений, которое состоит из двух величин: числа ходов и числа толканий; и так же добросовестно их сравнивает: сначала приоритетные величины расстояний, потом, если они совпали, — вторичные величины. В зависимости от того, какая пара сравнивается первой, получается либо честное move-optimal, push-optimal решение, либо наоборот, честное push-optimal, move-optimal решение.

Цитата:

CellsAdjacency.java
CellVector.java
MapHandler.java
MapLoader.java
Sokoban_Brute_Solver_2.java
State.java
StateProcessor.java

Алгоритм заключается в аккуратной реализации поиска Дэйкстры на графе состояний со всеми "радостями", возникающими при использовании стандартных коллекций. Я пошёл дальше: кроме поиска честного оптимального решения добавил подсчёт этих всех возможных оптимальных решений. В принципе, задача стандартная и заключается в подсчёте числа путей из ноды в ноду на ориентированном графе. Тут только надо аккуратно проследить, чтобы эти пути были оптимальными. Более того, тут же сразу делается случайный выбор одного из этих решений. Там, где подсчитывается полная сумма числа входящих в ноду оптимальных путей, можно сделать выбор одной группы этих путей с правильной вероятностью (группа заканчивается одним и тем же ходом в рассматриваемой ячейке, выбор конкретного пути в группе уже сделан ранее, тут важен только "вес" всей группы), и каждое из возможных решений будет в результате выбираться с одинаковой вероятностью. (Разумеется, равновероятными они будут на столько, на сколько позволят последовательные вызовы генератора псевдослучайных чисел).

Брутфорсер решает задачу обратным ходом. Это позволяет получить лучший результат меньшей ценой без использования отсечения мёртвых позиций. Первый уровень оригинальной игры, разумеется, ему не под силу, но вот если его слегка урезать, то будет совсем другое дело:

Используется синтаксис Text

    #####             
    #   #             
    #$  #             
  ###  $###           
  #  $  $ #           
### # ### ######
#   # ### #  ..#
# $  $    @  ..#
###########  ..#
          ######

________________________
Move-priority solution:

Moves  number:   195
Pushes number:    80

luuuL LUllD llddd rRRRR RRRur Dlllu
uullu lldDD uulld ddrRR RRRRR dRRlU
llluu ullLu uurDD llDDD uulld ddrRR
RRRRR uRRlD lllll llllu lldRR RRRRR
RRRRR llllu uulLu uullD DDDDu ulldd
drRRR RRRRd RUlll uuull LulDD Duull
dddrR RRRRR RRluR

Total number of different solutions: 4900

________________________
Push-priority solution:

Moves  number:   195
Pushes number:    80

luuuL LUllD llddd rRRRR RRRdr Ulllu
uullu lldDD uulld ddrRR RRRRR RRlll
luuul lLuuu rDDll DDDuu llddd rRRRR
RRRRl lluuu lLuul ulDDD DDuul ldddr
RRRRR RRuRR lDlll uuull LulDD Duull
dddrR RRRRR RdRRl Ullll lllll ulldR
RRRRR RRRRu RDldR

Total number of different solutions: 4900
 

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

Используется синтаксис Text

..\Sokwhole.txt  #45

######   
#    ##  
# $ $ ## 
## $.$+##
 # ..*. #
 ##$# # #
  #     #
  #######

________________________
Move-priority solution:

Moves  number:    89
Pushes number:    27

LuLul lDurr dLrrd DllUR Rdrrd dllUU
luuul Dulld Rurrd rDldl lURdr RuulD
rdddl lUUlu RRuul Dulld RRDuu rDrD

Total number of different solutions: 2

________________________
Push-priority solution:

Moves  number:   103
Pushes number:    23

LuLul lDurr dLrrd DllUR Rulul Dulld
Rurrd ddllU RRdrr rddll llUdr rrruu
llluu rDldR lulld Rddrr Udllu uuruu
lDDuu lldRR urD

Total number of different solutions: 84
 

Не смотря на всю простоту получившейся программы и ограниченные её возможности, я считаю результат определённым достижением. Какой ещё солвер позволяет каждый раз находить новое оптимальное решение?

(Оффтоп)

П.С. Не обошлось и без очепяток. В файле StateProcessor.java в самом конце функции public void displaySolution () вместо
Long .MAX_VALUE == solutionRoot .getPathCount ()
надо
Integer .MAX_VALUE == solutionRoot .getPathCount ()

[zykov]

B@R5uk в сообщении #1504881 писал(а):

Можете поделиться рекомендациями по этим солверам?

Году в 2004-2005 я писал такой солвер на C++ (для себя, ради интереса).
Идея тут простая - просто поиск перебором вширь.

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

B@R5uk в сообщении #1504843 писал(а):

На ряду с просто поиском решения конкретного уровня можно поставить задачу найти решение с минимально возможным числом ходов. Или же решение с минимальным числом толканий ящиков.

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

Вот тут кстати возникает интересная задача по ИИ, до которой руки так и не дошли.
Искать пусть не оптимальное, но "хорошее" решение на больших картах, где не получается найти оптимум из-за технических ограничений.
Вот например здесь использование второй цели вместо первой - это пример более дешевого поиска "хорошего" решения, пусть и не оптимального с точки зрения первой цели.

B@R5uk в сообщении #1504881 писал(а):

как лучше решать задачу, вперёд или назад?

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

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

Если надо, могу прислать коллекцию карт для тестирования (что-то не вижу, как сюда в сообщение файл прикрепить).
Карты были вытащены из разных приложений Sokoban.
78 небольших карт из старого приложения под виндоус. Ещё много карт из линукс приложения sasquatch.
Ещё 10 карт покрупнее, которые было сложно считать. Вот последняя карта:

Используется синтаксис Text

  #####
 ## . ##
###$ $###
#  $ $  #
# . . . #
### * ###
 ## * ##
 ##$.$##
 ## . ##
 ##$.$##
 ## + ##
  #####
 

На рабочем компьютере не считалась. Вышло решить на сервере с 2Гб памяти.
В процессе работы память до 1.6Гб поднималась. Считало 25 минут. Количество состояний в памяти 36 408 246.

[zykov]

zykov в сообщении #1532200 писал(а):

Идея тут простая - просто поиск перебором вширь.

Вспомнил, там чуть сложнее было.
Не просто поиск вширь, а A*-поиск.
В качестве оценки была сумма расстояний (прямоугольных расстояний) от ящиков до ближайших к каждому из них конечных положений.
Но честно говоря, принципиально это ничего не меняло. Могло несколько ускорить поиск в самом конце.
Но основная масса поиска происходит по "запутанному лабиринту головоломки", где такая простая оценка роли не играет.

[zykov]

B@R5uk в сообщении #1518989 писал(а):

Брутфорсер решает задачу обратным ходом. Это позволяет получить лучший результат меньшей ценой без использования отсечения мёртвых позиций. Первый уровень оригинальной игры, разумеется, ему не под силу, но вот если его слегка урезать, то будет совсем другое дело:

Урезанный уровень посчитало за 13 секунд. Тоже 80 толканий ящиков.
Полный уровень посчитало за 105 секунд. Получилось 116 толканий ящиков.

Используется синтаксис Text

MAP 1
######################
#####   ##############
#####$  ##############
#####  $##############
###  $  $ ############
### # ### ############
#   # ### #######  ..#
# $  $             ..#
##### #### #@####  ..#
#####      ###########
######################
 

[zykov]

zykov в сообщении #1532200 писал(а):

В процессе работы память до 1.6Гб поднималась. Считало 25 минут. Количество состояний в памяти 36 408 246.

Нашел в архивах последнюю версию солвера.
Она эту карту номер 10 за 373 секунды решила. Так же 151 толкание ящиков.
Памяти меньше старой использует.
Количество состояний 11 188 099, память 234.7Мб. Максимальная длина очереди 729 804.

[B@R5uk]

zykov в сообщении #1532200 писал(а):

Правда тут есть баланс. Либо делать сложную проверку, тогда больше получится отсечь, но работать будет медленней.

Да, я тоже над этим долго ломал голову. В итоге пришёл к выводу, что лучше решать задом наперёд. Статистика показывает, что при решении обратным ходом мёртвых позиций возникает на порядок меньше, в связи с чем от проверки тупиковых состояний можно вообще отказаться. Получается два зайца одним выстрелом: решается быстро и рационально. Особенно, если сделать небольшой препроцессинг карты.

zykov в сообщении #1532200 писал(а):

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

Это, вообще говоря, не верно. Вне зависимости от того, какая цель оптимизации является первоочередной, для каждого пути в графе решений подсчитывается как число ходов, так и количество толканий. Потому что при сравнении двух путей используемая (в зависимости от цели) компараторная функция учитывает обе эти величины. Поэтому в обоих случаях состояния задачи представляются одинаково. Я писал об этом вкратце в первом посте. Если владеете инглишем, то на Sokoban-Wiki в статье Moves vs. Pushes подробно этот вопрос разбирается. В частности:

Цитата:

Note: a ratio of 1 to $\infty$ doesn't mean that the other value is completely irrelevant!
Exmaple:
A solution of 20 moves / 4 pushes is a better solution for a level than 20 moves / 6 pushes

zykov в сообщении #1532252 писал(а):

Нашел в архивах последнюю версию солвера.
Она эту карту номер 10 за 373 секунды решила.

Интересно было бы посмотреть код.

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

Основная проблема задачи в том, что пространство решений задачи невероятно велико и растёт практически экспоненциально с размером карты. При решении в лоб это требует пропорционального расхода памяти, и, вне зависимости от метода решения, — серьёзных временных затрат. Это связано с тем, что большинство алгоритмов обрабатывают всю карту целиком. Представим себе задачу с двумя комнатами. Для каждого положения ящиков одной комнате такие алгоритмы рассматривают каждое положение ящиков в другой комнате. В результате полное число $N$ рассматриваемых состояний задачи с $L$ ящиками будет равно сумме произведений количества состояний $P_k$ в первой комнате с $k$ ящиками на число состояний $Q_{L-k}$ во второй комнате с $L-k$ ящиками:

$$N=\sum_{k=0}^L P_kQ_{L-k}$$

Было бы здорово разделить решение задачи на такой карте на две части: отдельно для каждой комнаты, а потом их сложить. Тогда новое число рассматриваемых состояний будет значительно меньше:

$$\widetilde{N}=\sum_{k=0}^L \Bigl(P_k+Q_k\Bigr)$$

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

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

Ну и про автоматизацию разбиения задачи на комнаты я вообще молчу. Тут для начала можно вообще отдать это на откуп человеку.

[zykov]

B@R5uk в сообщении #1533329 писал(а):

Это, вообще говоря, не верно

Что именно не верно?

[B@R5uk]

zykov, подход, в котором для сравнения оптимальности двух конкурирующих решений используется только одна величина: либо число толканий, либо количество ходов. Решение, конечно, получится, но какая-либо его оптимальность, вообще говоря, не гарантирована.

[zykov]

Честно говоря не понял, что имеется ввиду (про гарантии).
Если оптимизировали количество ходов, то количество ходов и будет оптимально. Это гарантированно.
Если оптимизировали количество толканий, то количество толканий и будет оптимально.
Если оптимизировали (как по той ссылке предлагают) взвешенную сумму количества ходов и количества толканий, то эта величина будет оптимальна.

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

[B@R5uk]

zykov, вот представьте себе задачу, в которой среди прочих различных решений имеются следующие:

• 24 хода, 13 толканий
• 24 хода, 11 толканий
• 28 ходов, 9 толканий
• 26 ходов, 9 толканий

Задача оптимизируется приоритетно по количеству ходов. Если забыть подсчитывать и сравнивать число толканий, то программа может выдать решение из первого пункта, хотя оно не является оптимальным ни в каком смысле. Правильным будет решение из второго пункта, потому что не смотря на то, что число ходов то же самое, количество толканий во втором решении меньше. Ну и четвертое решение является ответом к задаче, когда приоритет оптимизации идёт по числу толканий. Количество ходов при этом тоже надо подсчитывать, иначе программа может выдать третье решение, которое как и первое не является оптимальным ни в каком смысле.

Разумеется, если задача стоит найти хоть какое-нибудь решение вообще, то можно действовать как угодно.

[zykov]

Теперь понятно.
Нет, как номер 1, так и номер 2 оптимальны в плане количества ходов (если нет решения с менее чем 24 ходами).
Аналогично 3 и 4 в плане толканий.

То что Вы описываете, это оптимальность в плане составной метрики, например "там где ходов меньше, там лучше; если ходов одинаково, то лучше там где толканий меньше".
Вполне можно оптимизировать и такую составную метрику. Только наверно придется делать полный перебор (ну или по крайней мере перебор с отсечением). Т.к. поиск в ширину (так же как и А-стар) для такого типа метрики не работает.
При поиске в ширину, как только нашли первый путь до цели, он сразу оптимален. Например имеет оптимальные 24 ходы. Но это вполне может быть первый номер с 13 толканиями. Если после этого хотите найти оптимальные 11 толканий для этих 24 ходов, то надо будет продолжить перебор, отсекая варианты с 25 ходами и более. Но надо будет перебрать все варианты с 24 ходами, чтобы гарантировать оптимальность.
Что может оказатся гораздо дольше, чем найти первое решение с 24 ходами.
(Грубо говоря, вместо того чтобы найти первую точку на поверхности сферы, придется обойти все точки на сфере.)

-- 01.10.2021, 15:48 --

B@R5uk в сообщении #1533329 писал(а):

Интересно было бы посмотреть код.

Что-то не вижу, как прикрепить файлы в сообщение на форуме. Может тут это не работает, как на других форумах.
Скиньте свой e-mail в ЛС, я туда архив с исходниками пошлю.
Только сразу предуперждаю, что код не причёсанный. Там много экспериментов было, что-то добавлялось, что-то стиралось. Результат может быть труден для понимания.

[B@R5uk]

zykov в сообщении #1533488 писал(а):

Т.к. поиск в ширину (так же как и А-стар) для такого типа метрики не работает.

Почему-же не работает? Вон я выше код приводил, там как раз поиск в ширину (исчерпывающий, так как я статистику считал) и он сделал с составной метрикой. С А-стар придётся повозиться, чтобы функцию оценки более-менее нормальную составить.

zykov в сообщении #1533488 писал(а):

При поиске в ширину, как только нашли первый путь до цели, он сразу оптимален.

В том-то и проблема, что нет. Тут надо шагнуть чуть-чуть дальше: останавливать работу программы не сразу, как найдено первое решение, а продолжить доставать из очереди с приоритетом элементы до тех пор, пока они дают то же самое число ходов/толканий в первой контрольной величине композитной метрики (и, соответственно, обновлять решение, если найдётся лучшее). Как только очередная приоритетная величина превысит оную у решения, можно останавливаться: оптимальное решение найдено. Продолжительность работы при этом увеличивается незначительно, на мой взгляд.

zykov в сообщении #1533488 писал(а):

Что-то не вижу, как прикрепить файлы в сообщение на форуме.

Посмотрите, как я в первом посте на этой странице делал: публиковал код на pastebin.com, а в сообщение вставлял ссылку на станичку с кодом. Форум поддерживает форматированный код с подсветкой, но число символов на сообщение ограничено величиной 20к, если мне память не изменяет. Рекомендую там зарегаться сначала: можно будет код править. Я этого сначала не сделал, потом пожалел.

[B@R5uk]

Нашёл забавный пример тупиковых состояний при решении обратным ходом. Первый уровень в наборе Microban:

Если в конечном положении (или в любом другом, где возможно) ящик у левой стенки отодвинуть вправо, то получившееся состояние никаким образом нельзя будет привести к начальному, то есть оно будет тупиковым. Вроде бы такие ситуации можно отсеять препроцессингом (хотя вопрос "Как?" на первый взгляд нетривиален), запретив отодвигание ящика от стенки, что, фактически, будет удалением нескольких рёбер (в этом случае двух) в графе правил движения агента. Тут главное — не удалить ничего лишнего.

-- 19.10.2021, 16:07 --

B@R5uk в сообщении #1533329 писал(а):

К сожалению, это пока всё на стадии размышлений.

От стадии размышлений пытаюсь переходить к практике. Первый шаг — попытаться построить полный (хотя бы в каком-то смысле) граф состояний задачи. (В противоположность дереву, которое получается, при использовании алгоритмов поиска в ширину и А-стар). Вопрос визуализации такого графа остаётся открытым...