标签: iterative-deepening

我一直在阅读有关迭代深化的内容,但我不明白它与深度优先搜索的区别.

我知道深度优先搜索越来越深入.

在迭代深化中,您建立一个级别的值,如果该级别没有解决方案,则递增该值,然后从头开始(根).

这不会与深度优先搜索相同吗？

我的意思是你会继续增加和增加,直到找到解决方案.我认为这是同样的事情!我会走同一个分支,因为如果我从头开始,我会像以前一样走下同一个分支.

我理解BFS和DFS,但对于我的生活无法弄清迭代加深和BFS之间的区别.显然迭代加深与DFS具有相同的内存使用率,但我无法看到这是如何可能的,因为它只是像BFS一样不断扩展.如果有人能澄清那将是非常棒的.

如果需要,可以使用树:

    A
   / \
  B   C
 /   / \
D   E   F

我试图实现深度优先深度搜索状态空间图.我有一个带有三个顶点的图形,它们是两个激活边和两个禁止边.每个节点都有一个二进制值,统称这是图的状态.通过查看其中一个节点是高于阈值还是低于阈值(通过对所有传入节点求和计算),图形可以转换到新状态.每个转换最多只有一个节点会发生变化.由于它们是三个节点,它们是三个状态转换边缘,在状态转换图中留下每个状态.

我认为我的state_change/3工作正常,例如我可以查询:

?-g_s_s(0,1,1,Begin),node(Arc),state_change(g_s(Begin),Second,Arc).

