gpt4 book ai didi

tree - Setf(?)导致树中的循环

转载 作者:太空宇宙 更新时间:2023-11-03 18:42:17 26 4
gpt4 key购买 nike

我正在 Common Lisp (CLISP) 中实现进化算法,但遇到了问题。

我有一个树状类:

(defclass node ()
((item :initarg :item :initform nil :accessor item)
(children :initarg :children :initform nil :accessor children)
(number-of-descendants :initarg :descs :initform nil :accessor descs)))

还有一些方法:

(defmethod copy-node ((n node))
(make-instance
'node
:item (item n)
:descs (descs n)
:children (mapcar #'copy-node (children n))))

(defmethod get-subtree ((n node) nr)
(gsth (children n) nr))
(defmethod (setf get-subtree) ((val node) (n node) nr)
(setf (gsth (children n) nr) val))
(defmethod get-random-subtree ((n node))
(gsth (children n) (random (descs n))))
(defmethod (setf get-random-subtree) ((val node) (n node))
(setf (get-subtree n (random (descs n))) val))

(defun gsth (lst nr)
(let ((candidate (car lst)))
(cond
((zerop nr) candidate)
((<= nr (descs candidate)) (gsth (children candidate) (1- nr)))
(t (gsth (cdr lst) (- nr (descs candidate) 1))))))

(defun (setf gsth) (val lst nr)
(let ((candidate (car lst)))
(cond
((zerop nr) (setf (car lst) val))
((<= nr (descs candidate))
(setf (gsth (children candidate) (1- nr)) val))
(t (setf (gsth (cdr lst) (- nr (descs candidate) 1)) val)))
val))

我想做的是交换种群中两棵随机树的两个随机子树。但是当我做这样的事情时:

(defun stdx (population)
(let ((n (length population))
(npop))
(do ((done 0 (+ done 2)))
((>= done n) npop)
(push (stdx2 (copy-node (random-el population))
(copy-node (random-el population)))
npop))))

(defun stdx2 (father mother)
;; swap subtrees
(rotatef (get-random-subtree father)
(get-random-subtree mother))
(check-for-cycles father)
(check-for-cycles mother))

有时会检测到循环,这显然不应该发生。

检查循环没问题,我也用 (trace) 检测到循环。我一直在更新后代数。

我猜 (setf get-subtree) 有问题。我是 LISP 的新手,我不太擅长 setf 扩展。请帮助我。

最佳答案

想想这将如何实现:

;; swap subtrees
(rotatef (get-random-subtree father)
(get-random-subtree mother))

rotatef 形式将被宏扩展成类似这样的东西:

(let ((a (get-subtree father (random (descs father))))
(b (get-subtree mother (random (descs mother)))))
(setf (get-subtree father (random (descs father))) b)
(setf (get-subtree mother (random (descs mother))) a))

(您可以使用 macroexpand 来准确了解您的情况下的扩展。)

换句话说,随机子树将被选择两次(读取时一次,更新时一次),因此子树不会相互交换,而是对子树的引用被复制到另一棵树中的随机位置。

例如,在下图中,算法可能会选择蓝色和红色子树进行交换。但是当涉及到附加它们时,它会将它们放在标有圆点的点上。

图表的下半部分显示了子树附加到新点后的结果数据结构:您可以看到已经创建了一个循环。

所以你需要修改代码,这样你就可以选择随机子树一次。可能是这样的:

(let ((a (random (descs father)))
(b (random (descs mother))))
(rotatef (get-subtree father a)
(get-subtree mother b)))

关于tree - Setf(?)导致树中的循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13805966/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com