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

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

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

edge(a, b).
edge(b, c).
edge(c, d).
%edge(b, e).
%edge(e, f).
edge(f, e).
%edge(f, h).
%edge(h, j).
edge(j, i).
edge(j, k).
edge(k, l).

edge(b, f).
edge(j, f).
  
merge_list([], []):-!.
merge_list([HeadA|TailA], B):-
  select(HeadA, B, TailB), !,
  merge_list(TailA, TailB).

exist_edge(From, To):-
  edge(From, To); edge(To, From).
  
proliferate(FromState, [(CarId, CarCellTo)|FromTailState]):-
  select(Car, FromState, FromTailState),
  Car = (CarId, _CarCellFrom),
  move_car(Car, CarCellTo, FromTailState).
  
move_car((_CarIdFrom, CellFrom), CellTo, OtherCars):-
  exist_edge(CellFrom, CellTo),
  \+ member((_CarIdTo, CellTo), OtherCars).
  
is_state_processed(State, ProcessedStates):-
  member(ProcessedState, ProcessedStates),
  merge_list(State, ProcessedState), !.
  
path([[FinishState|PathPart]|_], [FinishState|PathPart]):-
  merge_list(FinishState, [(1, a), (2, b), (3, c), (4, c), (5, i), (6, j), (7, k), (8, l)]).
path([[FromState|PathPart]|ProcList], Path):-
  findall(Y, step(FromState, PathPart, Y), AdjNodes),
  append(ProcList, AdjNodes, NewProcList), !,
  path(NewProcList, Path).  
  
step(FromState, ProcessedStates,[ToState, FromState|ProcessedStates]):-
  proliferate(FromState, ToState),
  \+ is_state_processed(ToState, ProcessedStates).
 
solution(Path):-
  path([[[(5, a), (6, b), (7, c), (8, c), (1, i), (2, j), (3, k), (4, l)]]], RPath),
  reverse(RPath, Path), write(Path).

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

Если мы на вход подадим менее сложное требование (например ситуацию, когда нам необходимо всего 8 перестановок, чтобы достигнуть результата), то помучавшись 30 сек. она выдает список переходов.

В таком случае можно применить, так называемый поиск с заглублением – это модификация поиска в глубину, при которой сначала ищется решение за 1 ход, потом за 2, за 3 и т.д. пока не будет подобрано минимальное число ходов для получения ответа.