2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 01:15 
Заслуженный участник


02/08/10
629
Сокобан - самая сложная задача на Тимусе: https://acm.timus.ru/problem.aspx?space=1&num=1589 . Там ТЛ - 5 сек, МЛ - 64 МБ, поле до 8х8 (то есть игровая часть до 6х6), очень мощные тесты и за все время ее лишь 10 человек сдало.

Можете попробовать решить. Правда, на джаве, я бы не советовал даже пытаться =)

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 01:46 


18/09/21
1676
Цитата:
This is a table of size $n \times m$ ($3 \leq  n$, $m \leq 8$).
Что-то 3 маловато...

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 02:01 
Заслуженный участник


02/08/10
629
zykov в сообщении #1535846 писал(а):
Цитата:
This is a table of size $n \times m$ ($3 \leq  n$, $m \leq 8$).
Что-то 3 маловато...

Ну формально говоря это ж корректное игровое поле 3x3 :)
Код:
###
#@#
###


-- Пт окт 22, 2021 02:09:11 --

zykov
Кстати, Попробуйте пожалуйста свой солвер на таком тесте:
Код:
########
#. .@  #
#$$$*$*#
#. $   #
#.$.* *#
# $.$  #
#. .*  #
########

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 07:21 


18/09/21
1676
MrDindows в сообщении #1535847 писал(а):
Попробуйте пожалуйста свой солвер на таком тесте
Не посчитало.
Тут слишком много ящиков - 13. Обычно где-то 10 ещё считает.
Чем больше ящиков, тем больше фактор ветвления.

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 09:43 
Заслуженный участник


02/08/10
629
zykov в сообщении #1535865 писал(а):
MrDindows в сообщении #1535847 писал(а):
Попробуйте пожалуйста свой солвер на таком тесте
Не посчитало.
Тут слишком много ящиков - 13. Обычно где-то 10 ещё считает.
Чем больше ящиков, тем больше фактор ветвления.


А мое решение менее чем за 10 секунд справляется. Но чтобы задачу сдать - надо не больше 5 сек, и тестовый сервер вероятно медленнее макбука, да и не факт, что этот тест является максимальным для моего решения в заданных ограничениях.

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

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 12:51 
Аватара пользователя


26/05/12
1534
приходит весна?
Когда-то благодаря Сокобану я и наткнулся на этот замечательный сайт Тимус-ру.

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 19:39 


18/09/21
1676
MrDindows в сообщении #1535881 писал(а):
А мое решение менее чем за 10 секунд справляется
А что оно делает? Тоже ищет минимальное количество ходов/толканий или ищет какое-то решение, которое может быть не оптимальным.

MrDindows в сообщении #1535881 писал(а):
тестовый сервер вероятно медленнее макбука
Обычно сервера быстрее ноутбуков.

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение22.10.2021, 20:14 
Заслуженный участник


02/08/10
629
zykov в сообщении #1535933 писал(а):
Обычно сервера быстрее ноутбуков.

Производительность эппловской техники умеет удивлять =)

zykov в сообщении #1535933 писал(а):
А что оно делает? Тоже ищет минимальное количество ходов/толканий или ищет какое-то решение, которое может быть не оптимальным.

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

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение23.10.2021, 22:42 


18/09/21
1676
MrDindows в сообщении #1535941 писал(а):
Там у меня разные эвристики есть
Да, можно попробовать эвристик накидать. Но хотелось бы найти какой-то более фундаментальный подход позволяющий искать более-менее хорошие решения. Пусть не оптимальные, но искать гораздо быстрее, чем оптимальные.
MrDindows в сообщении #1535941 писал(а):
сперва запускается поиск в ширину, до определенного числа состояний. После этого, из самых перспективных запускаются поиски в глубину
Тут можно посоветовать поиск в ширину не только вперед, но ещё и назад из конечного состояния провести. Тогда эвристический поиск в глубину будет иметь больше шансов выйти на конечное состояние (когда он наткнётся на одно из состояний полученных поиском назад).

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение24.10.2021, 08:25 


18/09/21
1676
zykov в сообщении #1535865 писал(а):
Не посчитало.
Нет, всё таки посчитало.
Была техническая проблема. Раньше я это собирал в gcc под linux, а сейчас собрал в gcc mingw64 под windows (Win8.1 64bit). Оказалось, что под windows используется data model LLP64, а под linux это было LP64. Из-за этого 'long int' оказался 32 бита, хотя раньше был 64 бита. Вот программа и вылетала на большой карте из-за переполнения 32 битного целого.

