浅析区域填充算法

区域填充算法广泛应用于各个领域,经典的区域填充算法存在若干问题,在分析了两种传统区域填充算法的原理的基础上,阐述了两种改进的区域填充算法。     

基于蚁群优化的物流调度算法研究

物流过程的调度是一个组合优化问题。通过对几种经典物件分配算法的比较分析，提出了基于蚁群的物件优化渊度算法，实现物流过程中物件的动态分配。蚁群共同测试不同的组合，并选择一个优化的解决疗案，采用该方案能够按时交付更多的订单，同时也使订单的延迟变化很小。比较了蚁群算法与其它几种调度方法的效率，结果表明蚁群算法在物流过程中填有良好的性能。     

基于含神经元网络的智能控制系统和填充函数法的混合优化算法

针对反馈控制系统优化算法和填充函数法的早熟收敛问题,提出了一种基于含神经元网络的智能控制系统和填充函数法的混合优化算法(MPIDNN-FF)。该算法结合了神经元网络、智能控制系统优化算法和填充函数法。该算法在搜索过程中不但可以在线实时地修正PID等参数,而且不容易陷入局部最优点,从而得到的全局最优值更加精确。     

复杂多边形区域边界搜索算法的研究

首先分析了经典的区域填充算法的两个问题。在此基础上，借鉴种子填充算法的一些思想，提出了一种针对任意复杂多边形区域的搜索算法，该算法克服了传统算法的一些缺陷，可以满足实际编程需要。     

一种高能效的Keccak算法ASIC设计与实现

设计并实现了能同时支持SHA3四种模式的Keccak算法完整硬件电路。在对海绵结构和Keccak算法详细分析的基础上,将电路结构划分为并行执行的填充模块和置换模块,减少了算法执行的时钟周期。在所设计的Keccak算法硬件电路基础上,从能效角度对三种现有置换函数实现结构进行了比较分析。在65 nm工艺库下进行综合, SHA3-256标准下单位面积性能达到0.55 Mbps/gate,相较现有结构能效提高了约52%。     

一种对LRFU置换策略的自适应改进

数据库缓冲区页面置换算法对磁盘数据库的性能有着重要的影响,页面置换算法主要有基于访问时间的置换策略、基于访问次数的置换策略、两者结合的置换策略等。LRFU算法是一系列结合LRU和LFU置换策略的置换算法,很好地实现了两种置换策略的结合,但却没有给出一种在不同的应用场景中进行动态调整的机制。提出了一种对LRFU算法进行动态调整的方法,模拟测试发现改进的LRFU算法都不同程度地提高了缓冲区命中率。     

银欣夜莺SST-ST45NF

对于经常被电源风扇噪音困扰的发烧级玩家来说，银欣夜莺SST-ST45NF电源的出现无疑有一种看到希望的感觉。由于仅靠散热片就解决了内部的散热问题。SST-ST45NF电大 高亮这初就没有考虑使用风扇，     

小波域图像块修复

描述了一种在小波域中分块图像修复的新算法.该算法将修复过程分为两个步骤;首先寻找小波细节系数,用小波系数的能量来确定每一个图像梯度向量的大小;然后使用图像梯度向量来决定修复区中的哪个块应该首先被填充,使用基于小波域的纹理合成方法来具体填充这个块.连续迭代执行这两个步骤,直到修复区完全被填满.实验结果表明该算法的有效性.     

一种基于随机序列填充的信息隐藏方法

由于计算机技术的飞速发展使得解密技术也得到很大发展,它已对传统加密方法构成威胁。因此,文章提出了一种基于随机序列填充的信息隐藏方法,该方法中使用黄金分割算法计算出被隐藏信息的大小,然后使用填充算法将秘密信息隐藏在随机序列中。该方法有效提高了信息的安全性、可靠性,有着广泛的应用前景。     

一种改进的种子填充算法

对种子填充算法进行了分析和讨论,并提出一种改进的种子填充算法。由于只记录搜索的路径,并且增加一个空间很小的辅栈,改进的种子填充算法无论是时间还是空间效率都优于传统算法。     

互联网信息组织和规划中的带拒绝装箱问题

讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子，给定一个物品集，每个物品有两个参数：长度和罚值．物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子，则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计，它可用于分枝定界法求最优解．由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法，其绝对性能比为2；同时给出一个在线算法，其绝对性能比不超过3，渐近性能比为2，还对算法性能比的下界进行了讨论．     

Online Removable Square Packing

