gpt4 book ai didi

algorithm - 动态0/1背包总是一个玩笑吗?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:35:58 25 4
gpt4 key购买 nike

我已经获得了证明,该证据会使关于0/1背包问题的普遍想法蒙羞,我真的很难说服我自己是对的,因为我找不到可以支持我的主张的任何东西,因此我将首先陈述我的主张,然后证明它们,我希望任何人尝试进一步证实我的主张或取消其主张。任何合作表示赞赏。
断言:

  • 用于解决背包问题的bnb(分支和边界)算法的大小是,而不是,与K(背包的容量)无关。
  • bnb树完整空间的大小始终为O(NK)的,始终为,其中N为项数,而不是 O(2 ^ N)
  • 在时间和空间上,bnb算法总是优于标准动态编程方法。

  • 前提条件:bnb算法容易产生无效节点(如果剩余容量小于当前项目的权重,我们将不对其进行扩展。此外,bnb算法以深度优先的方式进行。
    草率证明:
    这是解决背包问题的递归公式:
    值(i,k)=最大值(值(i-1,k),值(n-1,k权重(i))+值(i)
    但是如果k 现在想象一下这个例子:
    K = 9
    N = 3
    V W:
    5 4
    6 5
    3 2
    现在,这里是此问题的动态解决方案和表:
    enter image description here
    现在想象一下,不管这是否是一个好主意,我们都只想通过内存来使用递归公式,而不要通过表格来实现此目的,而要使用诸如 map /字典或简单数组的形式来存储访问的单元格。为了使用内存来解决此问题,我们应该解决表示的单元格:
    enter image description here
    现在,这就像我们使用bnb方法获得的树:
    enter image description here
    ,现在用于草率的证明:
  • 记忆化和bnb树具有相同数量的节点
  • 内存节点取决于表大小
  • 表大小取决于N和K
  • 因此 bnb并不独立于K
  • 内存空间受NK限制,即O(NK)
  • 因此, bnb树的完整空间(或如果我们以广度优先的方式进行bnb的空间)始终为O(NK)而不是O(N ^ 2),因为整棵树都不会被构建并且就像妈妈一样。
  • 记忆化比标准动态编程具有更好的空间。
  • bnb的空间比动态编程要好(即使先广度执行)
  • 简单的bnb无需放松(并且仅消除不可行的节点)将比内存有更好的时间(内存必须在查找表中进行搜索,即使查找可以忽略,它们仍然是相同的。)
  • 如果我们忽略备忘录的查找搜索,则它比动态搜索要好。
  • 因此, bnb算法在时间和空间上总是比动态更好。

  • 问题:
    如果无论如何我的证明是正确的,将会出现一些有趣的问题:
  • 为什么要打扰动态编程?以我的经验,您可以在dp背包中做的最好的事情是拥有最后两列,如果从下至上填充它,您可以将其进一步改进为一列,并且它具有O(K)的空间,但仍然不能(如果以上说法正确)击败了bnb方法。
  • 如果我们将bnb与放松修剪(就时间而言)整合在一起,我们还能说bnb更好吗?

  • ps:很抱歉,很长很长时间!
    编辑:
    由于其中两个答案都集中在内存上,因此我只想澄清一下,我并没有完全专注于这个!我只是将内存作为一种证明我的主张的技术。我的主要重点是分支定界技术与动态编程,这是另一个问题的完整示例,通过bnb +松弛解决(来源:Coursera-离散优化):
    enter image description here

    最佳答案

    我认为从您的角度出发存在一个误解,那就是动态编程是背包问题的最新解决方案。该算法是在大学中教授的,因为它是动态编程和伪多项式时间算法的简单而出色的示例。

    我没有该领域的专业知识,也不知道现在有什么最新技术,但是分支定界方法已经使用了相当长的时间来解决背包问题:Knapsak-Problems by Martello and Toth这本书已经很漂亮了较旧,但对分支绑定(bind)的处理相当广泛。

    不过,从您的角度来看,这仍然是一个很好的观察,分支和绑定(bind)方法可以用于背包-las,您出生得太晚了,所以第一个没有这个想法的人就知道了:)

    您的证明中有一些我不理解的地方,在我看来还需要更多解释:

  • 您需要内存,否则您的树将具有O(2^N)节点(显然会有这种情况,否则背包将不会具有NP难度)。我在您的证明中看不到任何东西,可以确保内存存储/计算步骤少于O(NK)
  • 动态编程仅需要O(K)内存空间,因此我不明白为什么您可以宣称“bnb算法在时间和空间上总是比动态更好”。

  • 也许您的说法是正确的,但我现在无法以证明的方式来了解它。

    另一个问题是“更好”的定义。如果分支定界方法对于大多数问题或常见问题更好,还是必须对最坏情况(在现实生活中没有任何作用)更好,那么它是更好的选择吗?

    我链接到的这本书也对算法的运行时间进行了一些比较。基于动态编程的算法(显然比在学校教授的算法更复杂)对于某些问题甚至更好-请参见第2.10.1节。完全是个笑话!

    关于algorithm - 动态0/1背包总是一个玩笑吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45358299/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com