贪心策略

摘要： 城市内河周边环境常常受到破坏和污染,如何有效地对河道进行监测逐渐引起公众、政府和学术界的关注。目前传统的监测方式存在成本高昂、覆盖面不足等缺陷。鉴于智能移动设备的不断普及,文中提出利用群智感知来高效监测河道环境的新思路。该问题可描述为假定每一河段附近有c个位置点可监测该河段,然后根据大量用户的移动轨迹选择出其中r个用户来共同完成s个时段对所有河段的监测。文中规定用户数r越小,监测成本越少。设计了逐步贪心策略、全局贪心策略和整数规划策略用于解决该问题,即选择最少参与者达到“s时长-c范围-r用户”的监测目标。将上述策略应用于福州市台江区部分河道的环境监测,实验结果表明,上述策略均能获得比随机策略更好的解,其中整数规划策略的表现最好。但是,随着问题规模的变大,解决小规模整数规划的隐枚举算法会出现无法求解的情况,因此提出了基于贪心初始化的离散粒子群算法(Greedy Initialization-Discrete Particle Swarm Optimization,GI-DPSO)。虽然该算法可以求解大规模整数规划,但计算费时。综合考虑监测成本和计算代价,建议对小规模问题采用整数规划策略,对大规模问题采用全局贪心策略。

摘要： 为了更有效地求解0-1背包问题,在基本Jaya算法特点的基础上,提出一种带惯性权重的Jaya算法.算法在二进制编码后采用贪心策略对不可行解修复同时优化可行解,并引入线性递减的惯性权重来平衡迭代过程中全局搜索和局部搜索的关系,在算法迭代初期增强全局搜索的能力,在迭代后期提高搜索的精度.仿真实验表明,提出算法与其他三种算法相比在求解0-1背包问题上具有更好的寻优效果.

摘要： 在考虑加工设备对钢筋影响的基础上,建立了基于梯度提升决策树及整数规划的钢筋一维下料优化模型,以提高原材利用率;并在此基础上,结合课题组自主研发的智能分拣装置,建立了基于动态贪心策略的分拣优化模型,以促进钢筋优化在生产现场的良好应用,并提升生产效率。工程实例分析表明,优化切割方案原材利用率得到有效提升,且相较传统优化算法,下料优化方法寻优效率及稳定性更好;分拣优化减轻了现场人员工作强度,并大幅提升了分拣效率。该方法实现了对加工成本、质量、效率的有效保证,为工程中的一维下料钢筋生产提供了一条新的途径。

摘要： 针对大数据环境下并行MRPrePost频繁项集挖掘算法中存在计算节点负载不均衡,N-list合并效率低以及冗余搜索等问题,提出了基于N-list结构的混合并行频繁项集挖掘算法HP-FIMBN。首先,设计负载量估计函数(LE)来计算出频繁1项集F-list中每一项的负载量,同时提出基于贪心策略的分组方法(GM-GS)将F-list中的每一项根据其负载量进行均匀分组,既解决了数据划分中计算节点负载不均衡的问题,又降低了集群中各节点上子PPC-Tree树的规模;其次,提出预先放弃策略(EAS),该策略不仅能有效避免合并过程中的无效计算,而且不需要遍历初始N-list结构就能得到最终的N-list,极大地提高了N-list结构的合并效率;最后,采用集合枚举树作为搜索空间,并提出超集等价剪枝策略(SES)来避免挖掘过程中的冗余搜索,生成最终的挖掘结果。实验结果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果。

摘要： 为全面描述联合作战用频规划问题,引入多目标优化理论,以干扰冲突最少、需求满足最高和邻频风险最低作为优化目标建立了多目标的联合作战用频规划模型,并提出一种求解联合作战用频规划问题的非支配排序蚁群算法.在蚁群初始化阶段使用带贪心策略的爬山算法获取次优解集合以提升蚁群前期收敛速度,并运用社团检测机制将用频装备分簇以减少电磁干扰分析的计算复杂度从而加快算法进程.同时,在算法每次迭代中对得到的用频规划方案执行调度改进操作,并自适应调整信息素挥发系数等参数,以提升算法全局优化性能.仿真实验验证了模型的有效性,并通过反转世代距离与超体积指标证明了算法在收敛性、分布性与收敛速度上的优越性.