The online removable square packing problem is a two-dimen-sional version of the online removable Knapsack problem. For a sequence of squares with side length at most 1, we are requested to pack a subset of them into a unit square bin in an online fashion where the online player can decide whether to take the current square or not and which squares currently in the unit square to remove. The goal is to maximize the total packed area. Our results include: (i) No online algorithm can achieve a better competitive ratio than . (ii) The matching upper bound is achieved by a relatively simple online algorithm if repacking is allowed. (iii) Without repacking, we can achieve an upper bound of 3 by using the concept of bricks of Januszewski and Lassak. (iv) The offline version of the problem admits a PTAS. Research supported by NSFC (10231060).     

A型变尺寸装箱问题之模型及算法研究

作为对经典一维装箱问题的推广,提出一种A型变尺寸装箱问题（A-shaped Variable-sized BinPacking Problem,简称A SVBP）,即在物品的装箱过程中,每样物品有高度和横截面积两个参数,并且箱子的大小不一。该问题在文件系统管理和日常生活中的运输等问题中有着广泛的应用背景。把装箱问题的经典算法以及遗传算法推广到A型变尺寸装箱问题,实验结果表明：按照本文提出的求解模式,离线情况下求解A型变尺寸装箱问题最终结果的质量取决于预先求解其退化为经典装箱问题时的算法,求解物品装箱序列时用首次适应混合遗传算法比用Next Fit算法、First Fit算法、Best Fit算法最终得到的结果要好。     

Average Case Analysis of Bounded Space Bin Packing Algorithms

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.     

多约束的箱子大小可变的装箱问题

作为经典装箱问题的扩展,带有约束条件的装箱问题有着很强的应用背景。从钢铁公司板坯入库引发的装箱问题中,物品除了重量这一参数,还引入了特性和种类等参数。将板坯入库归结为多约束的箱子大小可变的装箱问题后,建立了数学模型,将经典装箱算法进行了推广,构建了新的启发式算法A,它对输入物品按特性进行预处理,再进行装箱。理论分析了NFD,FFD,算法A的最坏情况的性能,并对这三种算法进行了数值模拟,得出在相关特性均匀分布下,算法A的性能最好。     

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题.设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果.     

Asymptotic fully polynomial approximation schemes for variants of open-end bin packing

We consider three variants of the open-end bin packing problem. Such variants of bin packing allow the total size of items packed into a bin to exceed the capacity of a bin, provided that a removal of the last item assigned to a bin would bring the contents of the bin below the capacity. In the first variant, this last item is the minimum sized item in the bin, that is, each bin must satisfy the property that the removal of any item should bring the total size of items in the bin below 1. The next variant (which is also known as lazy bin covering is similar to the first one, but in addition to the first condition, all bins (expect for possibly one bin) must contain a total size of items of at least 1. We show that these two problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). Moreover, they turn out to be equivalent. We briefly discuss a third variant, where the input items are totally ordered, and the removal of the maximum indexed item should bring the total size of items in the bin below 1, and show that this variant is strongly NP-hard.     

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

一种自适应优化松弛量的装箱算法

装箱问题是物流系统和生产系统中的一个经典而重要的数学优化问题。装箱指把一系列物品按照一定顺序放进具有固定容量的箱子中,并最小化所使用的箱子数量,以最大限度地获取装箱问题的近似最优解。然而,现有的装箱算法存在明显的缺陷。遗传算法计算量过大,甚至无法求出所需解,启发式算法无法处理极端值问题,而现有的改进算法即使在引入松弛量的情况下,也极易陷入局部最小值。文中提出的Adaptive-MBS算法采用自适应权重来改进原有方法,即允许方法有一定的松弛量,并具有捕捉物体样本空间随时间变化的直觉,以使用更好的松弛量策略来装箱。Adaptive-MBS算法首先以当前箱子为中心,使用Adaptive_Search搜索算法迭代找到适合箱子容量的集合中所有物体的子集,Adaptive_Search搜索算法不要求完全装满箱子,而是允许箱子具有一定的松弛量,在训练过程中根据当前状态的变化,实现自动地调整松弛量,在找到完全填满箱子的子集后迭代至下轮搜索直至遍历完成。该方法不易陷入局部最优,具有较强的发现全局最优解的能力。文中使用装箱问题中经典的BINDATA和SCH_WAE数据集进行实验,结果表明,数据集中多达991例问题可以通过Adaptive-MBS算法得到最优解。在没有求解出最优解的实例上,所提算法也在所有对比算法上具有最低的相对偏移量百分比。数值实验结果表明,相较于其他经典的装箱算法,Adaptive-MBS算法有更好的效果,其收敛速度也显著优于其他算法。     

Two-dimensional on-line bin packing problem with rotatable items

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is “rotatable” by $\text{90°}$. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565.