В чем заключается принцип уменьшения размерности при решении комбинаторных задач?

Принцип уменьшения размерности при решении комбинаторных задач заключается в замене полного перебора всех вариантов частичными переборами меньших объёмов. 1

Это достигается исключением из рассмотрения ряда подмножеств, заведомо не содержащих искомого экстремума, и сужением области перспективных вариантов. 1

Некоторые методы, которые используют принцип уменьшения размерности:

• Выделение признаков. 3 Исходный набор переменных сокращается до более управляемых групп (признаков) для дальнейшей обработки. 3 При этом такой набор должен быть достаточным для точного и полного описания исходного набора данных. 3
• Метод агрегирования (обобщения, факторизации). 1 Лучшее решение отыскивается не на исходном множестве, а среди значительно меньшего числа выделенных представителей. 1 Тем самым решение ухудшается (огрубляется), но трудоёмкость его поиска можно существенно сократить. 1
• Методы ветвлений с отсечениями, ветвей и границ. 1 Позволяют сузить границы перебора за счёт построения частичных решений, представленных деревом поиска, и применения методов построения оценок, позволяющих опознать бесперспективные частичные решения. 1
• Методы, основанные на применении эвристик. 1 Снижение размерности перебора достигается через снижение требований, которое заключается в отказе от поиска оптимального решения и нахождении квазиоптимального решения за приемлемое время. 1