摘要： 针对直角坐标机器人在动态分拣过程中顺序规划算法效率低下的问题,提出了一种适用于机器人连续分拣作业的改进贪心策略规划算法。建立直角坐标机器人的运动学模型,确保物体被准确拾取。设计时间窗口,对传送带上的连续运动物体进行区域划分,并应用贪心策略对同一时间窗口内的物体规划分拣顺序。考虑物体存在分拣遗漏的风险,设计评价函数对贪心策略进行改进,增强了所提算法的实用性。设计模拟程序对所提算法进行仿真,并利用搭建的机器人平台开展分拣实验,验证了算法的可行性和有效性。实验表明:所提算法可在机器人实际分拣作业中规划出有效的分拣路径,平均分拣距离和分拣时间均小于顺序规划算法,提高了机器人对平面随机分布的连续运动物体的分拣效率,实时性好,实用性强,对机器人动态分拣场景下的分拣路径优化研究具有一定的指导意义。

摘要： 随着第五代移动通信技术(5G)的发展以及网络架构的演进,网络覆盖的分析以及优化不仅需要考虑基站天馈系统的链路预算,而且需要结合基站覆盖区域的时空特性,从而设计出更精确的覆盖优化方案。文章提出了一种基于Q学习的自适应网络覆盖优化算法,首先采用一种基于数据挖掘的网络覆盖预测模型,通过小区天线参数的配置预测出接入终端的覆盖情况,并基于真实数据验证模型预测的准确性;其次,改进强化学习中智能体的动作选择策略,根据覆盖率设置各小区不同的优化优先级,结合贪心策略,选择出需要优化的小区及其优化参数值,有效地降低了迭代过程中陷入局部最优的概率。仿真结果表明,文章所提算法可提高优化过程收敛速度,同时对网络覆盖率的提升幅度可达到20%。

摘要： TSP问题的应用十分广泛,而传统的遗传算法在求解TSP问题时存在求解精度低和时间长等不足。针对该问题提出了一种改进的分布式并行遗传算法用来求解大规模TSP问题。改进遗传算法使父代染色体进行顺序交叉、就近变异和局部最优选择,将大规模TSP问题用k-均值聚类算法进行分组,使用分布式并行算法将子问题分配到不同的计算节点上用改进的遗传算法求解。求解得到的子问题用Delaunay三角剖分算法进行合并,从而得到整个问题的解。通过TSPlib数据库进行实验,结果显示提出的算法在求解时间和求解精度上均有所提高。

摘要： 从某物流仓库装卸员工排班现状出发,对目前员工排班的状况进行分析,剖析了造成员工工作饱和度不稳定的因素。围绕员工排班策略,从仓库收发量预测、员工排班方面进行研究,致力于提升员工排班准确性,提升员工工作饱和度的稳定性,提高物流仓库的服务水平,提高员工福利等。提出了基于收发量预测的员工排班解决方案,对于保证服务水平的前提下降低成本的员工配置具有重要意义。

摘要： 根据商品车、轿运车主要几何特征,分别对商品车结构和轿运车结构建模.考虑多目的地不同订单需求、商品车配载三维尺寸约束和轿运车运输能力约束为限制条件,以混合配载利润最大化为目标函数,建立轿运车配载优化模型.针对禁忌搜索算法易局部收敛的缺点,引入贪心算法,并在禁忌搜索算法中采用两种置换操作生成领域,进而设计了一种改进的禁忌搜索算法进行求解,应用Matlab软件进行仿真计算,仿真实验结果证明了算法的有效性.

摘要： 实际项目调度中的很多关键资源往往具有时间窗特征,且具有多技能,项目中任务执行允许不连续,可以对任务进行适当拆分.本文对这种多技能资源时间窗约束下的任务可拆分项目调度问题进行研究,建立了一个数学规划模型,开发一类带有优先规则的Rollout算法进行求解,求解过程运用贪心策略实现资源指派.实例测试结果表明该算法比只使用优先规则的启发式方法求解效果好,算法具有有效性.

摘要： 词语对齐旨在计算平行文本中词语之间的对应关系，对机器翻译、双语词典构造等多项自然语言处理任务都具有重要的影响。虽然近年来词语对齐在建模和训练算法方面取得了显著的进展，但搜索算法往往都采用简单的贪心策略，面临着搜索错误较大的问题。本文提出了一种基于对偶分解的词语对齐搜索算法，将复杂问题分解为两个相对简单的子问题，迭代求解直至收敛于最优解。由于对偶分解能够保证求解的收敛性和最优性，本文提出的搜索算法在2005年度863计划词语对齐评测数据集上显著超过GIzA++和判别式词语对齐系统，对齐错误率分别降低4.2％和1.1％。