Вобщем считает она 10ч 40м. Основное хранилище 205.8М состояний (4.5Гб), очередь в максимуме до 35.8М состояний.
Минимально количество толканий ящиков 73.
MrDindows
А у Вас сколько толканий выдало?

-- 24.10.2021, 08:34 --

MrDindows в сообщении #1535847 писал(а):
Кстати, Попробуйте пожалуйста свой солвер на таком тесте:
Код:
########
#. .@  #
#$$$*$*#
#. $   #
#.$.* *#
# $.$  #
#. .*  #
########
Решение (по 1 толканию ящика за раз):

(Оффтоп)

Код:
Steps: 0  Pushes: 0 Cost: 11
########
#. .@  #
#$$$*$*#
#. $   #
#.$.* *#
# $.$  #
#. .*  #
########

Steps: 1  Pushes: 1 Cost: 11
########
#. .   #
#$$$+$*#
#. $$  #
#.$.* *#
# $.$  #
#. .*  #
########

Steps: 5  Pushes: 2 Cost: 11
########
#. .   #
#$@$.$*#
#.$$$  #
#.$.* *#
# $.$  #
#. .*  #
########

Steps: 10 Pushes: 3 Cost: 13
########
#. .   #
#$$@.$*#
#.$$$  #
#.$.* *#
# $.$  #
#. .*  #
########

Steps: 11 Pushes: 4 Cost: 13
########
#. .   #
#$$ .$*#
#.$@$  #
#.$** *#
# $.$  #
#. .*  #
########

Steps: 12 Pushes: 5 Cost: 16
########
#. .   #
#$$ .$*#
#.$ $  #
#.$+* *#
# $*$  #
#. .*  #
########

Steps: 13 Pushes: 6 Cost: 17
########
#. .   #
#$$ .$*#
#.$ $  #
#.$.+$*#
# $*$  #
#. .*  #
########

Steps: 14 Pushes: 7 Cost: 19
########
#. .   #
#$$ *$*#
#.$ @  #
#.$..$*#
# $*$  #
#. .*  #
########

Steps: 17 Pushes: 8 Cost: 21
########
#. .   #
#$$ *$*#
#.$    #
#.$..$+#
# $*$ $#
#. .*  #
########

Steps: 18 Pushes: 9 Cost: 22
########
#. .   #
#$$ *$*#
#.$    #
#.$.*@.#
# $*$ $#
#. .*  #
########

Steps: 21 Pushes: 10  Cost: 22
########
#. .   #
#$$ *$*#
#.$    #
#.$.* .#
# $*$ $#
#. *+  #
########

Steps: 33 Pushes: 11  Cost: 22
########
#. .   #
#$$ *$+#
#.$   $#
#.$.* .#
# $*$ $#
#. *.  #
########

Steps: 37 Pushes: 12  Cost: 24
########
#. .   #
#$$ +$.#
#.$ $ $#
#.$.* .#
# $*$ $#
#. *.  #
########

Steps: 42 Pushes: 13  Cost: 25
########
#. .   #
#$$ *@.#
#.$ $ $#
#.$.* .#
# $*$ $#
#. *.  #
########

Steps: 46 Pushes: 14  Cost: 25
########
#. .   #
#$$ * *#
#.$ $ @#
#.$.* .#
# $*$ $#
#. *.  #
########

Steps: 52 Pushes: 15  Cost: 27
########
#. .   #
#$$ * *#
#.$ $  #
#.$.* .#
# $*$ $#
#.$+.  #
########

Steps: 53 Pushes: 16  Cost: 28
########
#. .   #
#$$ * *#
#.$ $  #
#.$** .#
# $+$ $#
#.$..  #
########

Steps: 54 Pushes: 17  Cost: 29
########
#. .   #
#$$ * *#
#.$$$  #
#.$+* .#
# $.$ $#
#.$..  #
########

Steps: 55 Pushes: 18  Cost: 30
########
#. .   #
#$$$* *#
#.$@$  #
#.$.* .#
# $.$ $#
#.$..  #
########

Steps: 56 Pushes: 19  Cost: 31
########
#. .   #
#$$$* *#
#.$ @$ #
#.$.* .#
# $.$ $#
#.$..  #
########

