Ответ в теме: Задача "Автомобильный гараж"

      Комментарии к записи Ответ в теме: Задача "Автомобильный гараж" отключены
#2643

StrKllr
Участник

Здравствуйте еще раз.

Сейчас программа выглядит так

:- dynamic states/2.

/*nodes (боксы гаража)*/
node(0).
node(1).
node(2).
node(3).
node(4).
node(5).
node(6).
node(7).
node(8).
node(9).
node(10).
node(11).

/* edges (проезды между боксами) */
edge(0,1).
edge(1,0).
edge(1,2).
edge(2,1).
edge(1,4).
edge(4,1).
edge(2,3).
edge(3,2).
edge(4,5).
edge(5,4).
edge(5,6).
edge(6,5).
edge(5,7).
edge(7,5).
edge(7,9).
edge(9,7).
edge(8,9).
edge(9,8).
edge(9,10).
edge(10,9).
edge(10,11).
edge(11,10).

/* поиск в глубину (проверяет, есть ли путь между вершинами) */
dfs(A, B, _, [(A, B)], State):-
  edge(A, B),nth0(B,State,Spot), Spot == 0,!.

dfs(A, B, VN, [(A, X)|TR], State):-
  edge(A, X),nth0(X,State,Spot),Spot == 0, not(member(X, VN)),
  dfs(X, B, [A|VN], TR, State).

swapCar(As,I,J,Cs) :-
   same_length(As,Cs),
   append(BeforeI,[AtI|PastI],As),
   append(BeforeI,[AtJ|PastI],Bs),
   append(BeforeJ,[AtJ|PastJ],Bs),
   append(BeforeJ,[AtI|PastJ],Cs),
   length(BeforeI,I),
   length(BeforeJ,J),!.

checkPath(State,From,To):-dfs(From,To,[],Path,State),length(Path,Size),Size>0.

generateMoves(X,Y):- node(X), node(Y), X \== Y.

checkStartIsCar(State,Position) :- nth0(Position,State,Car),Car \== 0.

checkEndIsEmpty(State,Position) :- nth0(Position,State,Spot), Spot == 0.

moveCar(PreviousState):- generateMoves(From,To),checkStartIsCar(PreviousState,From), checkEndIsEmpty(PreviousState,To),checkPath(PreviousState,From,To), swapCar(PreviousState,From,To,NewState),
  \+(states(_, NewState)),
  assert(states(PreviousState, NewState)),fail;!.

path(Finish, [[Finish | PathPart] | _], [Finish | PathPart]):-!.
path(Finish, [[X | PathPart] | ProcList], Path):-
  moveCar(X),
  findall(Y, step(X, PathPart, Y), AdjNodes),
  append(ProcList, AdjNodes, NewProcList), !,
  path(Finish, NewProcList, Path).

step(X,T,[Y,X|T]):-
  states(X,Y),
  not(member(Y,T)).

path(Start, Finish):-
    path(Finish, [[Start]], RPath), !,
    reverse(RPath,Path), write(Path).

Сейчас для поиска решения используется поиск в ширину.

Теперь по функциям.
Функция DFS ищет путь по пустым клеткам от бокса до бокса, проверяя, чтобы по пути мы проходили только по пустым боксам (проверка на 0)
Функция SwapCar переставляет элементы с заданными индексами в массиве-состоянии, для получения нового состояния.
GenerateMoves используется для создания всевозможных перестановок, которые потом отсеются проверками CheckStartIsCar, dfs, CheckEndIsEmpty.
CheckStartIsCar проверяет, что точка, откуда мы собираемся двигать занята машиной.
CheckEndIsEmpty проверяет, что точка КУДА мы двигаем машину — пуста.

Таким образом мы движемся только по заданным ранее ребрам.

Также в moveCar добавлено добавление новых состояний

not(states(_, NewState)),
  assert(states(PreviousState, NewState)),fail;!

так как мы используем поиск в ширину.

Как в моём понимании должно всё работать.

Мы запускаемся от path(начальное положение, желаемое положение)
Наш moveCar сгенерирует все ДОПУСТИМЫЕ перемещения (он действительно это делает, проверял) из этого состояния. То есть, на первом ходу мы можем сделать 8 разных допустимых перемещений. Создаются ребра графа states, если еще не было пути в определённые состояния.
Затем уже стандартный поиск в ширину с достраиванием графа.

Если Вам не сложно, я бы с удовольствием посмотрел на Ваше решение.