Запилил таки первую работоспособную версию программы, которая честно строит граф пространства состояний задачи (у себя в памяти во всяком случае). Выдаёт она мне портянки такого вот вида:
(Оффтоп)
Код:
..\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)
Увидеть граф (не говоря уж заметить какие-либо его особенности) по такому выводу невозможно. Скоро остро встанет вопрос визуализации всего этого дела. Но пока надо ещё доделать построение графа, в частности, удалить из него все лишние вершины, соответствующие тупиковым состояниям, которые получаются при решении обратным ходом, а так же удалить все хвосты, которые уже и так есть, и ещё появятся при удалении тупиковых состояний, и добавить комплексную метрику к состояниям. Правда пока не решил: изменять ли расстояние с конца к началу или же наоборот.
Вообще, тяжкий был процесс рождения этой программы. Мало того, что я с графами никогда толком и не работал (узлы, ориентированные рёбра, представление всего этого дела в памяти), так я ещё толком не понимал, что я хотел сделать, что вообще можно сделать и что из этого всего будет рационально. На счёт второго и третьего у меня и сейчас остались сомнения.
Если взглянуть издалека, самый полный честный граф пространства решений будет иметь в качестве вершин все возможные (даже тупиковые, недостижимые ни прямым, ни обратным ходом) состояния, которые можно получить комбинаторным образом, а в качестве рёбер — все разрешённые ходы, соответствующие перемещению агента на одну клетку. Такой граф может даже содержать несвязанные подграфы. Применительно к решению конкретной задачи, он слишком велик и не представляет практического интереса. Однако, полный граф может быть полезен, если стоит задача программного построения новых пазлов, когда заданы только карта уровня и количество ящиков на нём (без указания начального и конечного положения ящиков и агента). Поиск двух максимально удалённых (в какой-либо метрике) вершин такого графа и будет давать новый пазл. Поиск вершин, удалённых не менее заданной величины, будет давать целый набор различных пазлов в одном и том же лабиринте.
При решении же конкретной задачи граф пространства решений желательно организовать таким образом, чтобы на столько мал, на сколько практически возможно. Наиболее компактным из известных мне кажется такой подход: указание положения ящиков и области связности ячеек, достижимых агентом без сдвигания ящиков. Этот подход, возможно, даже упоминался в теме выше. Такой вариант представления состояния хорош, только если необходимо найти хоть какое-то решение, или же какое-то с минимальным числом толканий (без учёта простых ходов агента). Если же нужно
решение, оптимальное в полноценной метрике (как я объяснял
ранее в теме), то такого представления мало, нужна ещё информация о положении агента.
Разумеется,
не для каждого положения агента в области связности нужно создавать вершину графа. И не для каждой пары вершин — ребро, даже если оно и возможно. Над тем что же оставить, а что выкинуть я так долго и ломал голову. В итоге решил сделать следующим образом. Вершины графа у меня сопоставляются тем состояниям, которые
непосредственно получаются сдвигом какого-то ящика; а так же тем,
из которых такой
сдвиг возможен. Состояния первого рода у меня в программе обозваны "приходящими", а второго — "отбывающими" (по очевидной причине, если учесть, что вся область связности у меня обрабатывается в один присест). Вершины графа, состояния которых отличаются положением ящиков, могут быть связаны направленным ребром, если одно состояние получается из другого сдвигом единственного ящика единственным ходом агента. Состояния же внутри области связности связываются рёбрами, которым может соответствовать один и более ходов агента (без смещения ящиков). При этом, вообще говоря, каждая вершина, соответствующая области связности, может быть соединена двумя рёбрами (в оба направления) с каждой вершиной той же области связности. Однако, для решения задачи интерес представляют только те рёбра, которые идут из "приходящих" вершин в "отбывающие". Чтобы не загромождать память лишними объектами, я только такие рёбра в свой граф и добавлял.
Таким образом у меня достигается некий компромисс между производительностью и полнотой информации. При этом вершинам графа соответствуют состояния, задаваемые положением ящиков и агента, а рёбрам — последовательности ходов агента, которые переводят связанные ребром состояния из одного в другое.
Процесс рождения программы продолжается...
Граф в памяти представляется следующими тремя классами. Не знаю, на сколько это оптимально.
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 <> ();
}
//...
}
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;
}
//...
}
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;
}
//...
}
(
, 
).
, где 
- число ящиков, 
- число точек. Здесь гораздо меньше вариантов для перебора, чем вариантов траекторий.