求解社区项目博弈的一种改进贪婪算法研究

针对社区项目博弈的一般模型,应用贪婪算法求解项目博弈的近似社会最优指派,给出参与者重加权分配机制,证明贪婪算法求得的指派恰好是非合作项目博弈的一个纳什均衡.定义控制参数,给出边际效益后悔值定义,利用后悔值改进了贪婪算法,证明基于后悔值贪婪算法求得的指派是非合作项目博弈的一个纳什均衡.通过数值仿真实验发现,与模拟退火算法比较,贪婪算法能够得到更好的社会效益,而且基于后悔值贪婪算法比贪婪算法得到更好的社会效益.     

贪婪t－相交有限序列族

设Ｆ为有限序列族，对ａ＝（ａ１，ａ２，…，ａｎ）∈Ｆ，ａｉ为整数且０≤ａｉ≤ｓｉ（整数），记ｓ（ａ）＝｛ｊ｜１≤ｊ≤ｎ，ａｊ＞０｝，ｓ（Ｆ）＝｛ｓ（ａ）｜ａ∈Ｆ｝，及Ａ｛１，２，…，ｎ｝时Ｗ（Ａ）＝Пｉ∈Ａｓｉ．称Ｆ为贪婪ｔ－相交，如对任何ａ，ｂ∈Ｆ，至少有ｔ个ａｉ，ｂｉ＞０，且Ｗ（Ａ）≥Ｗ（（｛１，２，…，ｎ｝－Ａ）＋Ｂ）对任何Ａ∈Ｓ（Ｆ）及ＢＡ（｜Ｂ｜＝ｔ－１）成立．本文得到当ｓ１＞ｓ２＞…＞ｓｎ时的最大贪婪ｔ－相交有限序列族．     

资源公平分配的一种贪婪算法

对资源公平分配模型提出了一种简单的贪婪算法，在一定条件下可得到全局最优解且在相当多的情况下所得解都为最优解。该方法效率极高，编程简单，计算量很小，从大量模拟情况来看相当有效。     

有向拟阵与贪婪算法

有向拟阵是拟阵的一种有向情形.本文证明了有向拟阵可用贪婪算法进行刻划.     

有交货时间限制的大规模实用下料问题

研究的是有交货时间限制的单一原材料下料问题(规模较大).对于一维下料问题,本文得到一个有各自交货时间的模型.针对该模型提出一种新的算法:DP贪婪算法.计算结果是总用料800根即可完成需求任务,材料利用率为99.6%.对于二维下料问题,在一维的基础上建立了二维的求解模型,运用我们自己设计的降维思想结合一维的DP贪婪算法,给出解决该模型的算法.计算结果是总用料451块即可完成需求任务,材料利用率位99.2%.算法设计时考虑了普遍的情况,所以算法在解决大多数实际下料问题,特别是大规模下料问题时是切实有效的.     

带准备时间的自由作业排序问题—最坏性能比分析

本文研究了一类自然的排序问题，带准备时间的自由作业排序。在机器台数任意的情况下，证明了一个简单的贪婪算法的最坏性能比不超过２，并猜想该算法的临界为２－１／ｍ，其中ｍ为机器台数。特别当ｍ＝２时，证明了该算法的最坏性能比恰为３／２。     

半序集的碰撞数与分层深度贪婪算法

设Ｐ＝（Ｘ，≤）是一个半序集，本文在关于碰撞数的深度贪婪算法的基础上，直接证明了对任意的Ｐ存在一个最优的ＤＬＧ扩张，给出了ＤＬＧ半序集的定义，并证明了半序集Ｐ是ＤＬＧ半序集的一个充分条件，最后给出了ＤＬＧ扩张算法。     

小波树逼近及其应用

利用“构造性贪婪算法(CGS)”构造目标函数的小波树逼近. 首先定义了一个函数类, 对此函数类中的每个函数, 由CGS生成的分片多项式逼近都具有给定的收敛阶. 其次通过研究所定义函数类的嵌入性质讨论了该函数类和其他已知函数空间的关系. 在小波树逼近领域, 给出了使小波树逼近达到最优收敛阶的一个充分条件. 最后证明, 如果树结构是用CGS生成的, 则相应的小波树逼近具有最优收敛阶.     

卫星运动预测及规避的建模与求解

近年来,随着各国侦查卫星系统的不断完善,有效根据观测数据预测卫星的轨迹,同时建立适当的规避防范措施变得尤为重要·通过研究地面监测站监测的卫星数据及地理信息,提出了一种基于三维坐标系变换的卫星轨迹求解模型,具体建立模型的方法为:建立4种不同的坐标系,通过卫星坐标在4种坐标系中的变换,将地面检测站检测到的卫星数据进行处理,拟合出卫星的六个运动参数,得出卫星运动轨迹方程,并较为精准的预测卫星被观测站观测到的情况,以及任意时刻星下点的经纬度坐标.针对卫星的运动情况,为满足我方军事目标的运动需求,根据新疆地图建立军队行军路线的有向图,然后,在考虑卫星规避的情况下对每条路线进行模拟分析,最终,通过每条路线模拟分析的结果进行比对,得出最优的行军路线.     

