Cтраница 2
Распределенная СПП находит в каждом множестве С / точки, отстающие друг от друга на минимальном расстоянии, аналогично точкам, помеченным звездочками на рис, 5.2. В общем случае это может оказаться достаточно сложной переборной задачей. [16]
Например, если алгоритм перебирает все подмножества заданного множества, то следует отказаться от тестов, приводящих к обработке множеств мощности, превосходящей 20, поскольку у множества мощности п имеется 2 различных подмножеств. Переборные задачи, для которых наиболее важен учет отмеченного соображения, содержатся в разделах, посвященных графам, логическим формулам, играм. [17]
Нетрудно предложить алгоритм, вычисляющий А ( х, у) за полиномиальное от 1 ( х) / ( /) время. Таким образом, решение системы булевых неравенств - переборная задача. [18]
Для задач, формулируемых в терминах графов, такой подход приводит к необходимости создания генераторов случайных графов с теми или иными свойствами. При этом на начальном этапе, при общей формулировке переборных задач и разработке универсальных методов их решения, оказывается достаточным формирование выборки случайных графов с теми или иными свойствами, подчиняющейся равномерному закону распределения вероятностей. [19]
Расширение списка универсальных задач представляет не только теоретический, но и практический интерес. Если бы удалось придумать полиномиальный алгоритм решения, скажем, задачи коммивояжера, то оказалось бы возможным построить ( причем эффективно) и алгоритм решения всех без исключения переборных задач. Если же, наоборот, удастся доказать, что эта задача не является полиномиально разрешимой, то огромное число практически важных переборных задач оказалось бы таким же. [20]
В задачах не очень малой размерности перебор практически нереализуем. Количество вариантов в реальных задачах исчисляется астрономическими числами. Проблема решения переборных задач заключается не в том, чтобы найти конечный алгоритм решения любой задачи соответствующего класса, а в том, чтобы найти эффективный алгоритм, решающий каждую ( без исключения) задачу класса достаточно быстро. [21]
Было доказано существование универсальных переборных задач, таких задач А, из полиномиальной разрешимости которых следует полиномиальная разрешимость любой переборной задачи. В классе хорошо интерпретируемых в содержательных терминах задач универсальные задачи представляют собой максимально сложные задачи. [22]
Первые 11 универсальных задач представляют собой комбинаторные задачи распознавания свойств. Но к ней редуцируется любая переборная задача. [23]
По крайней мере один из параметров переборной задачи ( например, ее размерность) неограничен. Таким образом, число индивидуальных задач в классе бесконечно. Индивидуальные задачи класса - переборной задачи - различаются исходными данными - значениями численных параметров условий задачи. [24]
Работа всякого алгоритма составляется из отдельных шагов. Число шагов до получения решения задачи является важнейшей характеристикой вычислительной сложности работы алгоритма. Различным индивидуальным задачам, определяемым данным Классом задач ( переборной задачей), отвечает разная входная информация и разное количество шагов алгоритма. В качестве характеристики входной информации х естественно брать длину 1 ( х) слова, которым она кодируется. Тогда сложность алгоритма на задаче х описывается функцией S ( x), определяющей число шагов, необходимых алгоритму для решения задачи х класса. [25]
Было доказано существование универсальных переборных задач, таких задач А, из полиномиальной разрешимости которых следует полиномиальная разрешимость любой переборной задачи. В классе хорошо интерпретируемых в содержательных терминах задач универсальные задачи представляют собой максимально сложные задачи. [26]
Расширение списка универсальных задач представляет не только теоретический, но и практический интерес. Если бы удалось придумать полиномиальный алгоритм решения, скажем, задачи коммивояжера, то оказалось бы возможным построить ( причем эффективно) и алгоритм решения всех без исключения переборных задач. Если же, наоборот, удастся доказать, что эта задача не является полиномиально разрешимой, то огромное число практически важных переборных задач оказалось бы таким же. [27]
Предположим, что рассматривается некоторое множество исходных моделей и исследуется определенная оптимизационная задача, процесс решения которой понимается как оптимальная аппроксимация исходной задачи из некоторого базового класса. Тогда можно сказать, что на множестве исходных задач задана модель решения поставленной оптимизационной задачи, если указан некий принцип или правило, согласно которому произвольной матрице или графу ставится в соответствие некоторое подмножество альтернатив. Определение принципа выбора оптимальных альтернатив приводит к переборной задаче, формализуемой в виде комбинаторной оптимизационной задачи на графах. [28]
Ясно, что нет проблемы в построении алгоритма решения; переборной задачи А. В результате после просмотра конечного числа слов у будет найдено, решение либо можно будет убедиться, что его нет. При сколько-нибудь заметных 1 ( х) это число фантастически велико и указанный перебор практически неосуществим. С полным основанием можно считать, что только полиномиальные, алгоритмы ( да и то не все) могут претендовать на практическую ценность. Поэтому основной вопрос, возникающий при теоретическом исследовании переборной задачи, - этот вопрос о том, является ли она полино. [29]
Строится первая матрица ветвления, производится ее приведение и сумма констант приведения суммируется к уже имевшейся нижней границе ( равной 48), что дает 56 как нижнюю границу стоимости любого тура в данной подзадаче. Ветвь не имеет смысла исследовать, если нижняя граница для туров в данной подзадаче превышает стоимость наилучшего тура, найденного в данный момент. Следовательно, это и есть искомый тур задачи. Рассмотренный пример хорошо показывает, как много вариантов в ряде случаев удается исключить из рассмотрения. Алгоритмы ветвей и границ являются одним из наиболее эффективных методов решения ряда переборных задач. Как правило, эти алгоритмы сложны для понимания, но выигрыш, получаемый в результате их применения, стоит тех усилий, которые приходится затрачивать либо на разработку собственного подобного алгоритма, либо на понимание предлагаемого готового алгоритма. [30]