- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我收到了逻辑课的家庭作业,但或多或少不知道如何解决它...像这样的查询
?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],Path).
Prolog 应该返回给定图中所有可能的路径。术语 r(X,List) 定义了图,这意味着可以从节点 X 到达 List 中的节点。在这种情况下,输出将是:
Path = [a,b,c] ;
Path = [a,b,e,d] ;
Path = [a,b,e,f,g] ;
Path = [a,d,e,b,c] ;
Path = [a,d,e,f,g] ;
false.
尽管我掌握了 SE 和网络上针对类似问题的众多解决方案,但我还是太笨了,无法弄清楚如何使用此作业中的图形定义。
我认为 find(Start,...) 应该用 r(Start,List) 中列表的所有成员递归调用,但作为 Prolog 的新手(我们只是做了标准的家谱...... .) 我不知道该怎么做。
任何帮助将不胜感激。我知道我没有太多可以开始的事实,但我已经花了半个晚上试图弄清楚一些事情,直到现在我还没有任何线索。
/编辑:
对于初学者,我认为我需要某种基本情况来中止递归。我觉得应该是吧
find([],_,_).
因为我猜想最后的递归调用没有任何东西可以开始,或者
find(_,[],_).
假设当程序完成处理时,定义相邻节点的术语列表应该是空的。
现在是真正的调用。大概是这样的
find(Start,[r(Start,[Adjacent|Restadj])|Rest],Path):-
find(???).
我的问题如下:
-如何让程序使用 r(...) 项中列表的成员作为下一个开始?
-如何检查节点是否已被“访问”/如何从 r 中的特定列表中删除节点
-如何将找到的节点放入路径列表中?简单追加?或者使用 [Path|Start] 之类的东西执行递归调用?
如您所见,它并不多。一些有启发性的问题会很好,因为 Prolog 看起来很有趣,因此学习起来很有趣......
在使用简洁的 PDT-Eclipse 跟踪工具一段时间后,我想我明白了程序在做什么。我现在不明白的是为什么最后一个节点总是丢失。回溯失败后,例如因为 r(c,[b]) 是下一个找到的项,而 memberchk(b,[b]) 失败是因为否定(这就是我所做的 + 所做的)并且没有其他项与 r(c ,X) 可以找到,它从寻找从节点 b 出发的其他可能性开始,该节点在 r(b,[...]) 中留下了相邻节点。但是为什么程序会忘记将节点c放入Path列表中呢?是否有可能做某种 if-then-else 以防万一
member(r(Node, Adjacent), Graph),
member(AdjNode, Adjacent),
\+ memberchk(AdjNode, Seen),
失败,仍然将最后一个节点附加到 Path?
最佳答案
我怀疑这里让您感到困惑的是,您必须从显式数据结构中查找数据,而不是从数据库中获取数据。第一次破解可能看起来像这样:
find(_, _, []).
find(Node, Graph, [Node|Path]) :-
member(r(Node,Adjacent), Graph),
member(AdjNode, Adjacent),
find(AdjNode, Graph, Path).
看看我是如何使用 member/2
从图中查找数据的。但是这个解决方案是不正确的,因为它会循环。一个改进可能是这样的:
find(Node, Graph, Path) :- find(Node, Graph, Path, []).
find(_, _, [], _).
find(Node, Graph, [Node|Path], Seen) :-
member(r(Node, Adjacent), Graph),
member(AdjNode, Adjacent),
\+ memberchk(AdjNode, Seen),
find(AdjNode, Graph, Path, [Node|Seen]).
这个版本与上面的版本基本相同,除了它有一个“已见”列表来跟踪它已经去过的地方。这仍然不会产生您想要的输出,但我认为这足以让您走上正轨。
编辑以响应您的编辑,
For starters, I think I'll need some kind of base case to abort the recursion.
是的。我选择了您的第一个案例,因为我认为您无法在遍历过程中安全地“使用”该图。我想您可以使用 select/3
代替 member/2
并向前传递无此节点的图。这可能是一件有趣的尝试(建议!)。
- How do I make the program use the members of the list in the r(...) term as the next Start?
如前所述,使用 member/2
从图中检索内容。这很有趣,因为您为所需的谓词使用了确切的词。 :)
- How do I check if a node has already been "visited"/ How can I remove a node from a specific list in r
正如我在第二组代码中所演示的,您的辅助谓词有另一个参数,并使用 memberchk/3
或 member/3
。
- How do I put the found nodes into the Path list? Simply append? Or execute the recursive call with something like [Path|Start]?
我进行了递归调用。 append/3
会更昂贵。
编辑:根据 Will 的评论使用 findall/3
,我们可以一次找到所有路径:
all_paths(From, Graph, Paths) :- findall(Path, find(From, Graph, Path), Paths).
你可以像这样调用它:
?- all_paths(a, [r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], AllPaths).
我还没有测试过,但它应该可以工作。
关于path - 在 Prolog 的 Graph 中查找所有可能的路径 w/o loops,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16443833/
我对这两个概念感到困惑:In-graph replication和 Between-graph replication阅读 Replicated training 时在 tensorflow 的官方
我对这两个概念感到困惑:In-graph replication和 Between-graph replication阅读 Replicated training 时在 tensorflow 的官方
我正在尝试使用 https://graph.windows.net/{teantId}/users/[email protected]/thumbnailPhoto?api-version=1.6 访
我正在尝试使用 Graphs.jl 模块从 Julia 中的图中获取子图。我有图,并将其顶点和边存储到列表中,然后我的算法在该列表中移动并删除不属于新子图的节点和边。到这一部分,一切正常,在整个算法之
我是 Arangodb 的新手。我对使用哪个图形 API 感到困惑。我可以在 http://localhost:8529/ url 看到一张图。官方视频讨论了 Gremlin(我也安装了它)。然后就是
截至今天,文档建议使用 Microsoft Graph 而不是 Azure AD Graph API 来访问 Azure AD/B2C 资源。 之前,通过 Azure AD Graph API,我们可
我们希望将 .NET 应用从使用 Azure AD Graph 迁移到 Microsoft Graph API。目前我们正在使用包 Microsoft.WindowsAzure.Configurati
也许我遗漏了什么,但我不知道为什么 GraphQL 的标题中有 graph。 我猜这与 Graph Theory 有关和 graph并且可以看到某种联系,但如果有人能用简单的术语解释它就太好了。 最佳
我正在尝试使用API使用户的Facebook Pages具有已关联的Instagram企业帐户: https://graph.facebook.com/v2.7/me/accounts?field
如何导出我通过调用 GraphPlot 获得的输出的调整大小版本 (或 TreePlot 如果它们产生不同的输出)到 jpg 文件? 目前,我只是调用 Export[file_name, G]在哪里
如何在使用 gremlin 查询创建边缘之前检查边缘是否已存在?如何更新现有边缘而不是删除并重新创建? 最佳答案 我不确定您是否还在寻找答案;然而,简单的答案是 Cosmos DB 在 Gremlin
我使用的是 Xcode 10.2.1 和 macOS Catalina Developer Beta 2。每当我尝试使用内存图调试器时,我都会收到此错误: Memory Graph Debugger:
我正在设置一个机器人以在Facebook页面上自动发布。但是,当我运行脚本时,图形API会引发以下错误: Graph returned an error: (#200) Requires either
如何制定包含非英语字符(例如日耳曼语Umlauts)的Microsoft Graph /myOrganization/users OData查询? 例子: 我的租户中有一个名为“ThomasMülle
我正在寻找发布目标帖子时可以与Facebook Graph API一起使用的国家/州/城市列表。 我在this页面上找到了一个JSON文件,但是该文件无法正确解析,我也怀疑它是否可以用于发布目标,因为
关于 Graph API,帖子的分享数、帖子见解的分享数和页面上显示的分享数不相同。我假设这些代表相同的计数。我的假设错了吗? 来自帖子: https://graph.facebook.com/XXX
我正在尝试访问作为嵌套子站点一部分的列表的项目,如下所示: https://{mytenant}.sharepoint.com/ vendorSiteCollection/ v
我打算开发一个应用程序,但开发人员告诉我每个 IP 每 600 秒有 600 次调用的限制。该应用程序有很多场景,这还不够。有没有办法以某种方式增加限制?或者 Facebook 是否提供任何高级帐户或
我在 Neo4j 中创建了一张伦敦地铁 map 。站点通过 :CONNECTED_TO 关系连接,时间值表示停止之间需要多长时间(目前这些是我为测试输入的随机值)。位于多条线路上的车站每条线路都有一个
我正在尝试拉回所有用户的列表,我的预期结果将是大约 20,000 个用户。 图表似乎将我限制为 1000。 图调用https://graph.microsoft.com/v1.0/users返回 10
我是一名优秀的程序员,十分优秀!