實施更快的算法

Question

我一直被困在這個問題上好幾天。顯然我需要編寫一個更好的算法來贏得下面的算法。下面的代碼是從着名的艾瑪文件實現的。這裏有沒有專家可以指導我如何贏得算法？

(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第一件事發現的功能。實質上，這將給你一個n * m世界的O（n * m）時間（設想一個世界，在每一行中有一個污點，在「最左側」和「最右側」之間交替）

既然你可以列出所有的灰塵位置，你可以建立一個最短的遍歷，或者至少是一個短於傾銷的遍歷，而不是選擇你發現的任何污垢，首先你選擇最接近的（對於一些距離度量，從代碼看起來你有曼哈頓距離（也就是說，你只能沿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)))