它给了我三个正确的答案:

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v1,
Second = g_s([node(v1, 1), node(v2, 1), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v2,
Second = g_s([node(v1, 0), node(v2, 0), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v3,
Second = g_s([node(v1, 0), node(v2, 1), node(v3, 0)]) 

我正在尝试使用Bratkos Prolog中为AI书提供的谓词id_path,这是问题11.3的解决方案,但我在使用/调整它时遇到了问题. 我想创建一个从起始节点到其他节点的路径,而没有进入循环 - 我不希望它有重复元素或在路径不存在时卡住.我希望路径说出起始状态,然后是一系列可以从起始状态访问的状态.如果有一个自循环,我希望每次到达那里都包含一次.即我想跟踪我进入状态空间的方式并使其独特,而不仅仅是状态空间在路径中是唯一的.

例如,从011开始,我希望所有三条长度为1的路径都可以找到弧线.

 ?-id_path(g_s([node(v1,0),node(v2,1),node(v3,1)],Last,[Temp],Path).
Path = [[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,1)],v1)];
Path =[[node(v1,0),node(v2,1),node(v3,1)], to([node(v1,0),node(v2,0),node(v3,1)],v2)];
Path=[[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,0)],v3)];

然后在下一个级别所有具有三个节点的路径,显示它需要到达节点的两个弧,然后在下一个级别所有具有四个节点的路径显示它需要的三个弧等

如果这有用,我还将我的代码放在SWISH中？(第一次尝试这个？!) …

我正在尝试开发一个简单的国际象棋引擎,但我正在努力实现其性能.我已经使用alpha-beta修剪和迭代加深实现了Negamax(没有任何额外的启发式),但是我无法获得超过3-4层的合理搜索时间.以下是从游戏开始我的程序日志的摘录:

2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - …

我试图call_with_depth_limit/3在 SWI-Prolog 中使用来实现迭代深化，要么我不明白它是如何工作的，要么它行为不端。我有一个例子，其中发生以下情况：

?- call_with_depth_limit(mygoal, 29, Result).
Result = 29 ;
Result = 25 ;
Result = 27 ;
Result = 27 ;
false.

?- call_with_depth_limit(mygoal, 26, Result).
Result = depth_limit_exceeded ;
false.

根据文档，如果目标可以用限制最大递归或更少来证明，它应该会成功。在限制为 30 的第一次调用中，我们看到结果为 25，因此我希望以 26 的限制调用它会成功。我在模块中使用约束处理规则，以防那里可能有一些交互使其行为不端。

编辑：玩过伊莎贝尔的回答后，我想我明白它的行为方式了：

• 它像往常一样运行深度优先搜索，但如果达到限制+1 深度，它就好像失败了。
• 失败的分支计入结果。
• 每次在成功回答后回溯时，它都会将 Result 重置为堆栈的当前深度。

看这个例子：

loop :- loop.

succeed(0).
succeed(N) :- N > 0, N1 is N - 1, succeed(N1).

fail(N) :- N > 0, N1 is N - 1, fail(N1).

?- call_with_depth_limit(succeed(0), 1000, Result). …

我已经编写了一个迭代加深算法,除非我添加循环检查,否则算法会返回一个比它应该更深的解决方案.但是当我没有检查周期时它确实可以正常工作,但这需要很长时间.任何人都可以发现这个bug吗？

(defun rec-depth-limited (problem node cutoff closed)
  (if (= cutoff 0)
    (if (funcall (problem-goalp problem) node)
          node)
    (if (visited-p node closed)
        nil
        (progn
          ;; when i remove the next line, it works correctly
          (setf (gethash (node-state node) closed) t)
          (loop for child in (expand node (problem-actions problem)) do
            (let ((result (rec-depth-limited problem child (1- cutoff) closed)))
                (if result
                    (return result))))))))

(defun iterative-deepening (problem)
  "Iterative deepening search"
  (let ((cutoff 0))
    (loop
      (format t "~%cut-off: ~A" cutoff)
      (let ((solution (rec-depth-limited
                             problem
                             (make-node …

I'm trying to write a CLIPS program which use the Iterative Deepening algorithm to solve a planning problem. For this same reason I would like to keep a low branching factor.

In the following code ?s is the variable which represent the level of the tree; I would like to use a single rule to make different checks. This is what I tried to do:

(defrule EXPAND::action
(declare (salience ?*load*))
(or
    (and ?f1_a <- (status ?s transport ?c1&:(> ?c1 0) …

我在游戏中使用alpha-beta修剪实现了迭代加深，并且还添加了一个“换位表”来存储已经评估过的板子。

现在，我正在执行以下操作：

1. 进行迭代加深时，深度= 0时，它将评估所有位置并将其分数存储在TT中。
2. 现在，当它以depth = 1重新运行时，如果TT中存在该板的值，我就简单地返回它。这将在深度= 0处停止算法，因为深度= 0板的所有值都已在TT中。

如果达到深度极限时，例如，我从TT返回值。depth = MAX_DEPTH，那么大子树将永远不会被剪切。

因此，我不了解如何重新使用TT中存储的值来提高游戏速度？

我在 python 中创建了一个连接 4 AI，我为此使用了带迭代深化和 alpha beta 修剪的 minimax。对于更大的深度，它仍然很慢，所以我想实现一个换位表。在阅读它之后，我想我得到了一般的想法，但我还没有完全让它发挥作用。这是我的代码的一部分：（minimax 的最大化部分）：

    if(isMaximizing):
    maxEval = -99999999999
    bestMove = None
    # cache.get(hash(board)) Here's where i'd check to see if the hash is already in the table 
    # if so i searched for the best move that was given to that board before.

    # loop through possible moves
    for move in [3,2,4,1,5,0,6]:
        if moves[move] > -1:
            # check if time limit has been reached for iterative deepening
            if startTime - time.time() <= -10:
                timeout …

有人可以解释Iterative Deepening A*吗？我仍然不明白它是如何工作的. 具有深度优先搜索功能的迭代深度搜索,如果仍未找到解决方案; 增加Depth ++直到找到解决方案.

如果使用Depth迭代加深,那么Iterative Deepening A*会使用什么来限制他们的搜索？

如果您需要解释IDA*如何工作,这是一张图片,我只是不明白它是如何工作的.

(1,2,4,9)等是步骤

0 + 2 = 2是f(n)= g(n)+ h(n)

我正在编写一个程序来玩点和框，我想通过在迭代深化方案中基于启发式值对alphaBeta中考虑的移动进行排序来提高我的时间效率。本质上，我想进入搜索树，在每次迭代中增加深度，并使用alphaBeta评估每个节点。在每个后续迭代中，我认为节点的顺序将由上一次迭代中节点的启发式值决定。但是，我在理解如何实现方面有困难。有人可以提供伪代码来说明如何将标准alphaBeta程序修改为使用迭代加深进行搜索吗？谢谢！

我有一个Prolog函数path(A,B,Path),它产生从A到B的板上的所有有效路径.

此函数的输出如下所示:

?- path(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
Path = [0, 1, 4, 2] ;
Path = [0, 3, 4, 2] ;
Path = [0, 1, 4, 5, 3, 2] ;

等等

它生成一组包含有效路径的无限列表.我只想得到这些路径中最短的路径(无论有多少路径).也就是说,我想要一个函数shortest(A,B,Path),它将在A到B的板上产生最短的有效路径.

我想要的输出是:

?- shortest(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
false.

我一直在玩setofProlog中的函数将所有路径绑定到一个集合,我对它施加了一些长度限制,但我还没有完成它的工作.

到目前为止我的糟糕工作看起来像这样.这绝对是错的,我很感激任何帮助,了解如何setof工作以及如何从这个集合中找到最短的列表.谢谢!

shortest(A,B,MinPath) :-
    setof(Path,path(A,B,Path),MinPath),
    min(length(Path), length(MinPath)).