Steps: 60 Pushes: 20  Cost: 33
########
#. .   #
#$$$* *#
#.$  $ #
#.$.* .#
# $.@$$#
#.$..  #
########

Steps: 65 Pushes: 21  Cost: 35
########
#. .   #
#$$$* *#
#.$  $ #
#.$.+ .#
# $.$$$#
#.$..  #
########

Steps: 69 Pushes: 22  Cost: 35
########
#. .   #
#$$$* *#
#.$ $@ #
#.$.. .#
# $.$$$#
#.$..  #
########

Steps: 78 Pushes: 23  Cost: 35
########
#. .   #
#$$$* *#
#.$ $  #
#.$.. *#
# $.$$@#
#.$..  #
########

Steps: 85 Pushes: 24  Cost: 35
########
#. .   #
#$$$* *#
#.$ $  #
#*@.. *#
# $.$$ #
#.$..  #
########

Steps: 94 Pushes: 25  Cost: 36
########
#. .   #
#$$@* *#
#.$$$  #
#* .. *#
# $.$$ #
#.$..  #
########

Steps: 95 Pushes: 26  Cost: 38
########
#. .   #
#$$ +$*#
#.$$$  #
#* .. *#
# $.$$ #
#.$..  #
########

Steps: 96 Pushes: 27  Cost: 38
########
#. .   #
#$$ .$*#
#.$$@  #
#* .* *#
# $.$$ #
#.$..  #
########

Steps: 102  Pushes: 28  Cost: 39
########
#. .   #
#@$ .$*#
#*$$   #
#* .* *#
# $.$$ #
#.$..  #
########

Steps: 103  Pushes: 29  Cost: 39
########
#. .   #
# @$.$*#
#*$$   #
#* .* *#
# $.$$ #
#.$..  #
########

Steps: 111  Pushes: 30  Cost: 39
########
#. .   #
#  $.$*#
#*$$   #
#* .* *#
# $.$@ #
#.$..$ #
########

Steps: 112  Pushes: 31  Cost: 40
########
#. .   #
#  $.$*#
#*$$   #
#* .* *#
# $*@  #
#.$..$ #
########

Steps: 113  Pushes: 32  Cost: 42
########
#. .   #
#  $.$*#
#*$$$  #
#* .+ *#
# $*   #
#.$..$ #
########

Steps: 116  Pushes: 33  Cost: 43
########
#. .   #
# $$.$*#
#*@$$  #
#* .. *#
# $*   #
#.$..$ #
########

Steps: 117  Pushes: 34  Cost: 43
########
#.$.   #
# @$.$*#
#* $$  #
#* .. *#
# $*   #
#.$..$ #
########

Steps: 118  Pushes: 35  Cost: 45
########
#.$.   #
#  @*$*#
#* $$  #
#* .. *#
# $*   #
#.$..$ #
########

Steps: 122  Pushes: 36  Cost: 45
########
#.$.   #
#   *@*#
#* $$$ #
#* .. *#
# $*   #
#.$..$ #
########

Steps: 135  Pushes: 37  Cost: 45
########
#.$.   #
#   * *#
#* $$$ #
#* .. *#
# $*   #
#*@..$ #
########

Steps: 149  Pushes: 38  Cost: 45
########
#.$.   #
#   * *#
#* $$@ #
#* ..$*#
# $*   #
#* ..$ #
########

Steps: 155  Pushes: 39  Cost: 45
########
#.$.   #
#   * *#
#* @$  #
#* *.$*#
# $*   #
#* ..$ #
########

Steps: 162  Pushes: 40  Cost: 47
########
#.$.   #
#   * *#
#* $@  #
#* *.$*#
# $*   #
#* ..$ #
########

Steps: 168  Pushes: 41  Cost: 48
########
#.$.   #
#   * *#
#* $   #
#*$*.$*#
# @*   #
#* ..$ #
########

Steps: 169  Pushes: 42  Cost: 50
########
#.$.   #
#   * *#
#*$$   #
#*@*.$*#
#  *   #
#* ..$ #
########

Steps: 170  Pushes: 43  Cost: 50
########
#.$.   #
#   * *#
#*$$   #
#* +*$*#
#  *   #
#* ..$ #
########

Steps: 171  Pushes: 44  Cost: 51
########
#.$.   #
#   * *#
#*$$   #
#* .*$*#
#  +   #
#* *.$ #
########

