好的,我发布了这个问题,因为这个练习:
我们可以修改Dijkstra算法,通过将最小值改为最大值来解决单源最长路径问题吗？如果是这样,那么证明你的算法正确.如果没有,那么提供一个反例.
对于本练习或与Dijkstra算法相关的所有事情,我假设图中没有负权重.否则,它没有多大意义,因为即使对于最短路径问题,如果存在负边缘,Dijkstra也无法正常工作.
好吧,我的直觉为我解答了:
是的,我认为可以修改.
我只是
distance[w] > distance[v]+weight以distance[w] < distance[v]+weight然后我做了一些研究来验证我的答案.我发现这篇文章:
首先,我认为我的答案是错误的,因为上面的帖子.但我发现上面帖子中的答案可能是错误的.它将单源最长路径问题与最长路径问题混淆.
同样在Bellman-Ford算法的 wiki中,它正确地说:
Bellman-Ford算法在加权有向图中计算单源最短路径.对于仅具有非负边缘权重的图形,更快的Dijkstra算法也解决了这个问题.因此,Bellman-Ford主要用于具有负边缘权重的图形.
所以我认为我的答案是对的,对吧？Dijkstra真的可以成为单源最长路径问题,我的修改也是正确的,对吧？
我正在尝试编写一个递归函数,该函数将包含整数列表的列表作为输入并返回类型([Int],Int)的元组.([INT],智力)
这是一个"棋盘游戏",你提供了一个板:
[[5,4,3,8,6],
[0,2,1,0,7],
[0,1,9,4,3],
[2,3,4,0,9]]
这将是一个4行5列的电路板.列表中的数字是"硬币值".这个棋盘游戏的目标是从列表的顶部到收集硬币的底部.您可以从顶行的任何位置开始向下移动,您可以直接向下或向左或向右对角线.您需要的路径将为您提供最大的总硬币值.
我创建了第一个函数,您输入路径列表[([Int],Int)]并返回具有最大硬币值的路径([Int],Int).
现在我需要创建一个函数来实际生成我将输入到第一个函数中的路径列表.
我知道我将不得不使用递归.我将输入电路板(如上图所示)和起始列.我将不得不取列号,然后创建所有可能路径的列表.如果我从列号开始,我的下一个可能的步骤是位置(在下一行) - 相同的列号,列号-1和列号+1.我需要递归调用它直到我到达底部.
我怎样才能存储这些路径步骤,然后存储所有可能路径的最终列表？
([Int],Int) - [Int]是列表/列号或行中的位置,Int是硬币值.
我是haskell的新手,虽然我明白自己要做什么,但编写代码真的很难.