摘要： P2P 流媒体数据分配技术是P2P 流媒体系统的核心技术。本文介绍了一种基于块重要度与缓冲延迟的P2P 流媒体数据分配算法，采用系统缓存延迟优先分配及数据块重要度优先分配的贪心策略，从缓存延迟、流媒体数据连续性等方面对传统数据分配算法进行了改进。通过仿真实验表明，改进的算法比同类算法具有更小的缓冲延迟，并且保证了媒体数据的连续播放。

摘要： 路径容量对于路由协议的设计、QoS保障以及拥塞控制等方面有重要指导意义.为充分发挥无线Mesh网络中多设备多信道的资源优势,以路径容量为研究对象,首先提出了针对无线Mesh网络的本地虚拟报文探测分析模型,给出网络无干涉传输的充要条件,然后将给定的路径容量测量问题转化为信道分配及报文调度的最优化问题.在此基础上,采取贪心策略作为启发式条件,设计了路径容量评估算法PCEAGS进行求解.最后,详细讨论了算法中的若干参数如路径跳数、报文数目、节点的平均信道及无线设备数目等对评测结果准确性的影响.实验结果表明,该算法能以较低的平均时间复杂度求得近似解,且具有良好的可扩展性.

摘要： 在现实世界中,大量复杂系统都可以通过抽象的节点和连边构成的网络来加以刻画.作为城市交通系统的重要组成部分,道路交通网络是一个典型的复杂系统,与人们的生活密切相关.道路交通网络中的关键节点识别问题是复杂网络领域研究中的一个经典难题.传统的度中心性算法和PageRank算法在复杂网络的关键节点的识别中具有较好的应用,考虑到道路交通网络中关键节点的特殊性和彼此关联性,本文在度中心性算法的基础上引入贪心算法的思想,提出了一个基于贪心策略的度中心性关键节点识别方法,同时,本文在PageRank算法的基础上引入贪心算法的思想,提出了一种基于贪心策略的PageRank关键节点识别方法,从而使道路交通网络中关键节点识别的结果更合理,在交通道路维护保养、规划设计,以及犯罪分子潜逃阻断等领域都有重要应用价值.通过公开数据集与经典的关键节点识别方法做比较,验证了算法的有效性.

摘要： 本发明提供一种天地融合网络中引入边缘计算架构后的计算卸载方法，利用博弈论的基本思想解决多设备同时接入卸载时对卫星边缘计算节点SEC上部署的通信资源竞争问题，利用贪心思想使得决策更新选择时能够获得最小的总体损耗值。因此，在天地融合网络中的卸载场景下，处理能力较弱的终端节点可通过该算法有策略地将其计算任务卸载至处理能力强的SEC上进行处理，从而减少网络的整体损耗值。本发明利用博弈论的基本思想解决多设备同时接入卸载时对卫星边缘计算节点上部署的通信资源竞争问题，利用贪心思想使得决策更新选择时能够获得最小的总体损耗值。

摘要： 本发明涉及一种基于贪心策略的无人飞行器的航迹规划方法，特别涉及导航计算领域。包括以下步骤：S1：获取原始数据集，并对所述原始数据集进行预处理得到降维数据集、出发点A、第一目的点B和水平度量d，所述预处理包括数据集可视化和数据降维处理；S2：从所述出发点A出发，依次沿着经过水平度量d排序的空间点集合X＝{x1,x2,…,xt,xt+1,…,xn}X＝{x1，x2，...，xt，xt+1，...，xn}进行遍历；S3：找到出发点A能访问到的最远的点xt，并按序构建出一个所述出发点A能在满足约束条件下访问校正点的集合X'＝{x1,x2,…,xt}。本方案解决了如何在系统定位精度限制下的进行航迹快速规划的技术问题，适用于飞行器航迹规划。

摘要： 本发明涉及一种基于贪心策略的失踪目标搜索方法。将连续的历史GPS轨迹数据转变成离散的位置点序列，计算目标位置转移概率矩阵，而后评估出找到目标的单位搜索代价；根据转移概率矩阵和评估的搜索代价计算“代价时跨比”、“概率代价比”，基于贪心策略遍历代价时跨比、概率代价比确定搜索时刻、待搜索位置的序列；重复上述过程，直到搜索时刻为目标时刻，输出目标位置。本发明方法利用历史轨迹数据，估测搜索时刻评估指标——期望的代价时跨比，和搜索位置评估指标——期望的概率代价比，来启发式确定搜索时刻和搜索位置，有效地降低了找到目标指定时刻所在位置的搜索代价。

