Комбинаторная задача

Cтраница 1

Комбинаторная задача, к которой применим метод поиска с возвратом, может быть описана следующим образом. [1]

Комбинаторные задачи, встречающиеся в различных областях знания, часто приводят к проблеме оптимизации. Пусть дан критерий, позволяющий выделить решения с некоторыми заданными свойствами. Требуется найти множество таких решений, называемых оптимальными. В большинстве задач этот критерий имеет числовую природу, а множество всех решений разбивается на вполне упорядоченные классы. [2]

Комбинаторная задача называется трудной, если можно доказать, что ни один компьютерный алгоритм не может решить ее за полиномиальное время. Дело в том, что при возрастании некоторого параметра проблемы время, необходимое для решения задачи, растет с экспоненциальной, или неполиномиальной, скоростью. Изучением такого рода проблем занимается новая отрасль математики и компьютерной науки, получившая название теории сложности. Ныне существуют сотни NP-полных проблем. По общему мнению, все они трудные ( хотя доказательство этого утверждения пока не известно) и все связаны между собой так, что если будет найден алгоритм, позволяющий решать одну из них за полиномиальное время, то этот же алгоритм позволит сразу же решить и все остальные задачи. Задача о подмножестве чисел, сумма которых равна заданной величине, принадлежит к числу NP-полных задач. [3]

Комбинаторные задачи характеризуются очень большим числом допустимых решений, что делает невозможным прямой перебор. [4]

Комбинаторные задачи и ( О, 1) - матрицы. [5]

Комбинаторные задачи классические / / Мат. [6]

Комбинаторные задачи и ( ОД) - матрицы. [7]

Представление в виде дерева множества, включающего в себя S. Элементы множества S обведены кружками. [8]

Любая комбинаторная задача, к которой применим алгоритм перебора с возвратом, может быть описана в общем виде следующим образом: даны п линейно упорядоченных множеств. [9]

Комбинаторные задачи построения привлекают к себе внимание уже давно ( можно вспомнить, например, знаменитую задачу Эйлера о 36 офицерах), но их большое прикладное значение выяснилось сравнительно недавно и явилось, очевидно, дополнительным мощным стимулом, вызвавшим все возрастающее количество комбинаторных исследований, посвященных существованию и построению блок-схем. [10]

Многочисленные перечислительные комбинаторные задачи, в том числе ряд классических задач, сводятся к определению числа последовательностей, обладающих или не обладающих некоторыми специальными подпоследовательностями. В [92] показана возможность единообразного описания и решения подобных задач. [11]

Эта комбинаторная задача весьма проста, но требует перебора большого числа различных вариантов; ее решение мы обсуждать не будем. После того как это сделано, нужно вычислить полиномы Джонса узлов, соответствующих полученным диаграммам. Если двум диаграммам соответствует один и тот же полином Джонса, можно попытаться доказать эквивалентность соответствующих диаграммам узлов с помощью преобразований Рейдемейстера. [12]

Одна комбинаторная задача, Кибернетический сб. [13]

Многие комбинаторные задачи укладываются в схему двух только что разобранных задач. [14]

Пример задачи паросочетания. [15]

Страницы: 1 2 3 4