Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XI Международной научно-практической конференции «Технические науки - от теории к практике» (Россия, г. Новосибирск, 25 июня 2012 г.)

Наука: Технические науки

Секция: Информатика, вычислительная техника и управление

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Чистик И.К. ЛОКАЛИЗАЦИЯ СУБОПТИМАЛЬНЫХ РЕШЕНИЙ NPC-ЗАДАЧ // Технические науки - от теории к практике: сб. ст. по матер. XI междунар. науч.-практ. конф. – Новосибирск: СибАК, 2012.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов


 


Чистик Игорь Константинович


аспирант кафедры ВТ и АСУ, г. Краснодар


E-mail:


 


LOCALIZATION OF SUBOPTIMUM SOLUTIONS OF NPC-TASKS


Igor Chistik


Post-graduate student, chair of CF and ACS,


Krasnodar


 


АННОТАЦИЯ


Труднорешаемые (трудные) задачи имеют большое число приложений, поэтому их решение представляет значительный интерес. По виду решения эти задачи можно разделить на два класса – задачи, имеющие точное решение и задачи, допускающие приближённое решение. Данная статья посвящена одному подходу к приближённому решению NPC-задач. NPC-задачи, допускающие приближённое решение относятся к классу NP задач, содержащих в своих условиях оптимизацию целевой функции. Такая постановка трудной задачи – есть достаточный признак того, что задача допускает приближённое решение.


ABSTRACT


The difficult solved (difficult) tasks have a large number of appendices therefore their decision represents considerable interest. By the form decisions can be divided these tasks into two classes – the tasks having the exact decision and tasks, allowing the approximate decision. This article is devoted to one approach to the approximate solution of NPC tasks. The NPC tasks allowing the approximate decision belong to the class of NP of the tasks containing in the conditions optimization of criterion function. Such statement of a difficult task – is a sufficient sign of that the task allows the approximate decision.


 


Ключевые слова: оптимизация; функционал; локализация; гармоника.


Keywords: optimization; functional; localization; harmonica.


 


1. Определение NPC-задач, имеющих приближённое решение


Пусть форма представления решения задана в общем случае семейством рекурсивных уравнений zi = K(xzj), где x – исходные данные задачи. Пусть функционал g(z) : ℳ ® ℝ+, определённый на множестве ℳ структур z, является весом структуры z. Тогда g(z) является количественной мерой, согласно которой все возможные решения (z1z2, …, zi, …, zm), можно упорядочить от наихудшего решения z1 до наилучшего (оптимального) zopt решения, согласно заданному критерию, например критерию минимальности:


g(z1) ³ g(z2) ³…³ g(zi) ³…³ g(zopt).


Класс NPC-задач, имеющих приближённое решение, составляют задачи с целевым функционалом g(z) если выполняются условия:


1)целевой функционал g(z) вводит порядок на множестве ℳ;


2)исходное множество ℳ не упорядочено по g(z);


3)на множестве возможных решений (z1z2, …, zi, …, zm) значение функционала g(zi+1) не зависит от значений {g(z1), g(z2),…,g(zi)} или указанная зависимость до сих пор не найдена (в дальнейшем изложении будем называть это условием независимости значений функционала);


4)постановка задачи требует нахождение в ℳ такого zopt, для которого выполняется один из критериев {min g(zopt), max g(zopt), min (g(zopt)–g0)}, где g0 – априорно заданная величина веса решения.


Согласно свойствам локализации субоптимальных решений в пространстве поиска ФФЦ субоптимальных решений локально равноудалены друг от друга на расстояние D, зависящее только от n и требуемого объёма поиска.


Определение 1


i-я гармоника – множество цепей p(nk), факториальная форма которых делится без остатка на величину (n – 1 – i)!.


Нулевая гармоника содержит одну цепь с нулевой ФФЦ – статистический глобальный оптимум. Цепи i-й гармоники удалены друг от друга на расстояние


Di = (n – 1 – i)!,                                         (1)

Расстояние между цепями p(n, k) достигает минимума при i = k.


Гармоники с меньшими номерами содержат больше субоптимальных цепей. На рисунке 1 показаны ФФЦ (0, 6, 12, 18) первой гармоники для задачи Б1 (Задача Б1: найти цепь p(n, n+1) с наименьшим весом h(p) на полном неориентированном графе с порядком n. На веса рёбер наложено ограничение в виде неравенства треугольника, то есть для трёх произвольных вершин графа веса смежных рёбер x, y, z подчиняются неравенству x £ y + z) определения оптимальной цепи p(5,6). Расстояние между цепями D1 = (n ‑ 2)! = 1×2×3 = 6.