Steps: 176  Pushes: 45  Cost: 51
########
#.$.   #
#   * *#
#*$$   #
#* .*$*#
#  .   #
#* **@ #
########

Steps: 181  Pushes: 46  Cost: 52
########
#.$.   #
#  $* *#
#*$@   #
#* .*$*#
#  .   #
#* **  #
########

Steps: 188  Pushes: 47  Cost: 53
########
#.$.   #
#  @* *#
#*$$   #
#* .*$*#
#  .   #
#* **  #
########

Steps: 190  Pushes: 48  Cost: 53
########
#.$.   #
#   * *#
#*@$   #
#*$.*$*#
#  .   #
#* **  #
########

Steps: 199  Pushes: 49  Cost: 54
########
#.$.   #
#   * *#
#* $   #
#*$.+$*#
#  .$  #
#* **  #
########

Steps: 201  Pushes: 50  Cost: 55
########
#.$.   #
#  $* *#
#* @   #
#*$..$*#
#  .$  #
#* **  #
########

Steps: 205  Pushes: 51  Cost: 57
########
#.$.   #
#  $* *#
#*     #
#*$..$+#
#  .$ $#
#* **  #
########

Steps: 206  Pushes: 52  Cost: 57
########
#.$.   #
#  $* *#
#*     #
#*$.*@.#
#  .$ $#
#* **  #
########

Steps: 214  Pushes: 53  Cost: 58
########
#.@*   #
#  $* *#
#*     #
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 215  Pushes: 54  Cost: 59
########
#. +$  #
#  $* *#
#*     #
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 225  Pushes: 55  Cost: 61
########
#. .$  #
#  $* +#
#*    $#
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 234  Pushes: 56  Cost: 63
########
#. .@$ #
#  $* .#
#*    $#
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 235  Pushes: 57  Cost: 65
########
#. . $ #
#  $+ .#
#*  $ $#
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 236  Pushes: 58  Cost: 67
########
#. . $ #
# $@. .#
#*  $ $#
#*$.* .#
#  .$ $#
#* **  #
########

Steps: 241  Pushes: 59  Cost: 69
########
#. . $ #
# $ . .#
#*$ $ $#
#*@.* .#
#  .$ $#
#* **  #
########

Steps: 250  Pushes: 60  Cost: 69
########
#. . $ #
# $ . .#
#*$ $ $#
#* .* .#
#  *@ $#
#* **  #
########

Steps: 261  Pushes: 61  Cost: 69
########
#. . $ #
# @$. .#
#*$ $ $#
#* .* .#
#  *  $#
#* **  #
########

Steps: 268  Pushes: 62  Cost: 70
########
#. . $ #
#  $. .#
#*$$@ $#
#* .* .#
#  *  $#
#* **  #
########

Steps: 273  Pushes: 63  Cost: 72
########
#. . $ #
#  $. .#
#*$$$ $#
#* .+ .#
#  *  $#
#* **  #
########

Steps: 276  Pushes: 64  Cost: 73
########
#. . $ #
# $$. .#
#*@$$ $#
#* .. .#
#  *  $#
#* **  #
########

Steps: 277  Pushes: 65  Cost: 73
########
#.$. $ #
# @$. .#
#* $$ $#
#* .. .#
#  *  $#
#* **  #
########

Steps: 286  Pushes: 66  Cost: 73
########
#.$. $ #
#  $. .#
#* $@ $#
#* .* .#
#  *  $#
#* **  #
########

Steps: 290  Pushes: 67  Cost: 73
########
#*@. $ #
#  $. .#
#* $  $#
#* .* .#
#  *  $#
#* **  #
########

Steps: 292  Pushes: 68  Cost: 73
########
#* . $ #
#  @* .#
#* $  $#
#* .* .#
#  *  $#
#* **  #
########

Steps: 293  Pushes: 69  Cost: 73
########
#* . $ #
#   * .#
#* @  $#
#* ** .#
#  *  $#
#* **  #
########

Steps: 299  Pushes: 70  Cost: 73
########
#* .$@ #
#   * .#
#*    $#
#* ** .#
#  *  $#
#* **  #
########

Steps: 304  Pushes: 71  Cost: 73
########
#* .$  #
#   * *#
#*    @#
#* ** .#
#  *  $#
#* **  #
########

