Я бы сделал две основные вещи: Сначала , алгоритм имеет состояние, состоящее из нескольких «переменных» (queue, stack и т. Д.). Сначала я бы построил функцию, которая представляет алгоритмическое состояние с использованием неизменяемой карты, например
(defn initialize-state [g start]
(let [nodeset (disj (nodes g) start)]
{:g g
:nodeset nodeset
:pred (apply assoc {} (interleave (nodes g) (repeat nil)))
:dist (apply assoc {start 0} (interleave nodeset (repeat -1)))
:sigma (apply assoc {start 1} (interleave nodeset (repeat 0)))
:stack []
:queue (conj clojure.lang.PersistentQueue/EMPTY start)
:current-vertex nil}))
Затем я бы в REPL проверил, правильно ли инициализирована эта карта для различных вариантов g и start.
Второй , я бы разбил алгоритм на несколько небольших функций, которые принимают состояние в качестве ввода и возвращают состояние в качестве вывода, вот так ( код не сработает, необходимо заполнить недостающие части):
(defn next-vertex [state]
{:pre [(state? state)]
:post [(state? %)]}
(let [v (peek (:queue state))]
(-> state
(update :stack conj v)
(assoc :current-vertex v))))
(defn process-successor [state w]
(let [dist-w (dist w)]
(cond
;; fill in...
)))
(defn process-successors [state]
{:pre [(state? state)]
:post [(state? %)]}
(reduce
process-successor
state
(successors (:g state) (:current-vertex state))))
(defn pop-queue [state]
{:pre [(state? state)]
:post [(state? %)]}
(update state :queue pop))
Карты с ключами :pre и :post являются так называемыми предварительными и последующими условиями, и функция state? может быть реализована, например, как (defn state? [x] (and (map? x) (contains? x :queue))), просто как проверка работоспособности.
Обратите внимание, что для каждой написанной вами функции вы можете протестировать ее в REPL с некоторыми данными, чтобы убедиться, что она работает, прежде чем писать следующую функцию. Все эти функции теперь могут быть объединены в полный переход состояния с помощью comp:
(def next-state (comp pop-queue process-successors next-vertex))
Теперь окончательный алгоритм выглядит примерно так:
(defn ss-shortest-path [g start]
(loop [state (initialize-state g start)]
(if (empty? (:queue state))
state
(recur (next-state state)))))
Итак, подведем итог: реализовать алгоритм намного проще, если разбить его на более мелкие части , которые можно разработать и проверить индивидуально.