对于反顶集问题的动态值搜索
Wen Sun1, Jin-Kao Hao2, Zihao Wu1
1School of Cyber Science and Engineering, Southeast University, Nanjing, China.
PeerJ. Computer science
|June 22, 2023
概括
这项研究介绍了NP-hard反顶集问题的新算法. 代的动态值搜索算法在基准图表上取得了最先进的结果,为大多数实例找到最佳解决方案.
科学领域:
- 计算机科学 计算机科学
- 图形理论 图形理论
- 组合优化的优化.
背景情况:
- 回应顶点集问题旨在找到一个最小的顶点子集,其去除使定向图成为非循环的.
- 这个问题在计算上具有挑战性,因为它的NP-hard性质限制了实际应用.
- 现有的算法很难有效地为大型或复杂的图形找到最佳解决方案.
研究的目的:
- 开发一个有效的算法来解决NP-hard反顶集问题.
- 为了提高现有的最先进的算法对这个问题的性能.
- 分析关键算法组件对性能的影响.
主要方法:
- 开发一个代的动态值搜索算法.
- 集成本地优化,动态值搜索和扰动技术.
- 对来自不同来源的101基准定向图进行了广泛的计算实验.
主要成果:
- 拟议的算法在24个图表中实现了创纪录的最佳解决方案.
- 它匹配了101个基准图表中的75个最知名的解决方案.
- 与当前最先进的方法相比,该算法表现出卓越的性能.
结论:
- 代的动态值搜索算法对反顶集问题非常有效.
- 该算法在解决这个计算上具有挑战性的问题方面取得了重大进展.
- 进一步的分析证实了其核心组件在实现最佳结果方面的有效性.
相关概念视频
Uniform Depth Channel Flow: Problem Solving
92
To calculate the flow rate for a trapezoidal channel, first, identify the bottom width, side slope, and flow depth of the channel. The cross-sectional area (A) corresponding to the depth of flow (y), channel bottom width (B), and side slope (θ) is determined by:Next, calculate the wetted perimeter, which includes the bottom width and the sloped side lengths in contact with the water. Using the values of the cross-sectional area and the wetted perimeter, determine the hydraulic radius by...
92
Collisions in Multiple Dimensions: Problem Solving
4.3K
In multiple dimensions, the conservation of momentum applies in each direction independently. Hence, to solve collisions in multiple dimensions, we should write down the momentum conservation in each direction separately. To help understand collisions in multiple dimensions, consider an example.
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
4.3K
Difference from Background: Limit of Detection
6.7K
The limit of detection (LOD) is the smallest amount of analyte that can be distinguished from the background noise. The LOD value corresponds to the concentration at which the analyte signal is three times larger than the standard deviation of the blank signal. Below this value, the analyte signal cannot be differentiated from the background noise. It is calculated by dividing the calibration slope by 3 times the standard deviation of the blank signals.
The LOD indicates the presence or absence...
The LOD indicates the presence or absence...
6.7K
Effects of feedback
608
Feedback in control systems plays a critical role in shaping various operational parameters, extending beyond simple error reduction to influence stability, bandwidth, gain, impedance, and sensitivity. Understanding these effects requires examining a basic feedback system characterized by defined input, output, error, and feedback signals.
Feedback significantly modifies the gain of a control system. The gain of a system without feedback is altered by a factor of one plus GH, where G represents...
Feedback significantly modifies the gain of a control system. The gain of a system without feedback is altered by a factor of one plus GH, where G represents...
608
Normal and Tangetial Components: Problem Solving
205
Consider a man with a mass of 70 kg seated in a chair connected to a pin support through a member BC. If the man maintains an upright position, the task is to determine the horizontal and vertical reactions of the chair on the man when the member makes a 45° angle with the horizontal. At this moment, the man has a speed of 5 m/s, increasing at a rate of 1 m/s².
205
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.2K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.2K


