相关实验视频
Updated: May 27, 2025

09:23
Harmonic Nanoparticles for Regenerative Research
Published on: May 1, 2014
11.4K
基于富里埃变换的P-NP实例分解,用于解决线性排序问题
Xabier Benavides1,2, Leticia Hernando3, Josu Ceberio4
1University of the Basque Country UPV/EHU, Donostia-San Sebastian, 20018, Spain xbenavides@bcamath.org.
Evolutionary computation
|February 20, 2025
概括
本研究介绍了一种新的元启发式算法,P-Descent Search (PDS),用于线性排序问题 (LOP). PDS利用里埃变换来简化复杂的优化问题,从而提高了搜索效率.
科学领域:
- 组合优化的优化.
- 计算复杂性理论 计算复杂性理论
- 算法设计 算法设计
背景情况:
- 对有限群的里埃变换是分析组合优化问题的宝贵工具.
- 现有的启发式和元启发式算法很少利用福里埃转换信息作为搜索指导.
- 线性排序问题 (LOP) 作为一个案例研究来解决这个研究差距.
研究的目的:
- 通过利用里埃变换属性,为线性排序问题 (LOP) 提出一种新的元启发式算法.
- 为了解决利用福里埃变换用于指导搜索的启发式算法中的研究缺口.
- 开发一个优化策略,将NP难题转化为更易处理的形式.
主要方法:
- 基于富里埃转换的实例分解策略,将LOP实例划分为P和NP-Hard组件.
- 分解实例的线性聚合,以创建具有可调P和NP-Hard比例的人工实例.
- 开发P-Descent Search (PDS) 的元启发式算法,最初优化具有高P组件权重的替代实例.
主要成果:
- 增加P组件的重量会导致一个不那么崎的健身景观,适合本地搜索优化.
- P-Descent Search (PDS) 算法展示了有希望和可预测的性能.
- PDS的性能显示与特定问题特征的相关性,表明自动超参数调整的潜力.
结论:
- 拟议的实例分解和P-Descent Search提供了一种有效的方法来解决线性排序问题.
- 该方法成功地将复杂的优化场景转化为更易于管理的,用于启发式优化.
- 这些发现为进一步研究用于组合优化的自适应和自动调整的元启发式算法开辟了道路.
相关概念视频
Interpreting ¹H NMR Signal Splitting: The (n + 1) Rule
1.1K
In the AX proton spin system, proton A can sense the two spin states of a coupled proton X, resulting in a doublet NMR signal with two peaks of equal (1:1) intensity. When proton A is coupled to two equivalent protons (AX2 spin system), the spin states of each X can be aligned with or against the external field, creating three possible scenarios. This results in a 1:2:1 triplet signal, where the central peak corresponds to the chemical shift of A and is twice as large or intense as the...
1.1K
¹H NMR: Interpreting Distorted and Overlapping Signals
989
Spin systems where the difference in chemical shifts of the coupled nuclei is greater than ten times J are called first-order spin systems. These nuclei are weakly coupled, and their chemical shifts and coupling constant can generally be estimated from the well-separated signals in the spectrum.
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
989
Fast Fourier Transform
256
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
The computational efficiency of the FFT becomes...
256
Properties of Fourier series I
187
The Fourier series is a powerful tool in signal processing and communications, allowing periodic signals to be expressed as sums of sine and cosine functions. A foundational property of the Fourier series is linearity. If we consider two periodic signals, their linear combination results in a new signal whose Fourier coefficients are simply the corresponding linear combinations of the original signals' coefficients. This property is crucial in applications like frequency modulation (FM)...
187
¹H NMR: Pople Notation
1.7K
The Pople nomenclature system classifies spin systems based on the difference between their chemical shifts. Coupled spins are denoted by capital letters with subscripts indicating the number of equivalent nuclei. When the coupled nuclei have well-separated chemical shifts, they are assigned letters that are far apart in the alphabet, such as A and X. When the difference in chemical shifts is small, coupled nuclei are named using adjacent letters of the alphabet (AB, MN, or XY).
A proton...
A proton...
1.7K
¹H NMR: Complex Splitting
1.2K
A proton M that is coupled to a proton X results in doublet signals for M. However, NMR-active nuclei can be simultaneously coupled to more than one nonequivalent nucleus. When M is coupled to a second proton A, such as in styrene oxide, each peak in the doublet is split into another doublet.
Splitting diagrams or splitting tree diagrams are routinely used to depict such complex couplings. While drawing splitting diagrams, the splitting with the larger coupling constant is usually applied...
Splitting diagrams or splitting tree diagrams are routinely used to depict such complex couplings. While drawing splitting diagrams, the splitting with the larger coupling constant is usually applied...
1.2K