摘要： 本发明公开了一种基于距离贪心策略的病人生理数据特征选择方法，针对于现今特征选择算法性能较低的劣势进行了改良，该算法用贪心策略改进了原灰狼算法中的位置更新部分，提升了算法开发最优解的能力，改善了收敛速度，该算法可以有效提高分类准确度，降低数据特征冗余。

摘要： 本发明提供一种基于EM算法与贪心策略的红细胞序列样本分割方法，其主要步骤包括利用EM算法对对不可直接观测到的状态模型进行估算，然后根据这个初值进行不断迭代，对模型参数进行不断更新直至其收敛，并利用贪心策略对EM迭代过程进行优化。从而实现对样本序列分割。本发明提高基础医学仿真的真实性与直观性，在此基础上减少仿真过程中的手动工作量。

摘要： 本发明属于计算机无线通信技术领域，涉及在基站集成无线网络环境下,一种基于新效用函数贪心策略的按需服务数据包调度贪心算法。首先我们建立该环境下数据包调度问题的数学模型，包括时隙模型和报文请求模型，将原问题转化为整形规划问题，这种整形规划问题可以证明为NP问题，在线性时间内不能找到其最优解，根据模型的特殊情况，可以将问题转化为0‑1整形规划问题，这样可以大大的减少求解问题的复杂性。在实际的online条件(即当前只有部分信道情况已知，部分待调度报文到达)下，基于本文提出的效用函数函数值的贪心策略比基于现有效用函数的贪心策略具有更好的仿真效果，能够提高分配报文的总效益。

摘要： 本发明公开了一种基于空间位置评价和贪心策略的多视图靶点标定方法，该方法引入已知空间坐标的精度评价点，将精度评价点和靶标靶点视为未知空间位置的靶点进行标定计算，最终通过比较精度评价点的标定位置坐标和实际位置坐标得到标定精度，为直接精确评价靶标标定的空间位置精度提供了依据。同时基于贪心算法的思想，提出了一种多视图标定策略，可以在使用较少视图就标定出满意结果时提前结束标定流程，无需每次固定采集大量的视图，提高了标定效率。并且可以自动滤除数据质量较差的视图，进一步减少了个别异常数据对标定结果的影响，提高了标定精度，增强了鲁棒性。

摘要： 本发明涉及一种基于遗传算法和贪心策略的飞艇多任务点航线规划方法，根据飞艇转弯时的最小飞行速度和最大转弯坡度角，计算得到飞艇的最小转弯半径；根据遗传算法的全局搜索能力，得到飞艇从起飞点经过所有任务点回到降落点的最优飞行顺序；基于贪心策略的航线规划方法，依次得到最优飞行顺序中每相邻两个任务点间的最优航线，连接每相邻两个任务点间的最优航线，最终得到飞艇从起飞点通过所有任务点返回着陆点的最优航线。本发明在飞艇大转弯半径的影响下准确经过多任务点并快速准确地生成最优航线，提高了飞行效率；结合了遗传算法的全局搜索能力和贪心策略的局部最优的特点，提高了运算效率。

摘要： 本发明公开了一种基于贪心策略的多机协同成像路径规划方法，包括以下步骤：更新探测装备的信息及待探测区域的信息；探测装备的信息包括状态信息，所述状态信息包括空闲状态、非空闲状态；根据当前所有空闲状态的探测装备及待探测区域的信息确定最优探测路径；将最优探测路径对应的探测装备的状态由空闲置为非空闲状态，该探测装备根据最优探测路径进行路径探测，记录探测装备完成此次路径探测所需的时间，更新待探测区域的信息；判断待探测区域的面积大小是否为0。本发明的方法通过规划不同探测装备的航迹，使各装备相互协作完成特定待探测区域的成像覆盖。

摘要： 本发明公开了一种基于贪心策略的采摘机器人主动建图方法，其包括SLAM建图方法，基于贪心策略的主动探索点的选取以及局部规划器的设计，核心点在于主动探索点的选取，本发明综合考虑frontier与机器人之间的距离，frontier集合的信息熵以此决定探索点，并依据探索点使用模拟退火算法对探索路径进行优化，减少了机器人的探索路径长度以及缩短了建图时间。