Подходящий алгоритм

Cтраница 4

Допустимое множество точек. 1 - первый тип сырья. 2 - второй тип сырья. 3 - третий тип сырья. [46]

На рис. 3 изображено допустимое множество точек, состоящее, как видно, из трех сгущений. Эти сгущения могут быть связаны как с различными типами сырья, так и с какими-либо другими учтенными или неучтенными факторами. Естественно, если искать глобальный экстремум, то его возможно не удастся определить в рамках действующих условий. Например, для третьего типа сырья необходимо при такой неоднородности допустимого множества применять при предварительной обработке данных кластерный анализ. После получения классов экстремум отыскивается для каждого класса раздельно. Одновременно, применяя подходящий алгоритм кластеризации, возможно отбросить случайные выбросы. [47]

Каждая из задач представляет собой по форме массовую задачу переборного типа. Если для любой из этих задач каким-либо образом угадано решение, то проверка того факта, что найденное решение действительно удовлетворяет условиям задачи, требует полиномиального ( от длины записи входных данных) числа шагов. Наконец, все эти задачи, как говорят, полиномиально эквивалентны. Пусть, например, задачи А и В представляют собой поиск для заданного двоичного набора а некоторого набора 6, который по отношению к а обладает заданным свойством. Тогда должны существовать полиномы pi ( п) и р2 ( п) с натуральными коэффициентами и такие алгоритмически вычислимые функции / i ( x), / 2 ( ж), отображающие множество всех двоичных наборов в себя, что, во-первых, функции / i ( x), / 2 ( х) можно вычислить подходящими алгоритмами, которые для любого двоичного набора длины п заканчивают работу соответственно не более чем через р ( п) или р ( п) шагов. О функциях Л ( х), / 2 ( х) говорят, что они полиномиально сводят задачу А к задаче В и задачу В к задаче А. [48]

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