-
题名最小支配阈值集问题的降阶回溯算法
- 1
-
-
作者
储旭
宁爱兵
胡开元
代苏玉
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机工程与科学》
CSCD
北大核心
2024年第5期897-906,共10页
-
基金
国家自然科学基金(71401106)。
-
文摘
图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。
-
关键词
最小支配阈值集问题
数学性质
上下界算法
降阶回溯算法
-
Keywords
threshold-minimum dominating set problem
mathematical property
upper and lower bound algorithm
backtracking algorithm with reduction
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名疫情期间生活物资集散点选址问题的降阶回溯算法
- 2
-
-
作者
储旭
宁爱兵
胡开元
代苏玉
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机应用研究》
CSCD
北大核心
2023年第8期2351-2360,共10页
-
基金
国家自然科学基金资助项目(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
疫情爆发后,封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一,该问题可抽象为疫情期间生活物资集散点选址问题,其实质为组合优化中的NP-hard问题。基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究,首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出分配子算法、上下界子算法以及降阶子算法;基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程,结果表明该算法能通过减小问题规模来降低问题求解的难度。
-
关键词
生活物资集散点选址问题
数学性质
分配算法
上下界算法
降阶回溯算法
-
Keywords
location problem of distribution points for living supplies
mathematical properties
allocation algorithm
upper and lower bound algorithms
backtracking algorithm with reduction
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
