神都夜行录吧 关注:222,110贴子:4,033,538
  • 23回复贴,共1

关于点灯活动的碎片数【学术?

只看楼主收藏回复

规则我明白了,我也看到你们说的模拟结果了。这里只是纯粹的请教一下,这是一个np问题吗?是的话,随机算法得到的近似解可以达到多少?
问题1:按照规则,最多能获得多少碎片?(不考虑每个规则奖励的不同)
问题2:在已经翻开牌的前提下(截至发帖时间,已经翻开4张),问题1的解?


IP属地:内蒙古1楼2020-02-14 14:53回复
    我看到的说法“最少可获得27片”这是可证明的吗?
    “期望值在33片“是完全随机的多次模拟得到的结论吗?


    IP属地:内蒙古2楼2020-02-14 15:04
    收起回复
      大哥,我就玩个游戏……


      IP属地:内蒙古来自iPhone客户端3楼2020-02-14 15:11
      回复
        不知道可不可以用dijkstra最短路径算法


        IP属地:浙江4楼2020-02-14 15:13
        收起回复
          有志于研究此问题的欢迎讨论。只是吃瓜的话……欢迎捧场?


          IP属地:内蒙古5楼2020-02-14 15:14
          回复
            医学生来这里集合一下,一起恰瓜


            来自Android客户端6楼2020-02-14 15:19
            收起回复
              @🍁风灵草🍁 要不要假期动动脑


              来自iPhone客户端7楼2020-02-14 15:34
              收起回复
                我先抛砖引玉从分析暴搜入手。81个格子如果全排列的话是81!但这是不可能的因为没有考虑到对称性。上下左右的对称性是显而易见的,但其实不止,比如我将第4列与第5列整体互换,达成的规则数一定不会变。但是第3列与第4列互换就不行。那么行互换应该是(3!)^3=216,同理列互换也是216


                IP属地:内蒙古8楼2020-02-14 15:40
                收起回复
                  谁也不知道有没有保底啊


                  IP属地:上海来自iPhone客户端9楼2020-02-14 15:48
                  回复
                    感觉动态规划是解不了,不能分成子问题也没有递推关系。还是得穷举,不知道能不能找到穷举的


                    IP属地:浙江来自iPhone客户端10楼2020-02-14 16:06
                    回复