【摘 要】
：
标签割问题是定义在标签图上的一类经典的组合优化问题。标签图由顶点集、边集、标签集以及边集到标签集的映射组成。在算法研究中,标签割问题是一般图上对应优化问题的推广;在实际应用中,标签割问题被用来衡量共享风险链路网络的健壮性等。最小s-t标签割问题是标签割问题中的基本问题,其目标是在标签图上求一个最小标签子集,使得在图上删除该子集对应的边集后,s点和t点不再连通。最小s-t标签割问题,一方面,是最小s
论文部分内容阅读
标签割问题是定义在标签图上的一类经典的组合优化问题。标签图由顶点集、边集、标签集以及边集到标签集的映射组成。在算法研究中,标签割问题是一般图上对应优化问题的推广;在实际应用中,标签割问题被用来衡量共享风险链路网络的健壮性等。最小s-t标签割问题是标签割问题中的基本问题,其目标是在标签图上求一个最小标签子集,使得在图上删除该子集对应的边集后,s点和t点不再连通。最小s-t标签割问题,一方面,是最小s-t割问题的推广;另一方面,是最小s-t权重标签割问题和多点对最小标签割问题的子问题。最小s-t标签割已被证明是NP困难问题,并且在P≠NP的假设下不存在近似比小于2log1-1/log logc n n（c＜1/2）的多项式时间近似算法,目前,该问题缺乏能够提供较优可行解的启发式算法。本文研究了最小s-t标签割问题及其相关问题的启发式算法。据我们所知,这是首次从启发式算法的角度对最小s-t标签割问题的系统性研究。根据最小s-t标签割问题的特征,本文基于随机游走与路径采样的思路,提出了一个评估算法,用以量化标签的影响因子。该算法通过运行多次随机深度优先遍历,根据遍历经过的标签次数和每次遍历得到的路径长度对每个标签进行打分。其中使用的随机深度优先遍历以s为起点,t为终点,在遍历过程中,根据边上标签的虚拟权重（以区分带权标签图中的实际权重）随机选择下一个顶点。本文基于评估算法设计了求解最小s-t标签割问题的启发式算法。该算法分为三个阶段:第一阶段,根据输入的标签图随机生成多个具有不同虚拟标签权重的标签图;第二阶段,在每个生成的标签图上应用求解子算法:对标签进行评估,选择最优标签放入可行解,并删除此标签对应的边集,直到该图上s点(点不再连通。第三阶段,从生成标签图的所有可行解中选择最小的解作为算法解返回。本文作者发现,该算法不仅适用于最小s-t标签割问题,还可以通过修改评估算法中的统计方式求解最小s-t权重标签割问题,通过修改评估算法中随机深度优先遍历的起点终点求解多点对最小标签割问题。通过实验对比发现,本文设计的启发式算法在上述问题中均能得到较优的可行解。另外,算法中虚拟标签权重范围,生成的标签图个数以及随机深度优先遍历的次数都是算法的参数,可以根据实际问题规模和运行条件进行修改。并且,由于算法在随机生成的多个标签图上的求可行解过程是独立、互不干扰的,只需要简单修改就可通过并行计算进行算法加速。
其他文献
大学语文课程作为一门基础课、通识课,在课程思政建设中具有独特优势。在大学语文中有机融入思政教育元素,改革创新课程教学,找准课程思政内容的融入点,让学生在润物无声中树立坚定的理想信念、提高人文素养。
由于天气和人为等因素的影响,雾霾现象变得更普遍并严重影响着人们的生活。雾霾天气会使图像采集设备获取的图像质量下降,从而影响无人驾驶等视觉计算系统的安全性和准确性。不同浓度的雾霾给图像上的目标检测和图像分割等深度学习领域的计算机视觉任务带来不同程度的困难,因此通过训练使深度学习模型能够学习到图像中不同程度的雾霾特征显得尤为重要。现阶段的雾霾分类方式包括两类。一类方法是基于传统数值统计的雾霾分类,此类
基于消费级深度相机的实时三维重建技术包括深度相机逐帧捕捉数据、相机姿态实时估计、融合体模型提取面模型、前景分割等步骤,在重建过程中,往往会出现噪声、冗余和帧间不匹配等问题。论文详细描述了从深度相机捕捉数据到最终三维模型的建立过程中,对重建三维模型精度与质量进行提升的三种方式,分别是帧块的自适应处理,TSDF的精细化处理以及基于平面检测的前景分割。在深度相机的拍摄过程中,由于相机剧烈抖动或光线变化等
推荐系统在人们的生产生活中应用广泛,在信息爆炸时代对于信息的过滤、便民服务等方面发挥了重要作用。序列推荐是推荐系统的重要领域,被广泛应用于电影、电商、短视频等行业,其主要任务是通过分析用户与项目之间的交互序列,利用序列之间的依赖性来捕获用户最近期的偏好,从而预测用户下一次可能交互的项目。推荐系统成功的关键是用户偏好和项目特征的准确表示,许多广泛应用的推荐模型都是基于欧几里得空间（即欧氏空间）的表示
大数据时代,隐私泄漏问题成为了社会发展的隐患。加强隐私保护,既需要公众提高对个人隐私的保护意识,也需要强有力的隐私保护技术予以支撑。可搜索加密（Searchable Symmetric Encryption,SSE）作为一种数据利用与共享的重要手段,既能在查询过程中保护数据所有者的数据隐私,又能保留数据的可查询性质,具有非常重要的研究意义。作为实现密文检索的重要工具,可搜索加密的基本工作过程是,给
随着科技以及电子设备的日益发展,在线学习逐渐成为一种流行且常见的教育方式。在线学习具有资源多元化、易于使用、受众面广泛等优点,学习者可以不受时间和地域限制地进行学习,然而其缺少了传统教育所具有的实时的反馈机制。实时且准确地对学习者的在线学习过程中的学习参与度进行评估,不仅能够给予学习者足够的监督反馈使其保持良好的学习状态,而且能够给予授课者适时的教学反馈使其有效提高教学质量,对于在线教育的发展具有
近年来,继人脸识别、指纹识别、声音识别、动作识别等生物识别技术之后,基于心电信号（Electrocardiogram,ECG）的身份识别（以下简称心电身份识别）凭借其活体检测、隐私性高、安全性突出等独特优势,已成为一种被广泛关注的新身份识别技术。目前,心电信号虽已成功应用于身份识别,但其识别性能远不如其他生物特征技术。心电信号容易受到各种干扰噪声的影响,稳定性比较差,而且具有高区分性的特征并未得到
股票预测是指对股票具有深刻了解的研究人员根据股票行情的发展进行的对未来股票趋势方向以及涨跌程度的预测行为。然而,由于股票市场的高度波动性和非平稳性,极大增加了股票预测的难度。新闻媒体信息的爆炸式增长以及自然语言处理和文本挖掘技术的不断发展为股票预测的进一步研究提供了新思路,使研究者能够从众多的新闻媒体信息中揭示市场趋势和波动性。在现有的基于新闻文本的股票预测方法中,大多数方法主要以单一新闻信息（如
大学教育中的语文教育是多方面、多样性的综合体,素质教育也是培养大学生的重要内容,不仅要把思政融入到教学中,更要突出表现大学生自身的特点。大学语文课程是一门重要的基础性学科,是以围绕人文教育开展的核心课程,充分利用语文课堂这一途径,发挥学科特长,将思政教育有效结合,推动大学语文教学改革,以达到以德树人的根本目标。课程思政教育下的大学语文课堂要获得良好的学习效果,需要教师不断地提高自身能力,还需要学校
随着物联网的不断发展,物联网设备的数量和种类正在急速增加。物联网设备应用十分广泛,有一部分物联网设备无法使用传统的电池或电源进行供电,因此需要用到能量收集技术。能量收集就是通过收集物联网设备周围的微小能量（例如太阳能、风能等）,从而达到维持自身系统对电能的需求。能量收集可以为不方便使用传统供电方式的物联网设备供电,保证物联网设备的运行。但是,由于能量收集设备的能量输出通常很弱且不稳定,因此物联网设