Steps: 310  Pushes: 72  Cost: 73
########
#* .$  #
#   * *#
#*     #
#* ** *#
#  *  @#
#* **  #
########

Steps: 316  Pushes: 73  Cost: 73
########
#* *@  #
#   * *#
#*     #
#* ** *#
#  *   #
#* **  #
########


-- 24.10.2021, 09:01 --

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

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение24.10.2021, 13:35 
Заслуженный участник


02/08/10
629
zykov в сообщении #1536158 писал(а):
Вобщем считает она 10ч 40м. Основное хранилище 205.8М состояний (4.5Гб), очередь в максимуме до 35.8М состояний.
Минимально количество толканий ящиков 73.
MrDindows
А у Вас сколько толканий выдало?


Быстрее всего находится решение с 350 толканиями. Если отключить дфс, то находит такое же решение, как и у вас, с 73 толканиями, но чуть быстрее, за 12 секунд :)

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение10.11.2021, 21:21 
Аватара пользователя


26/05/12
1534
приходит весна?
Запилил таки первую работоспособную версию программы, которая честно строит граф пространства состояний задачи (у себя в памяти во всяком случае). Выдаёт она мне портянки такого вот вида:

(Оффтоп)

Код:
..\SokWhole.txt  #7
#####
#   ##
# .* #
#  $@#
#  ###
#### 

Active cells:
#####
#...##
#.,,.#
#.,,.#
#..###
#### 

Initial state:
1-3~10
#####
#...##
#..$.#
#..$@#
#..###
#### 

=================
State Space:
-----------------

Final state
0-1~2
#####
#...##
#.$$.#
#.@..#
#..###
#### 
In: 1-2~12 >--(U)--> 0-1~2
Out: 0-1~2 >--(luur)--> 0-1~5
Out: 0-1~2 >--(luurr)--> 0-1~6

0-1~5
#####
#.@.##
#.$$.#
#....#
#..###
#### 
In: 0-1~2 >--(luur)--> 0-1~5
Out: 0-1~5 >--(D)--> 1-2~0

0-1~6
#####
#..@##
#.$$.#
#....#
#..###
#### 
In: 0-1~2 >--(luurr)--> 0-1~6
Out: 0-1~6 >--(D)--> 0-3~1

0-2~1
#####
#...##
#.$@.#
#.$..#
#..###
#### 
In: 1-2~8 >--(L)--> 0-2~1
Out: 0-2~1 >--(ulld)--> 0-2~7
Out: 0-2~1 >--(ulldd)--> 0-2~9

0-2~3
#####
#...##
#.$..#
#.$@.#
#..###
#### 
In: 0-3~10 >--(L)--> 0-2~3
Out: 0-2~3 >--(uulld)--> 0-2~7
Out: 0-2~3 >--(uulldd)--> 0-2~9

0-2~7
#####
#...##
#@$..#
#.$..#
#..###
#### 
In: 0-2~1 >--(ulld)--> 0-2~7
In: 0-2~3 >--(uulld)--> 0-2~7
Out: 0-2~7 >--(R)--> 1-2~0

0-2~9
#####
#...##
#.$..#
#@$..#
#..###
#### 
In: 0-2~1 >--(ulldd)--> 0-2~9
In: 0-2~3 >--(uulldd)--> 0-2~9
Out: 0-2~9 >--(R)--> 0-3~2

1-2~0
#####
#...##
#.@$.#
#.$..#
#..###
#### 
In: 0-1~5 >--(D)--> 1-2~0
In: 0-2~7 >--(R)--> 1-2~0
Out: 1-2~0 >--(ur)--> 1-2~6
Out: 1-2~0 >--(ld)--> 1-2~9
Out: 1-2~0 >--(lddr)--> 1-2~12

1-2~3
#####
#...##
#..$.#
#.$@.#
#..###
#### 
In: 1-3~10 >--(L)--> 1-2~3
Out: 1-2~3 >--(ru)--> 1-2~8

1-2~6
#####
#..@##
#..$.#
#.$..#
#..###
#### 
In: 1-2~0 >--(ur)--> 1-2~6
Out: 1-2~6 >--(D)--> 2-3~1

1-2~8
#####
#...##
#..$@#
#.$..#
#..###
#### 
In: 1-2~3 >--(ru)--> 1-2~8
Out: 1-2~8 >--(L)--> 0-2~1

