РОЗДІЛ 2
ДОСЛІДЖЕННЯ ВЛАСТИВОСТЕЙ ЗАДАЧІ КЛАСИФІКАЦІЇ В УМОВАХ НЕВИЗНАЧЕНОСТІ
Матеріал розділу 2 присвячено дослідженню властивостей задачі класифікації, виділеного в розділі 1 типу, з умовною назвою "задача сегментації". Поняття "обчислювальної складності", що використано в цьому розділі, визначається в класичному розумінні, "для найгіршого випадку", який визначається в фундаментальних роботах по теорії обчислювальної складності задач дискретної математики [27]. Оцінюючи обчислювальну складність задачі у найгіршому випадку, використовуємо ієрархію, що склалася до теперішнього часу та має вигляд: "поліноміальні задачі" - "NP-важкі задачі"- "важкорозв'язувані задачі". В більшості публікацій, присвячених дослідженню обчислювальної складності дискретних задач, розглядається або задача розпізнавання, або задача оптимізаційна. Систематичний огляд обчислювальної складності дискретних багатокритеріальних задач зроблено в роботах [34-36]. Публікації по дослідженню обчислювальної складності дискретних інтервальних задач на сьогодні відсутні.
2.1. Оцінка обчислювальної складності задачі класифікації в інтервальній і багатокритеріальній постановках
Як показано в [34], нижньою оцінкою складності проблеми знаходження ПМА є максимальна (по всім індивідуальним задачам масової задачі) потужність ПМА . При оцінці максимальної потужності будемо розглядати випадки повних задач, тобто таких індивідуальних задач, для яких існує збіжність .
Потужність розв'язку може мати швидкість зростання таку, що перевищує будь-який поліном від розмірності задачі. Інакше кажучи, потужність ПМА є такою великою, що її не можна представити в вигляді виразу, довжина якого була би обмежена поліномом від довжини входу. В цьому випадку задача є важкорозв'язуваною в самому сильному сенсі .
Як відомо [34], багатокритеріальна задача покриття графа зірками є NP- важкою, тому що як окремий випадок містить задачу розбиття графа на шляхи довжиною два [27]. Оцінимо складність задачі класифікації в постановці для багатокритеріального випадку ВЦФ (1.2) -(1.3).
Сформульована на конкретному N-зваженому графі G задача сегментації з ВЦФ (1.2)-(1.3) є повною, якщо існують такі ваги , при яких виконується рівність .
Масова задача називається повною, якщо існує її повна індивідуальна задача для кожного (m+ l )- вершинного графа.
Лема 2.1. Для будь-якого задача сегментації з ВЦФ (1.2)-(1.3) є повною.
Доведення. Оберемо будь-яке , що визначається даним N-вершинним графом . Для тривіальних випадків або Х=1 твердження очевидно. Нехай потужність МДР . Розглянемо спочатку випадок N=2, коли ВЦФ (1.2) має вигляд
. (2.1)
В даному графі G ребра перенумеровані числами , а ваги цих ребер визначимо таким чином:
(2.2)
З (2.1) і (2.2) маємо
(2.3)
де константа .
Позначимо різницю для пари . Тоді для будь-яких
, . (2.4)
Нехай серед елементів множини ребро е з найбільшим номером належить . Тоді з (2.1)-(2.4) слідують нерівності , які означають, що будь-яка пара є векторно-непорівнянною за ВЦФ (2.1). Останнє, з урахуванням необхідної рівності , означає виконання рівності . Для N=2 лема 2.1 доведена.
При будь-якому N2 для будь-якої індивідуальної задачі з ВЦФ (1.2)-(1.3) додавання нових критеріїв до цієї ВЦФ або залишає ПМ і ПМА незмінними, або поповнює їх новими альтернативами. Рівність потужностей виконується і при N3, якщо для критерії (1.3) визначимо згідно (2.1)-(2.3), а для - будь-яким способом. Лема 2.1 доведена.
Дводольний граф G=(V1,V2,E) називаємо нетривіальним, якщо потужності його долей строго більше 1.
Лема 2.2. Максимальна потужність МДР задачі сегментації для випадку m=2 визначається формулою , де через m і l позначені потужності долей V1 і V2, , відповідно повного дводольного графа G=(V1,V2,E).
Доведення. Згідно визначенню допустимий розв'язок містить всі вершини і підмножини вершин . Тому вибір типу компоненти зв'язності розв'язку x для однієї з двох вершин , однозначно визначає тип компоненти зв'язності для другої вершини множини . З урахуванням цих зауважень розглянемо можливі варіанти покриття повного дводольного графа G=(V1,V2,E) (h+1)-вершинними зірками, що називаються h-зірками. Нехай одна з вершин, для визначеності перша v1, є центром l-зірки, тоді друга вершина v2 множини є ізольованою. Таке покриття можливо у (одному) випадку. Якщо v1 є центром (l-1)-зірки, тоді розв'язок x як другої компоненти зв'язності містить ребро інцидентне другій вершині v2 множини . Таке покриття можливо побудувати способами. Якщо v1 є центром (l-z)-зірки, тоді друга вершина v2 множини є центром z-зірки. Таке покриття можливо побудувати способами. Якщо v1 - ізольована вершина, то вершина v2 множини є центром l-зірки. Таке покриття можливо в (одному) випадку.
Таким чином, потужність МДР є сумою всіх варіантів покриттів повного дводольного графа G=(V1,V2,E) для m=2 h-зірками, що розглянуті, і визначається формулою .
Лема 2.3. Для випадку максимальна потужність МДР задачі сегментації визначається рекурентною формулою , де |V1|=m і |V2|=l, , для повного дводольного графа G=(V1,V2,E).
Доведення. Нехай заданий повний дводольний граф G*=(V1*,V2,E). / V1* /=m=2 і /V2 /= l, . Згідно лемі 2.2 максимальна потужність МДР для цього випадку визначається точною формулою . Додамо до першої долі цього графа вершину v3. Отримаємо повний дводольний граф G=(V1,V2,E). Розглянемо можливі варіанти покриття отриманого графа G=(V1,V2,E) h-зірками. Нехай одна з вершин, для визначності v3, є центром l-зірки, тоді вершини v1 і v2 множини являються ізольованими. Таке покриття можливо в (одному) випадку, якщо v3 є центром (l-1)-зірки, тоді розв'язок x як другу компоненту зв'язності містить ребро , інцидентне одній з вершин v1 або v2 множини . Вибір (l-1)-зірки на графі G=(V1,V2,E) можливо отримати способами. Розглянемо кількість