-
0 votesanswersviews
Iterative Deepening深度优先搜索和广度优先搜索生成的节点总数是多少
在分支因子“b”和最浅目标“d”的深度方面,Iterative Deepening深度优先搜索和广度优先搜索生成的节点总数是多少 -
0 votesanswersviews
通过增加分支因子和深度在迭代加深中的顶部效应
我正在研究迭代深化这个link . 我主要担心的是 Overhead . 该链接说明了这一点 分支因子越高,重复扩展状态的开销越低 对于这一陈述没有给出任何解释,也没有在该链接上给出令人信服的论据 . 我正在寻找这个陈述背后的原因,因为我认为随着分支因子的增加,开销应该增加,这也意味着没有节点增加,那么开销会减少多少? 直到现在我找不到任何合理和有帮助的东西 . 如果有人可以帮助纠正我的概念... -
3 votesanswersviews
迭代加深如何影响时间复杂度?
我有一个树遍历算法,它通常在O(bm)中运行,其中b是分支因子,m是最大深度 . 使用迭代加深,该算法一次又一次地运行,在增加的深度m次: O(bm)=b⁰b¹b²... bm 基于我对时间复杂度的有限理解,我们采用最大元素,因为随着时间的推移,这是最重要的元素,因此元素将是bm,其中m是达到的最大深度 . 因此,根据这些知识,我会得出结论,迭代加深算法也在O(bm)中运行 . 但是,从逻辑的角度... -
1 votesanswersviews
迭代加深深度首先搜索比深度优先搜索更高的时间复杂度?
似乎迭代深化搜索应该具有比BFS更高的渐近时间复杂度,因为每次深度限制增加时,它必须从头开始搜索 . 但维基说不然,为什么? -
1 votesanswersviews
迭代加深深度首先使用有限的内存进行搜索
这是Find first null in binary tree with limited memory的后续行动 . 维基百科说,迭代加深深度优先搜索将找到最短路径 . 我想在内存中限制k个节点并以最少的次数访问树 . 例如,如果我的二叉树是: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 而且我... -
1 votesanswersviews
完全迭代深化深度优先搜索
在那一刻,我有一个看起来有点像这样的物体 . C# public class Step { int id; List<Step> nextSteps; } 我试图将它转换为另一个看起来非常相似的对象,除了它不允许循环这一事实 . 它应该通过不扩展已经出现在更高深度的节点的子节点来处理循环 . 迭代深化解决了这个问题(深度优先搜索实现但是广度优先搜索顺序),但我正在努力使用以下... -
33 votesanswersviews
迭代深化与深度优先搜索
我一直在阅读有关迭代深化的内容,但我不明白它与深度优先搜索的区别 . 我知道深度优先搜索越来越深入 . 在迭代深化中,您 Build 一个级别的值,如果该级别没有解决方案,则递增该值,然后从头开始(根) . Wouldn't this be the same thing as depth-first search? 我的意思是你会继续增加和增加,直到找到解决方案 . 我认为这是同样的事情!我会走同... -
3 votesanswersviews
如何在迭代深化/深度限制搜索中存储访问状态?
更新:搜索第一个解决方案 . 对于正常的深度优先搜索,它很简单,只需使用哈希集 bool DFS (currentState) = { if (myHashSet.Contains(currentState)) { return; } else { ... -
1 votesanswersviews
迭代加深二叉树中的深度优先搜索
我有一个普通的二叉树,我试图应用迭代加深深度第一次搜索使用c: struct node { int data; struct node * right; struct node * left; }; typedef struct node node; 我正在使用一个函数将节点插入到树中,现在我需要实现搜索功能,如下所示: function search(root,goa... -
10 votesanswersviews
prolog深度第一次迭代加深
我试图实现深度优先深度搜索状态空间图 . 我有一个带有三个顶点的图形,它们是两个激活边和两个禁止边 . 每个节点都有一个二进制值,统称这是图的状态 . 通过查看其中一个节点是高于阈值还是低于阈值(通过对所有传入节点求和计算),图形可以转换到新状态 . 每个转换最多只有一个节点会发生变化 . 由于它们是三个节点,它们是三个状态转换边缘,在状态转换图中留下每个状态 . 我认为我的state_chan... -
1 votesanswersviews
迭代加深深度首先在2d数组中搜索
我试图在2d数组(迷宫)中实现迭代加深搜索 . static void Run_Ids(int x, int y) { int depth_limit = 0; while(!cutoff) { out.println("Doing search at depth: " + depth_li... -
4 votesanswersviews
如何使用alpha beta修剪实现迭代深化
我正在编写一个程序来播放Dots和Boxes,我希望通过在迭代深化方案中根据他们的启发式值在alphaBeta中考虑我考虑的移动来提高我的时间效率 . 基本上,我想进入搜索树,每次迭代都会增加深度,并使用alphaBeta评估每个节点 . 在每次连续迭代中,我考虑节点的顺序将由来自前一次迭代的节点的启发式值决定 . 但是,我无法理解如何实现这一点 . 有人可以为标准alphaBeta程序如何使用迭... -
1 votesanswersviews
实现迭代深化深度优先搜索
我使用维基百科page中的以下伪代码来实现迭代深化深度优先搜索图形 function IDDFS(root) for depth from 0 to ∞ found ← DLS(root, depth) if found ≠ null return found function DLS(node, depth) if dep... -
1 votesanswersviews
如何存储从迭代加深深度优先搜索中找到的路径
我试图使用数组来存储从Iterative deepening depth-first search算法找到的路径 . 我有N个顶点,我希望通过数组pathTo [N]存储从顶点X到顶点Y的路径,其中pathTo [W] = V表示将从节点V访问节点W,即V是dfs中W的父节点树 . (因此,通过追溯父母从N回来,我们可以找到通向N的路径 . ) 任何人都可以帮我用伪代码实现它吗?我会尝试从中...