基于背包模型的人员优化配置问题

运用背包模型解决油库人员在各岗位的优化配置问题,并运用贪婪算法进行求解.考虑到各人员的总工作时间的均衡性,运用反向排序的方法对原有的贪婪算法进行改进.最后,通过举例对两种算法进行评价.     

快件揽收实时车辆路径问题的一种贪婪算法

快递运营中，调派车辆前往随机发生的快件发件人处上门揽收快件，是一个实时编排行车路径的动态决策过程．本文针对该问题，采用了揽收所有快件的最后时刻最早和行车路径最短的目标，结合车辆揽收快件数平衡的要求，给出一种贪婪算法；然后，对Solomon设计的100个点规模的VRPTW算例做计算试验，分析了车辆数对目标的影响．     

贪婪格点路径的一些性质

设{Xv:v∈Zd}是一族独立同分布的随机变量序列,对Zd上的任意一路径π,定义S(π)=∑v∈πXv,记Mn=maxπ∈Π0(n)S(π),Π0(n)表示从原点出发大小为n的自不相交的路径的全体.论文讨论Mn的性质,得到了类似完全收敛性的结果,即对任意的ε>0,∑∞n=11nPMnn-M>ε<∞.另外还讨论了Xv允许取负值的情形,得到类似的结果,从而推广了Gandolfi和Kesten所研究的贪婪格点路径模型.     

排序的贪婪算法的参数上界

本文研究平行机排序中最著名的贪婪算法─LPT算法的性质．经典排序中机器随时可以开始加工．本文研究机器不都是从开始就可以加工,而是需要一个准备时间,也就是说本文研究各台机器最早可以开工的时间可以不同的同型号平行机（ideaticalParallel）的排序问题,分析LPT算法得到的近似解的参数上界．     

警车配置及巡逻方案研究

以警车的配置与巡逻方案为研究对象,建立了一套警车巡逻模型,并提出巡逻效果显著度及隐藏性的评价标准,分别针对警车初始位置配置与巡逻方案的制定,提出警车配置优化选址的贪婪算法与基于多Agent的警车巡逻方案设计方法,给出了不同情景下的配置及巡逻方案:①在只考虑警车选址配置的情况下,配置19辆警车可以使全市路网警车覆盖率达到92.8%;②在顾及巡逻效果显著性与隐藏性的情况下,配置25辆警车使全市路网在整个巡逻过程中平均警车覆盖率达到90.9%;③在配置10辆警车的情况下,使得全市路网在整个巡逻过程中平均警车覆盖率达到61.5%.     

一类人员招聘问题的算法研究

在人员招聘工作中,通常有招聘总人数和各部门最低录取人数要求等限制。针对给定的限制条件,本文给出了一类人员招聘问题的数学模型。考虑招聘过程中固定指标为0和机动指标为0的特殊情形,分别给出了相应模型的贪婪算法和匈牙利指派算法,在此基础上给出了求解该问题的一种基于指派问题的一般算法,并对相应的算法的最优性给出了证明,算法的复杂度仅为O(m3)。以公务员招聘的实际算例验证,模型能合理地满足招聘单位的实际需求。     

Besov类上的贪婪算法

我们讨论了Besov类MBpr,θ上的相应于张量积小波词典Wd的最佳m-项 逼近问题,证明了其最佳m-项逼近的阶可以通过简单的贪婪算法得到.     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

需求信息更新时单一仓储中心动态选择策略

研究了需求波动情形下,如何动态选择第三方仓储中心以减少物流成本的问题。首先将需求信息完全预知的单一中心选择问题转化为特殊的最短路问题,并设计了相应的动态规划算法。其次,针对需求波动难以预测的在线问题,从在线策略和竞争分析的角度,设计了简单贪婪策略,并证明了该策略在一般情形下不具有竞争性;而当任一阶段的总运输成本与仓储中心转换成本之比都大于在一定数值时,简单贪婪策略则具备竞争性,并能够有效的控制成本。最后,通过算例验证了动态规划算法与简单贪婪策略的可行性与有效性。     

一类带时间窗车辆分配问题的贪婪算法

本文对一类带时间窗的车辆分配问题进行了分析,引入了车辆任务的概念,并将问题转化为车辆与车辆任务的匹配问题,同时制订了运输任务选择和车辆选择的贪婪策略,并在此基础上设计了车辆分配问题的贪婪算法,最后通过实例验证了算法的有效性。     

求解旅行商问题的一种改进粒子群算法

本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。