Рисунок 1 – ФФЦ = 0, 6, 12, 18 первой гармоники в задаче определения оптимальной цепи p(5,6)


 


Для проверки цепей p(nk) m-й гармоники предлагается строить окрестность СГО посредством арифметической прогрессии с шагом Dm и объёмом поиска d


,            (2)


где f – ФФЦ, d – объём поиска, или рекуррентной формулой


.          (3)


Сдвиг m-й гармоники на величину t позволяет, начиная с ФФЦ ft, строить окрестность  СГО, определяемую по формуле


.               (4)


На рисунке 2 показаны ФФЦ (2, 8, 14) первой гармоники объёмом d = 3, сдвинутой на t = 2 от СГО для задачи Б1 определения оптимальной цепи p(5,6). Расстояние между цепями D1 = (n – 2)! = 1×2×3 = 6.

Рисунок 2 – Факториальные формы = 2, 8, 14 цепей p(5,6) первой гармоники, сдвинутой на t = 2

 

2. Локализация субоптимальных решений на основе выбора рангов факториальных форм цепей

Теорема 1


При построении окрестности СГО в виде последовательности цепей p(n,k) с шагом Dp = ri×(ni)! оценка вычислительных затрат dp на построение каждой цепи определяется неравенством


k-i+1 £ dp £ k.

Доказательство

По определению разности


Dp = AB = a1a2ak – b1b2bk = c1c2ck.

Перепишем условие теоремы в ФСС


Dp = ri×(ni)! = 0102ri…0k.

Приравняем оба выражения для Dp


c1c2cick = 0102ri…0k.


Таким образом, ФФЦ двух цепей отличаются друг от друга в одном i‑ом разряде ci = ri. Следовательно, по определению функции маскирования ФФЦ X(A Ù B) = i и


dp(A,B) = k – X(A Ù B) + 1 = k – i + 1.


При i = 1 шаг максимальный Dp = r1×(n–1)! и вычислительные затраты dp = k. При i = k шаг минимальный Dp = rk×(nk)! и вычислительные затраты dp = 1 ■

Теорема 2


Окрестности СГО в виде последовательности цепей p(n,k) в которой для построения каждой очередной цепи требуется не менее dp переходов, имеет оценку величины шага Dp


1 £ Dp £ (dp – 1)!.

Доказательство

Вычислительные затраты по условию теоремы


dp ³ k – X(A Ù B) + 1.

Старший значащий разряд, в котором отличаются две ФФЦ A и B


X(A Ù B) £ k – dp + 1.

Пусть


Dp = AB = a1a2ak – b1b2bk = c1c2ck.


По свойствам функции маскирования можно определить такую разность C = c1c2cick, что


c1c2cick = 0102ri…0k,

где i = X(A Ù B). По определению разности


Dp = 0102ri…0k = ri×(ni)! = ri×(n – X(A Ù B))!.

Разность двух ФФЦ A ¹ B минимальна при ri = 1. Подставляем неравенства для X(A Ù B) и ri


Dp = (n + dp – k – 1)!.

При dp = 1 и k = n шаг минимальный Dp = 0! = 1.

При dp = k и k = n шаг максимальный Dp = (k – 1)! ■


Разработан частный метод на основе выбора рангов факториальных форм цепей. Данный метод превосходят быстрые эвристики Шермана-Рейтера и Лина по точности решения и может являться компонентом комбинированных способов решения задач рассматриваемого класса. Разработанный метод поиска субоптимальных решений имеет гибкие условия останова перебора: достижение заданного количества/доли проверенных решений, либо времени поиска, либо достижение заданного порога целевой функции, либо по завершению построения окрестности СГО, при этом декомпозиция пространства поиска на непересекающиеся области предполагает эффективную реализацию на параллельных вычислительных системах и языках программирования.

 


Список литературы:


1.Гашков С.Б., Чубариков В.Н. Арифметика. Алгоритмы. Сложность вычислений. 2-е изд., перераб. – М.: Высш. шк., 2000. – 320 с.


2.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.


3.Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. – М.: Мир, 1985. – 512 с.

Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.