Реализовать более быстрый алгоритм

Question

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

(defun find-closest (list) 
    (x (car (array-dimensions list))) 
     (y (cadr (array-dimensions list))) 
      (let ((elems (aref list x y))) 
       (dolist (e elems) 
        (when (eq (type-of e) type) 
         (return-from find-closest (list x y)))) nil)) 

Я попытался реализовать DFS, но потерпел неудачу, и я не совсем понимаю, почему. Ниже мой код.

(defun find-closest (list) 
    (let ((open (list list)) 
    (closed (list)) 
    (steps 0) 
    (expanded 0) 
    (stored 0)) 
    (loop while open do 
     (let ((x (pop open))) 
     (when (finished? x) 
      (return (format nil "Found ~a in ~a steps. 
Expanded ~a nodes, stored a maximum of ~a nodes." x steps expanded stored))) 
     (incf steps) 
     (pushnew x closed :test #'equal) 
     (let ((successors (successors x))) 
      (incf expanded (length successors)) 
      (setq successors 
      (delete-if (lambda (a) 
       (or (find a open :test #'equal) 
        (find a closed :test #'equal))) 
        successors)) 
      (setq open (append open successors)) 
      (setq stored (max stored (length open)))))))) 

Answer 1

Глядя на код, функция find-some-in-grid возвращает первую найденную вещь из type. Это, по сути, даст вам время O (n * m) для мира n * m (представьте себе мир, где у вас есть одна грязь на каждой линии, чередуя «самые левые» и «самые правые»).

Поскольку вы можете вытащить список всех мест грязи, вы можете построить кратчайший обход или, по крайней мере, более короткое обходное путешествие, вместо того, чтобы выбрать любую грязь, которую вы случайно найдете, сначала вы выбираете ближайшую (для некоторых метрика расстояния, из кода, похоже, у вас есть расстояния Манхэттена (т. е. вы можете двигаться только по оси X x или оси Y, а не одновременно). Это должно дать вам робот, который по крайней мере так же хорош, как робот с немым обходом и часто лучше, даже если он не является оптимальным.

С условием, что у меня нет реализации книги и базы чисто на том, что у вас в вопросе, может быть что-то вроде этого:

(defun find-closest-in-grid (radar type pos-x pos-y) 
    (labels ((distance (x y) 
       (+ (abs (- x pos-x)) 
       (abs (- y pos-y))))) 
    (destructuring-bind (width height) 
     (array-dimensions radar) 
     (let ((best nil) 
      ((best-distance (+ width height)))) 
     (loop for x from 0 below width 
      do (loop for y from 0 below height 
       do (loop for element in (aref radar x y) 
         do (when (eql (type-of element) type) 
          (when (<= (distance x y) best-distance) 
           (setf best (list x y)) 
           (setf best-distance (distance x y)))))))) 
     best)))