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

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

取消只看楼主收藏回复

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


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


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


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


        IP属地:内蒙古8楼2020-02-14 15:40
        收起回复