实施更快的算法

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)))