1-2~9
#####
#...##
#..$.#
#@$..#
#..###
#### 
In: 1-2~0 >--(ld)--> 1-2~9

1-2~12
#####
#...##
#..$.#
#.$..#
#.@###
#### 
In: 1-2~0 >--(lddr)--> 1-2~12
Out: 1-2~12 >--(U)--> 0-1~2

0-3~1
#####
#...##
#.$@.#
#..$.#
#..###
#### 
In: 0-1~6 >--(D)--> 0-3~1
In: 1-3~8 >--(L)--> 0-3~1
Out: 0-3~1 >--(ul)--> 0-3~5
Out: 0-3~1 >--(ulld)--> 0-3~7
Out: 0-3~1 >--(rd)--> 0-3~10

0-3~2
#####
#...##
#.$..#
#.@$.#
#..###
#### 
In: 0-2~9 >--(R)--> 0-3~2
In: 2-3~12 >--(U)--> 0-3~2
Out: 0-3~2 >--(luur)--> 0-3~5
Out: 0-3~2 >--(lu)--> 0-3~7
Out: 0-3~2 >--(luurrdrd)--> 0-3~10

0-3~5
#####
#.@.##
#.$..#
#..$.#
#..###
#### 
In: 0-3~1 >--(ul)--> 0-3~5
In: 0-3~2 >--(luur)--> 0-3~5
Out: 0-3~5 >--(D)--> 2-3~0

0-3~7
#####
#...##
#@$..#
#..$.#
#..###
#### 
In: 0-3~1 >--(ulld)--> 0-3~7
In: 0-3~2 >--(lu)--> 0-3~7

0-3~10
#####
#...##
#.$..#
#..$@#
#..###
#### 
In: 0-3~1 >--(rd)--> 0-3~10
In: 0-3~2 >--(luurrdrd)--> 0-3~10
Out: 0-3~10 >--(L)--> 0-2~3

1-3~8
#####
#...##
#..$@#
#..$.#
#..###
#### 
In: 1-3~10 >--(u)--> 1-3~8
Out: 1-3~8 >--(L)--> 0-3~1

Initial state
1-3~10
#####
#...##
#..$.#
#..$@#
#..###
#### 
Out: 1-3~10 >--(L)--> 1-2~3
Out: 1-3~10 >--(u)--> 1-3~8

2-3~0
#####
#...##
#.@..#
#.$$.#
#..###
#### 
In: 0-3~5 >--(D)--> 2-3~0
Out: 2-3~0 >--(lddr)--> 2-3~12

2-3~1
#####
#...##
#..@.#
#.$$.#
#..###
#### 
In: 1-2~6 >--(D)--> 2-3~1
Out: 2-3~1 >--(llddr)--> 2-3~12

2-3~12
#####
#...##
#....#
#.$$.#
#.@###
#### 
In: 2-3~0 >--(lddr)--> 2-3~12
In: 2-3~1 >--(llddr)--> 2-3~12
Out: 2-3~12 >--(U)--> 0-3~2

-----------------
State Space (end)
=================

Size of State Space: 23 element(s)

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

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

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

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

Разумеется, не для каждого положения агента в области связности нужно создавать вершину графа. И не для каждой пары вершин — ребро, даже если оно и возможно. Над тем что же оставить, а что выкинуть я так долго и ломал голову. В итоге решил сделать следующим образом. Вершины графа у меня сопоставляются тем состояниям, которые непосредственно получаются сдвигом какого-то ящика; а так же тем, из которых такой сдвиг возможен. Состояния первого рода у меня в программе обозваны "приходящими", а второго — "отбывающими" (по очевидной причине, если учесть, что вся область связности у меня обрабатывается в один присест). Вершины графа, состояния которых отличаются положением ящиков, могут быть связаны направленным ребром, если одно состояние получается из другого сдвигом единственного ящика единственным ходом агента. Состояния же внутри области связности связываются рёбрами, которым может соответствовать один и более ходов агента (без смещения ящиков). При этом, вообще говоря, каждая вершина, соответствующая области связности, может быть соединена двумя рёбрами (в оба направления) с каждой вершиной той же области связности. Однако, для решения задачи интерес представляют только те рёбра, которые идут из "приходящих" вершин в "отбывающие". Чтобы не загромождать память лишними объектами, я только такие рёбра в свой граф и добавлял.

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

Процесс рождения программы продолжается...

