- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数:
function BACKTRACKING-SEARCH(csp) returns solution/failure
return RECURSIVE-BACKTRACKING({},csp)
function RECURSIVE-BACKTRACKING(assignment,csp) returns soln/failure
if assignment is complete then return assignment
var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
if value is consistent with assignment given CONSTRAINT[csp] then
add {var = value} to assignment
result <- RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove {var = value} from assignment
return failure
BACKTRACKING-SEARCH(csp) 中 csp 的输入是一个 csp 类,其中包含 a) 状态列表,b) 颜色列表,以及 c) 以状态为键且值为的有序字典不能具有相同颜色的状态的邻居列表。
问题是我很难理解该算法是如何正确工作的。如果有人能给我这个算法的正确解释,我将不胜感激。我的一些具体问题是:
if assignment is complete then return assignment
我假设由于赋值是作为空字典 {} 输入的,这将返回解决方案,即包含状态及其颜色的字典。但是,我不明白如何检查作业是否完成?会不会像根据状态数检查字典的大小?
var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
输入的 csp 类包含一个状态列表,我假设这可能只是 var 等于从列表中弹出一个值?我想,让我感到困惑的是,在我输入的情况下,我不确定参数(VARIABLES[csp]、assignment、csp)在做什么。
for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
再次,对 (var, assignment, csp) 的输入到底在做什么感到困惑。但我假设它会遍历状态字典中的每个值(邻居)?
if value is consistent with assignment given CONSTRAINT[csp] then
add {var = value} to assignment
result <- RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove {var = value} from assignment
如何正确检查值是否与给定约束 [csp] 的赋值一致?我假设约束应该是我尚未实现的 csp 类的一部分?我不明白这个 if 语句在检查方面做了什么。如果有人能清楚地解释这个 if 语句和 if 语句的主体,那将是非常有用的。
最佳答案
因此,在重新整理了一些大学文献(Peter Norvig 的人工智能:一种现代方法)之后,事实证明您手上的问题是递归的应用 Backtracking作为寻找 Graph Coloring Problem 的解决方案的一种方式,也称为 map 着色(考虑到它的历史是为了解决绘制 map 所需的最小化颜色的问题)。将 map 中的每个国家替换为节点及其边界将为您提供一个图表,我们可以在其中应用递归回溯来找到解决方案。
递归回溯将作为深度优先树搜索下降图节点,检查每个节点是否可以使用颜色。如果不是,则尝试下一种颜色,如果是,则尝试下一个未访问的相邻节点。如果对于给定节点,没有颜色满足条件,它将后退(回溯)并移动到兄弟节点(如果该节点没有兄弟节点,则移动到父节点的兄弟节点)。
所以,
I assume that since assignment is inputted as an empty dictionary {}, that this will return the solution, that is, the dictionary that contains states and their colors ... Would it be something like checking the size of the dictionary against the number of states?
是的,是的。一旦字典包含具有颜色的图形的所有节点,您就会有一个解决方案。
The input csp class contains a list of states, I assume this could just be var equal to popping off a value in the list?
该伪代码语法令人困惑,但总的想法是您将有办法找出图形中尚未着色的节点。一种简单的方法是从字典中返回一个没有赋值的节点。因此,如果我正确理解语法,var
将存储一个节点。VARIABLES[csp]
在我看来像是 CSP 结构中节点列表的表示。
I'm not sure what the parameters (VARIABLES[csp], assignment, csp) are doing, given my input
如上所述,赋值参数是包含到目前为止评估的节点(以及 future 的解决方案)的字典,csp 是包含 a,b 和 c 的结构。
Again, confused on what the inputs of (var, assignment, csp) are doing exactly. But I assume that it'll go through each value (neighbor) in dictionary of the state?
ORDER-DOMAIN-VALUES 似乎是一个函数,它将在您的 CSP 结构中返回有序的颜色集。 FOR 循环将遍历每种颜色,以便测试它们以满足该级别的问题。
if value is consistent with assignment given CONSTRAINT[csp] then
在这里,您正在做的是使用该值测试约束,以确保它是真实的。在这种情况下,您要检查与该节点相邻的任何节点是否已经不具有该颜色。如果相邻节点具有该颜色,则跳过 IF 并迭代 for 循环以尝试下一种颜色。
如果没有相邻节点具有该颜色,则进入 IF 主体并将具有颜色 value
的节点 var
添加到 assignment
字典中(我相信 {var = value} 是一个元组表示,我会写成 {var,value},但是哦,好吧)。然后再调用函数recursive backtracking,递归。如果递归调用返回非失败,则返回其结果(这意味着已经找到解决方案)。
如果它返回一个失败(意思是,它尝试了所有的颜色并且所有这些颜色恰好被另一个相邻节点使用),那么从分配
(解决方案) 阵列并移动到下一个颜色。如果所有颜色都用完了,返回失败。
关于algorithm - 理解约束满足问题 : map coloring algorithm,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52682417/
我在一本书(Interview Question)中读到这个问题,想在这里详细讨论这个问题。请点亮它。 问题如下:- 隐私和匿名化 马萨诸塞州集团保险委员会早在 1990 年代中期就有一个绝妙的主意
我最近接受了一次面试,面试官给了我一些伪代码并提出了相关问题。不幸的是,由于准备不足,我无法回答他的问题。由于时间关系,我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题,以便我可以改
这是我的代码 public int getDist(Node root, int value) { if (root == null && value !=0) return
就效率而言,Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少? 我知道这与具体的实现和硬件密切相关,但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下,问了一些他们认为
我想学习一些关于分布式算法的知识,所以我正在寻找任何书籍推荐。我对理论书籍更感兴趣,因为实现只是个人喜好问题(我可能会使用 erlang(或 c#))。但另一方面,我不想对算法进行原始的数学分析。只是
我想知道你们中有多少人实现了计算机科学的“ classical algorithms ”,例如 Dijkstra's algorithm或现实世界中的数据结构(例如二叉搜索树),而不是学术项目? 当有
我正在解决旧编程竞赛中的一些示例问题。在这个问题中,我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟,我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。 解决
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 8 年前。 Improve
我开始学习 Nodejs,但我被困在中间的某个地方。我从 npm 安装了一个新库,它是 express -jwt ,它在运行后显示某种错误。附上代码和错误日志,请帮助我! const jwt = re
我有一个证书,其中签名算法显示“sha256rsa”,但指纹算法显示“sha1”。我的证书 SHA1/SHA2 的标识是什么? 谢谢! 最佳答案 TL;TR:签名和指纹是完全不同的东西。对于证书的强度
我目前在我的大学学习数据结构类(class),并且在之前的类(class)中做过一些算法分析,但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分
有一个由 N 个 1x1 方格组成的区域,并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。 下面是一些面积的例子。 我想在这个区域中选择一些方块,并且两个相邻的方块不能一起选择(对角接触
我有一些多边形形状的点列表,我想将其包含在我页面上的 Google map 中。 我已经从原始数据中删除了尽可能多的不必要的多边形,现在我剩下大约 12 个,但它们非常详细以至于导致了问题。现在我的文
我目前正在实现 Marching Squares用于计算等高线曲线,我对此处提到的位移位的使用有疑问 Compose the 4 bits at the corners of the cell to
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数: function BACKTRACKING-SEARCH(csp) returns solution/failure return R
是否有包含反函数的库? 作为项目的一部分,我目前正在研究测向算法。我正在使用巴特利特相关性。在 Bartlett 相关性中,我需要将已经是 3 次矩阵乘法(包括 Hermitian 转置)的分子除以作
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
问题的链接是UVA - 1394 : And There Was One . 朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。 我搜索了一种替代算法并
COM 中创建 GUID 的函数 (CoCreateGUID) 使用“分散唯一性算法”,但我的问题是,它是什么? 谁能解释一下? 最佳答案 一种生成 ID 的方法,该 ID 具有一定的唯一性保证,而不
在做一个项目时我遇到了这个问题,我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状,但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。 我有 n 个不同大小的容器,
我是一名优秀的程序员,十分优秀!