Поиск путей в 2d массиве

Question

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

(defparameter *test-array*
  #2A((131 673 234 103 18)
      (201 96 342 965 150)
      (630 803 746 422 111)
      (537 699 497 121 956)
      (805 732 524 37 331)))

(defun find-paths (array &aux (height (array-dimension array 0)) (width (array-dimension array 1)))
  "Returns the possible paths across a given 2d array from the left column to
  the right column."
  (loop :for i :from 0 :below height
        ;; We have three ways per starting point up, left and down.
        ;; In the first and last row there are two ways, only.
        :append (loop :for (j l) :in '((1 0) (0 1) (-1 0))
                       :when (and (>= (+ j i) 0) (< (+ j i) height))
                         :collect (list (aref array i 0) (aref array (+ i j) l))) :into paths
        :finally (return paths)))

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

Answer 1

Это кажется решаемым динамическим программированием.

Я бы создал новый массив с такими же размерами, который содержит два значения в каждой координате: лучший путь к нему и его стоимость. Инициализируйте эти значения в крайнем левом столбце, а затем распространяйте их вправо.

Затем распространяйте путь каждого элемента, насколько это улучшение. Затем налево, потом вниз. Перемещайтесь по направлениям, пока ни одно из них не даст улучшения.

Наконец, лучший путь в крайнем правом столбце - это решение.