Граф в памяти представляется следующими тремя классами. Не знаю, на сколько это оптимально.
Используется синтаксис Java
public class StateSpace {
   
    private GraphNode initialNode;
    private Set <GraphNode> finalNodes;
    private Map <State, GraphNode> statesAndNodes;
   
    public StateSpace () {
        initialNode    = null;
        finalNodes     = new TreeSet <> ();
        statesAndNodes = new TreeMap <> ();
    }
    //...
}

Используется синтаксис Java
public class GraphNode implements Comparable <GraphNode> {
   
    private State state;
    private Set <GraphArc> ingoingArcs, outgoingArcs;
    private Object value;
   
    public GraphNode (State state) {
        this .state  = state;
        ingoingArcs  = new TreeSet <> ();
        outgoingArcs = new TreeSet <> ();
        value = null;
    }
    //...
}

Используется синтаксис Java
public class GraphArc implements Comparable <GraphArc> {
   
    private GraphNode sourceNode, targetNode;
    private byte [] movesData;
   
    public GraphArc (GraphNode sourceNode, GraphNode targetNode, byte [] movesData) {
        if (sourceNode .equals (targetNode)) {
            throw new IllegalArgumentException ("\n\nLoop arc.\n\n");
        }
        this .sourceNode = sourceNode;
        this .targetNode = targetNode;
        this .movesData  = movesData;
    }
    //...
}

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение11.11.2021, 10:38 
Аватара пользователя


26/05/12
1534
приходит весна?
Оказывается, существует замечательный формат файлов для хранения графов, называется GraphML. Я даже нашёл онлайн-редактор, который позволяет импортировать/редактировать/экспортировать файлы в этом формате. К сожалению, возможности этого онлайн-редактора по-настоящему убогие, он не полностью следует спецификации формата, и, что самое обидное, не имеет возможности автоматически красиво разместить вершины графа на плоскости по нажатию кнопки с небольшим числом настроек (таких, например, как плотность размещения). Но код, генерирующий код GraphML-файла я пишу сам, и, проковырявшись с кружочками часа два, для портянки выше у меня получилась вот такая красивая картинка:

(Оффтоп)

Изображение

Исходный код для неё был:
код: [ скачать ] [ спрятать ]
Используется синтаксис XML
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns">
  <graph id="graph" edgedefault="directed">
    <node id="0-1~2" text="0-1~2"/>
    <edge source="0-1~2" target="0-1~5" text="luur" isDirect="true"/>
    <edge source="0-1~2" target="0-1~6" text="luurr" isDirect="true"/>
    <node id="0-1~5" text="0-1~5"/>
    <edge source="0-1~5" target="1-2~0" text="D" isDirect="true"/>
    <node id="0-1~6" text="0-1~6"/>
    <edge source="0-1~6" target="0-3~1" text="D" isDirect="true"/>
    <node id="0-2~1" text="0-2~1"/>
    <edge source="0-2~1" target="0-2~7" text="ulld" isDirect="true"/>
    <edge source="0-2~1" target="0-2~9" text="ulldd" isDirect="true"/>
    <node id="0-2~3" text="0-2~3"/>
    <edge source="0-2~3" target="0-2~7" text="uulld" isDirect="true"/>
    <edge source="0-2~3" target="0-2~9" text="uulldd" isDirect="true"/>
    <node id="0-2~7" text="0-2~7"/>
    <edge source="0-2~7" target="1-2~0" text="R" isDirect="true"/>
    <node id="0-2~9" text="0-2~9"/>
    <edge source="0-2~9" target="0-3~2" text="R" isDirect="true"/>
    <node id="1-2~0" text="1-2~0"/>
    <edge source="1-2~0" target="1-2~6" text="ur" isDirect="true"/>
    <edge source="1-2~0" target="1-2~9" text="ld" isDirect="true"/>
    <edge source="1-2~0" target="1-2~12" text="lddr" isDirect="true"/>
    <node id="1-2~3" text="1-2~3"/>
    <edge source="1-2~3" target="1-2~8" text="ru" isDirect="true"/>
    <node id="1-2~6" text="1-2~6"/>
    <edge source="1-2~6" target="2-3~1" text="D" isDirect="true"/>
    <node id="1-2~8" text="1-2~8"/>
    <edge source="1-2~8" target="0-2~1" text="L" isDirect="true"/>
    <node id="1-2~9" text="1-2~9"/>
    <node id="1-2~12" text="1-2~12"/>
    <edge source="1-2~12" target="0-1~2" text="U" isDirect="true"/>
    <node id="0-3~1" text="0-3~1"/>
    <edge source="0-3~1" target="0-3~5" text="ul" isDirect="true"/>
    <edge source="0-3~1" target="0-3~7" text="ulld" isDirect="true"/>
    <edge source="0-3~1" target="0-3~10" text="rd" isDirect="true"/>
    <node id="0-3~2" text="0-3~2"/>
    <edge source="0-3~2" target="0-3~5" text="luur" isDirect="true"/>
    <edge source="0-3~2" target="0-3~7" text="lu" isDirect="true"/>
    <edge source="0-3~2" target="0-3~10" text="luurrdrd" isDirect="true"/>
    <node id="0-3~5" text="0-3~5"/>
    <edge source="0-3~5" target="2-3~0" text="D" isDirect="true"/>
    <node id="0-3~7" text="0-3~7"/>
    <node id="0-3~10" text="0-3~10"/>
    <edge source="0-3~10" target="0-2~3" text="L" isDirect="true"/>
    <node id="1-3~8" text="1-3~8"/>
    <edge source="1-3~8" target="0-3~1" text="L" isDirect="true"/>
    <node id="1-3~10" text="1-3~10"/>
    <edge source="1-3~10" target="1-2~3" text="L" isDirect="true"/>
    <edge source="1-3~10" target="1-3~8" text="u" isDirect="true"/>
    <node id="2-3~0" text="2-3~0"/>
    <edge source="2-3~0" target="2-3~12" text="lddr" isDirect="true"/>
    <node id="2-3~1" text="2-3~1"/>
    <edge source="2-3~1" target="2-3~12" text="llddr" isDirect="true"/>
    <node id="2-3~12" text="2-3~12"/>
    <edge source="2-3~12" target="0-3~2" text="U" isDirect="true"/>
  </graph>
