小编Sus*_*sie的帖子

这不是一个家庭作业问题,而是来自我正在研究的项目的一些问题.上图是一组盒子的包装配置,其中A,B,C,D在第一层上,E,F,G在第二层上.问题是如果这些方框是以随机顺序给出的,那么这些方框可以放在给定配置中的概率是多少？

放置的唯一条件是所有盒子需要从上到下放置,放置后不能移动.因此,不允许在现有盒子或浮动位置下滑动,但是可以为同一层上的盒子节省空间.例如,E只能在A和B已经到位时放置.如果处理顺序是AEB ...那么它不能被放置在指定的配置中,如果处理顺序是ACBE ...则可以正确放置E.

更具体的描述是将打包配置转换为一组依赖关系或先决条件.第一层上的ABCD具有0个依赖关系,而E的依赖关系是{A和B},F是{B和C},G是{C和D},相应的依赖关系必须在E或F或G发生之前发生.虽然它不适用于这个问题,但在某些问题中,依赖关系也可以是"或"关系而不是"和".

我想知道解决这个问题的一般确定性算法是什么,还是这类问题？我能想到的一种方法是以随机顺序生成A,B,C,D,E,F,G 10,000次,并且对于每个订单检查是否在调用每个元素时发生了相应的先决条件.然而,这种天真的想法是耗时的,并且不能产生确切的概率(我相信这个问题的答案是基于我实施的这种天真算法的1/18).

建议将不胜感激!

我有一个2D numpy数组,我希望获得每个2d滚动窗口中包含的最大值,该值从左到右,从上到下,每次滚动一行或一列.最天真的方法是遍历所有滚动窗口并获得此滚动窗口中包含的所有值的最大值.我在下面写下了这个方法:

import numpy as np
shape=(1050,300)
window_size=(120,60)
a = np.arange(shape[1]*shape[0]).reshape(shape[1],shape[0])
max_Map=np.full((shape[1]-window_size[1]+1,shape[0]-window_size[0]+1),0,dtype='uint32')

for i in range(shape[1]-window_size[1]+1):
    for j in range(shape[0]-window_size[0]+1):
        window_max=np.max(a[i:i+window_size[1],j:j+window_size[0]])
        max_Map[i][j]=window_max

但这非常低效,因为每次滑动之间只有2行(或2列)发生了变化,但我的代码没有考虑2个连续滚动窗口之间的任何相关性.我能想到的一个改进是每个滑动窗口(假设水平滚动)我将计算最左列的最大值和剩余列的最大值,并将2个值的最大值作为当前窗口最大值.对于下一个滚动窗口,最大值将是新添加的列和之前剩余的列的最大值...但我仍然不认为这是优化的...

我真的很感激,如果有人能指出我正确的方向,我觉得这应该是一个研究得很好的问题,但我无法在任何地方找到解决方案......提前谢谢!