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

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

Вообще, я не понимаю ваш алгоритм. Опишите пожалуйста что делает каждая функция. Я не понимаю зачем вам генерировать перестановки. Я пытался разобрать, например, что если ваша программа передвинет машину 6 с клетки b в клетку f — то будет ли она на следующем шаге пытаться передвинуть ее назад в клетку b. Если ваша программа так делает, то это можно исправить и эффект может появиться. Например, на каком-то шаге она может передвинуть 4 машины, значит в дереве поиска решения на следующем ярусе будет 4 узла, но если она может сдвинуть их еще и назад — то 8 узлов. Если в вашем дереве потом будет например 10 ярусов (задача решается за 10 ходов) — то программа зря обрабатывает 4^10 вариантов, а это много.

Но я еще раз повторюсь, я не смог понять ваш код. Я уже просил подробно его расписать. Мне кажется, что комментарии в коде у вас лишь запутывают. Так функция dfs у вас не проверяет наличие пути между вершинами (или делает не только это).

Я не понимаю почему у вас в БД явно записаны все дуги — можно было описать лишь половину, вторая часть могла бы быть получена так:

check_edge(A, B):-
  edge(A, B), !; edge(B, A).

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

Я не понял почему и зачем swapCar выполняет 4 раза append и что он вообще должен делать. Как по мне, чтобы переставить машину X из бокса A в бокс B надо выполнить что-то такое:

select(node(A, X), State, StatePart), !,
NextState = [node(B, X)|StatePart].

И это однозначно будет работать быстрее чем ваш код.

Мне вообще не понятно что делает функция generateMoves. Просто не понимаю зачем нужно генерировать все возможные пары вершин (перемещаться мы все равно может только по дугам графа, которых гораздо меньше), хотя ваша функция moveCar пытается перемещать все машины как попало — без учета дуг графа (если я правильно понял).

Может быть я не прав. Я хочу помочь, но не могу понять код. Я прошу описать то, как с вашей точки зрения он работает (каждая функция).