懒惰地将结结合起来进行一维动态规划

Question

几年前我参加了算法课程,我们给出了以下问题(或类似的问题):

有一个n楼层的楼层,电梯一次只能上2层楼,一次只能下3层楼.使用动态编程编写一个函数,该函数将计算电梯从一层i到另一层所需的步数j.

使用有状态方法显然很容易,你创建一个数组n个元素,并用值填充它.你甚至可以使用一种技术上非有状态的方法,它涉及累积结果递归传递它.我的问题是如何通过使用延迟评估和打结来以非有状态的方式执行此操作.

---

我想我已经设计了正确的数学公式:

where i+2和i-3是否在允许的值范围内.

不幸的是我不能让它终止.如果我i+2首先放置案例然后选择一个偶数楼层,我可以让它来评估目标等级以下的均匀楼层,但就是这样.我怀疑它直接射向最高的平坦地板,其他一切,下降3级,然后重复,永远在最顶层的几层之间振荡.

所以它可能以深度优先的方式探索无限空间(或有限但有环).我无法想象如何以广泛的方式探索这个空间而不使用其间有效模仿状态方法的大量数据结构.

---

虽然这个简单的问题令人失望,但我怀疑在一维中看到了一个解决方案,我可能能够使它适用于问题的二维变化.

---

编辑:许多答案试图以不同的方式解决问题.问题本身对我来说并不感兴趣,问题在于使用的方法.Chaosmatter创建一个minimal可以比较潜在无限数字的函数的方法可能是朝着正确方向迈出的一步.不幸的是,如果我尝试创建一个表示100层楼的列表,结果计算时间太长,因为子问题的解决方案不会被重用.

我尝试使用自引用数据结构,但它没有终止,存在某种无限循环.我会发布我的代码,这样你就可以理解我的目标.如果有人能够在自引用数据结构上使用动态编程实际解决问题,我会改变接受的答案,使用懒惰来避免多次计算事物.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

您可以看到如何1 + levels !! i尝试引用先前计算的结果以及如何filter (\n -> n >= 0 && n <= 10) [x+2,x-3]尝试将值限制i为有效值.正如我所说的,这并不实际工作,它只是证明了方法由我希望看到这个问题就解决了.解决它的其他方法对我来说并不有意思.

Answer 1

问题是min需要完全评估两个调用f,所以如果其中一个无限循环min将永远不会返回.因此,您必须创建一个新类型,编码返回的数字f为零或零的后继.

data Natural = Next Natural 
             | Zero

toNum :: Num n => Natural -> n
toNum Zero     = 0
toNum (Next n) = 1 + (toNum n)

minimal :: Natural -> Natural -> Natural
minimal Zero _            = Zero
minimal _ Zero            = Zero
minimal (Next a) (Next b) = Next $ minimal a b

f i j | i == j = Zero
      | otherwise = Next $ minimal (f l j) (f r j)
      where l = i + 2
            r = i - 3

这段代码实际上有效.

Answer 2

既然你试图在两个方面解决这个问题,并且除了描述的问题之外的其他问题,让我们探索一些更通用的解决方案.我们正在尝试解决有向图上的最短路径问题.

我们对图形的表示当前是这样的a -> [a],其中函数返回可从输入到达的顶点.任何实现还需要我们可以比较以查看两个顶点是否相同,因此我们需要Eq a.

下图是有问题的,并且介绍了解决问题的几乎所有困难:

problematic 1 = [2]
problematic 2 = [3]
problematic 3 = [2]
problematic 4 = []

当试图从1到4时,必须检测到一个涉及2和3的循环,以确定没有从1到4的路径.

广度优先搜索

如果应用于有限图的一般问题,所提出的算法将具有在时间和空间上无限制的最坏情况性能.我们可以修改他的解决方案,通过添加循环检测来攻击仅包含有限路径和有限循环的图形的一般问题.他的原始解决方案和这个修改都会在无限图中找到有限路径,但两者都无法可靠地确定无限图中两个顶点之间没有路径.

acyclicPaths :: (Eq a) => (a->[a]) -> a -> a -> [[a]]
acyclicPaths steps i j = map (tail . reverse) . filter ((== j).head) $ queue
  where
    queue = [[i]] ++ gen 1 queue
    gen d _ | d <= 0 = []
    gen d (visited:t) = let r = filter ((flip notElem) visited) . steps . head $ visited 
                        in map (:visited) r ++ gen (d+length r-1) t

shortestPath :: (Eq a) => (a->[a]) -> a -> a -> Maybe [a]
shortestPath succs i j = listToMaybe (acyclicPaths succs i j)

重复使用stepWill的答案中的函数作为示例问题的定义,我们可以得到11层楼的4层到5层的最短路径长度fmap length $ shortestPath (step 11) 4 5.这回来了Just 3.

让我们考虑一个带有v顶点和e边的有限图.具有v个顶点和e个边的图可以通过大小为n~O(v + e)的输入来描述.该算法的最坏情况图是有一个无法到达的顶点,j其余的顶点和边用于创建从最开始的最大数量的非循环路径i.这可能类似于一个包含所有不是顶点的集团,i或者是j从i每个顶点到另一个顶点的顶点j.具有e边的集团中的顶点数是O(e ^(1/2)),因此该图具有e~O(n),v~O(n ^(1/2)).在确定j无法访问之前,此图将具有要探索的O((n ^(1/2))!)路径.

