Первый шаг - попытаться сформулировать проблему в виде графа.В этом случае каждый узел (также называемый вершиной) на графике представляет некоторую возможную конфигурацию (положение или состояние) пустыни, описываемую местоположением грузовика и количеством газа в каждом лагере.Поскольку пустыня является фиксированной линией, имеет смысл представлять ее как массив количеств газа.С этими деталями, вот начальный узел графа:
truck (gas: 3)
v
[0, 0, 0, 0, 0]
^ ^
start goal
С этой позиции, назовите его (A), какие переходы (ребра) в другой узел возможны?Вот они:
(B) (C) (D)
truck (gas: 0) truck (gas: 0) truck (gas: 0)
v v v
[0, 2, 0, 0, 0] [0, 0, 1, 0, 0] [0, 0, 0, 0, 0]
Вот как переходы выглядят в графической форме:
A
/|\
/ | \
B C D
Узлы (B), (C) и (D) являются дочерними узлами(A), их родитель, что означает доступный переход от родителя к ребенку.Один за другим исследует этих детей - BFS , тогда как в DFS вы выбираете первого ребенка, (B), и продолжаете изучать его первого ребенка, пока он не достигнет листаузел без детей.
Ясно, что (D) является конечным конечным узлом, потому что у него нет детей (это не цель, у грузовика нет газа, а в лагере нет газа, поэтому он застрял;нет доступных переходов для рассмотрения).
Следующим шагом является проверка всех возможных дочерних состояний, доступных для узлов (B) и (C).Вот дети (B):
(E) (F) (G)
truck (gas: 3) truck (gas: 0) truck (gas: 0)
v v v
[0, 1, 0, 0, 0] [0, 0, 1, 0, 0] [0, 0, 0, 0, 0]
(H)
truck (gas: 0)
v
[0, 1, 0, 0, 0]
Теперь график выглядит следующим образом:
A
/ | \
/ | \
/ | \
B C D
/|\ \
/ | \ \
E F G H
Обратите внимание, что узлы (F) и (G) идентичны (C) и(D) и (E), безусловно, самый многообещающий маршрут.Несмотря на это, (C) будет следующим расширением, поскольку это BFS, а не DFS.Я пропущу диаграмму, но должно быть ясно, что оба потомка (C) ((I) и (J)) являются конечными конечными узлами (у грузовика закончится бензин, независимо от того, движется он влево или вправо).В этот момент график выглядит следующим образом:
A
/ | \
/ | \
/ | \
/ | \
/ | \
B C D
/|\ \ |\
/ | \ \ | \
E F G H I J
В этот момент должно быть ясно, что все ведет к конечному узлу, кроме (E), чьи дочерние элементы будут расширяться до тех пор, пока не будет достигнута цельили исследуются все узлы в графе (то есть нет решения).
Если цель достигнута, она гарантированно будет кратчайшим путем, поскольку глубина расширения увеличивается на 1 на каждом шаге, и все возможности перехода рассматриваются последовательно для каждого уровня глубины.
Я надеюсь, что это упражнение сделает алгоритм более понятным;на самом деле, похоже, что (E) находится всего в двух шагах от цели - посмотрите, сможете ли вы найти оставшуюся часть пути вручную.
При реализации имейте в виду, что используется стек (или рекурсивныйзвонки) выполняет DFS, а очередь делает BFS.Кроме того, каждый узел должен иметь свою собственную копию «пустынного» массива или ему нужен способ отменить его перемещение, если оно недопустимо.Наконец, на каждом узле, проходите через каждого возможного потомка, уменьшая некоторое количество газа (или добавляя 3, если в базовом лагере) и пробуя оба движения влево и вправо для каждого.
Последний шаг: оптимизация.Отслеживая уже изученные узлы и избегая их повторного вычисления (это также может помочь избежать бесконечных циклов в графе, что не кажется проблемой в этом случае (почему?)), Вы можете пожертвовать пространством хранения и выигратьскорость.Вы также можете использовать эвристический поиск для дальнейшего повышения скорости, отдавая предпочтение более перспективным маршрутам на графике.