</graphml>

В красный цвет я перекрасил вершину, соответствующую начальному состоянию задачи, в зелёный — конечную. Конечных как правило бывает несколько, но конкретно в этом пазле оказалась только одна. Цифрами закодированы состояния: первые две указывают на каких ячейках находятся ящики, последняя (после тильды) — агент. Нумерация ячеек следующая:
Изображение
Надо бы перейти к цифро-буквенной нумерации ячеек, как на шахматной доске, так будет и проще и нагляднее (но не очень компактно). На графе видны два "хвоста": состояния 1-2~9 и 0-3~7, которые подлежат удалению. Тупиковых состояний обратным ходом в этом пазле не получилось.

Забавно, как хорошо на графе видны топологически различные пути решения головоломки, а так же всевозможные циклы. Например, цикл luurrdrdLuullddR, начинающийся в состоянии 0-3~2, гоняет ящик туда-сюда между ячейками 2 и 3.

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение11.11.2021, 23:04 


12/07/15
2907
г. Чехов
Mihaylo в сообщении #1505958 писал(а):
Предлагаю так:
1. Сначала разработать стратегию накрытия точек ящиками. Разработка стратегии сводится к поиску всех возможных размещений ящиков по точкам $A=\frac{n!}{(n-r)!}$, где $n$ - число ящиков, $r$ - число точек. Здесь гораздо меньше вариантов для перебора, чем вариантов траекторий.
В рамках каждой из стратегий:
2. Разработать тактику сдвигания ненужных ящиков, чтобы не мешались.
3. Разработать тактику движения ящиков на точки.
4. Выстраивать тактику движения персонажа (траектории) для реализации тактик п.2 и п.3.
5. Если тактики п.2-4 полностью собрались, значит стратегия реализуема.
В рамках общей стратегии:
6. Отобрать оптимальную стратегию.

Из этого множества соответствий "ящики-точки" можно легко отбросить недопустимые соответствия путем доказательства, а также, наоборот, доказать, что накрыть точку может только один из ящиков. Те же мертвые ящики легко отбрасываются из рассмотрения. Нужно стараться сокращать стратегические решения из п.1 в первую очередь.

А вот из этого что-то реализовано?

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение11.11.2021, 23:14 


18/09/21
1676
B@R5uk
Честно говоря потерял нить мысли. К какой цели сейчас идёте?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 62 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group