在这种情况下,此函数所需的内存为O((n ^(1/2))!),因为它只需要每个路径的队列不断增加.

对于这种情况,该函数所需的时间是O((n ^(1/2))!*n ^(1/2)).每次扩展路径时,都必须检查新节点是否已经在路径中,这需要O(v)~O(n ^(1/2))时间.如果我们有Ord a一个Set a或类似的结构来存储被访问的顶点,这可以改进为O(log(n ^(1/2))).

对于非有限的图形,这个功能应该只是不能确切地终止时不存在从有限的路径i来j但确实存在,从一个非限定路径i来j.

动态编程

动态编程解决方案不会以相同的方式推广; 让我们探讨一下原因.

首先,我们将调整chaosmasttter的解决方案,使其具有与广度优先搜索解决方案相同的界面:

instance Show Natural where
    show = show . toNum 

infinity = Next infinity

shortestPath' :: (Eq a) => (a->[a]) -> a -> a -> Natural
shortestPath' steps i j = go i
    where
        go i | i == j = Zero
             | otherwise = Next . foldr minimal infinity . map go . steps $ i

这很适合电梯问题,shortestPath' (step 11) 4 5是3.不幸的是,对于我们的问题,shortestPath' problematic 1 4溢出堆栈.如果我们为Natural数字添加更多代码:

fromInt :: Int -> Natural
fromInt x = (iterate Next Zero) !! x    

instance Eq Natural where
    Zero == Zero         = True
    (Next a) == (Next b) = a == b
    _ == _ = False

instance Ord Natural where
    compare Zero Zero         = EQ
    compare Zero _            = LT
    compare _ Zero            = GT
    compare (Next a) (Next b) = compare a b

我们可以问最短路径是否短于某个上限.在我看来,这真实地展示了懒惰评估所发生的事情.problematic 1 4 < fromInt 100是False和problematic 1 4 > fromInt 100是True.

接下来,为了探索动态编程,我们需要介绍一些动态编程.由于我们将构建一个解决所有子问题的表,我们需要知道顶点可以采用的可能值.这给我们一个稍微不同的界面:

shortestPath'' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> Natural
shortestPath'' steps bounds i j = go i
    where
        go i = lookupTable ! i
        lookupTable = buildTable bounds go2
        go2 i | i == j = Zero
              | otherwise = Next . foldr minimal infinity . map go . steps $ i

-- A utility function that makes memoizing things easier
buildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i e
buildTable bounds f = array bounds . map (\x -> (x, f x)) $ range bounds

我们可以像shortestPath'' (step 11) (1,11) 4 5或那样使用它shortestPath'' problematic (1,4) 1 4 < fromInt 100.这仍然无法检测周期......

动态编程和循环检测

循环检测对于动态编程是有问题的,因为当从不同路径接近子问题时子问题不同.考虑我们problematic问题的变体.

problematic' 1 = [2, 3]
problematic' 2 = [3]
problematic' 3 = [2]
problematic' 4 = []

如果我们试图从获取1到4,我们有两个选择:

• 去2和走的最短路径2,以4
• 去3和走的最短路径3,以4

如果我们选择探索2,我们将面临以下选择:

• 去3和走的最短路径3,以4

我们希望以最短路径的两个探索从结合3到4到表中同一条目.如果我们想避免周期,这实际上是一些更微妙的东西.我们遇到的问题确实是:

• 去2和走的最短路径2,以4不参观1
• 去3和走的最短路径3,以4不参观1

选择后 2

• 去3和走的最短路径3,以4不登陆1或2

有关如何从获得这两个问题3,以4有两个略有不同的答案.它们是两个不同的子问题,不能适合表中的相同位置.回答第一个问题最终需要确定你不能去4的2.回答第二个问题很简单.

我们可以为每个可能的先前访问过的顶点组制作一堆表,但这听起来效率不高.我几乎让自己相信,只使用懒惰,我们无法将触及能力作为动态编程问题.

广度优先搜索redux

在研究具有可达性或周期检测的动态编程解决方案时,我意识到一旦我们在选项中看到一个节点,访问该节点的后续路径就不会是最佳的,无论我们是否遵循该节点.如果我们重新考虑problematic':

如果我们试图从获取1到4,我们有两个选择:

• 去2,并采取从最短路径2到4无需访问1,2或3
• 去3,并采取从最短路径3到4无需访问1,2或3

这为我们提供了一种算法,可以很容易地找到最短路径的长度:

-- Vertices first reachable in each generation
generations :: (Ord a) => (a->[a]) -> a -> [Set.Set a]
generations steps i = takeWhile (not . Set.null) $ Set.singleton i: go (Set.singleton i) (Set.singleton i)
    where go seen previouslyNovel = let reachable = Set.fromList (Set.toList previouslyNovel >>= steps)
                                        novel = reachable `Set.difference` seen
                                        nowSeen = reachable `Set.union` seen
                                    in novel:go nowSeen novel

lengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe Int
lengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i

正如所料,lengthShortestPath (step 11) 4 5是Just 3和lengthShortestPath problematic 1 4是Nothing.

在最坏的情况下,generations需要空间为O(v*log v),时间为O(v*e*log v).