ЛЕКЦИИ Курс: Проектирование систем: Структурный подход Каф. Коммуникационные сети и системы, Факультет радиотехники и кибернетики Московский физико-технический институт (университет) / Марк Ш. ЛЕВИН Институт проблем передачи информации, РАН Окт. 9, 2004 ПЛАН: 1.Покрытие (иллюстрации): *покрывающее дерево, *минимальное дерево Штейнера, *2-связный граф, 2.Задача коммивояжера, задача о назначении (паросочетании) (формулировки) 3.Задача сопоставления (иллюстрации), применение в обработке экспериментальных данных 4.раскраска графа, задачи покрытия (иллюстрации и приложения) 5.Выравнивание (Alignment), максимальные подструктуры, минимальные надструктуры (иллюстрации, приложения) 6.задачи составления расписаний (Timetabling)

Покрытие (иллюстрация): 1-связный граф a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Дерево Штейнера (пример): a4a4 a3a3 a7a7 a1a1 a0a0 a2a2 a5a5 a6a6 a9a9 a8a8 2 a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Покрывающее дерево (длина = 19): a4a4 a3a3 a7a7 a1a1 a0a0 a2a2 a5a5 a6a6 a9a9 a8a8 2

Покрытие (иллюстрация): 2-связный граф Покрытие 2-связным графом: Выделение двух клик из 3 узлов (центры)

Покрытие (иллюстрация): 2-связный граф Покрытие 2-связным графом Соединение каждого узда с двумя центрами

Задача коммивояжера a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a ФОРМУЛИРОВКА: Множество городов: A = { a 1, …, a i, …, a n } Расстояние между городами i и j : ( a i, a j ) - множество перестановок элементов A, перестановка s* = min ( s ) f(s)=f(s*) f(s)= n-1 i=1 ( a(s[i]), a(s[i+1]) + ( a(s[n]), a(s[1]) a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a L =

Задача коммивояжера АЛГОРИТМЫ: 1.Жадный алгоритм 2.На основе покрывающего дерева 3.Метод ветвей и границ Др. ВЕРСИИ (много): 1.Цикл или путь 2.m-коммивояжеров 3.асимметричная задача (i.e., расстояния ( a i, a j ) и ( a j, a i ) - различны ) 4.Различные типы пространств (метрические пространства и др. ) 5.Многокритериальные задачи Др.

Задача о назначении (о паросочетании) a3a3 a1a1 a2a2 anan b1b1 ФОРМУЛИРОВКА: Множество элементов: A = { a 1, …, a i, …, a n } Множество позиций B = { b 1, …, b j, …. b m } (здесь let n = m) Эффективность пары i и j : z ( a i, b j ) = {s} - множество перестановок (назначений) элементов A на позиции множества B: s* =, т.е., элемент a i на позицию s[i] в B Целевая функция: max n i=1 z ( i, s[i]) b2b2 b3b3 bmbm...

Задача о назначении (паросочетаниях) АЛГОРИТМЫ: 1.Полиномиальный ( O(n 3 ) ) ВЕРСИИ: 1.Min max задача 2.Многокритериальные задачи Др.

A = { a 1, … a n }B = { b 1, … b m } C = { c 1, … c k } ПРИМЕР: 3-сопоставление (3-MATCHING) (3-дольный граф) Задачи сопоставления

АЛГОРИТМЫ: 1.Эвристики (т.е., жадные алгоритмы, локальная оптимизация, гибридные эвристики) 2.Переборные алгоритмы (например, метод ветвей и границ) 3.Морфологический подход ВЕРСИИ: 1.Динамические задачи (сопоставление трасс целей от нескольких радаров) 2.Задачи с ошибками в исходных данных 4.Задачи с неопределенностью (вероятностные параметры, размытые параметры) Др. Задачи сопоставления

Прикладной пример: применение задачи о назначении для определения скоростей частиц КАДР 1КАДР 2КАДР 3 ПРОСТРАНСТВО СКОРОСТЕЙ

МОДЕЛИ & АЛГОРИТМЫ: 1.Корреляционные функции (из радиотехники: обработка сигналов) 2.Задача о назначении между двумя соседними кадрами (алгоритмические схемы: генетические алгоритмы, другие алгоритмы для задачи о назначениях, гибридные схемы) 3.Многостадийная задача о назначениях (например, анализ трех кадров и др. ) (алгоритмические схемы: генетические алгоритмы, Другие алгоритмы для задачи о назначениях, гибридные схемы) ВЕРСИИ : 1.Базовая задача 2.Задачи с ошибками 3.Задача с неопределенными оценками (вероятность, размятые множества) Др. Прикладной пример: применение задачи о назначении для определения скоростей частиц

ПРИЛОЖЕНИЯ (среда газа или жидкости): 1.Физические эксперименты 2.Науки о климате (например, исследование облаков) 3.Химические процессы 4.Биотехнология Источники: 1.PIV системы (лазер/оптические системы) 2.Фотографии со спутников 3.Электронные микроскопы Др. Прикладной пример: применение задачи о назначении для определения скоростей частиц

Задача раскраски графа (иллюстрация) Исходный граф G = (A, E), A – множество вершин, E – множество ребер Задача: Назначить цвета для каждой вершины с минимальным общим числом цветов и ограничением: соседние вершины имеют различный цвет G = (A,E)

Задача раскраски графа (иллюстрация) G = (A,E) Правильная расцветка

Задача раскраски графа (иллюстрация) ПРИЛОЖЕНИЯ: 1.Назначение регистров в процессе компиляции (А.П. Ершов, 1959) 2.Назначение частот / каналов связи (статическая задача, динамическая задача и др.) 3.Проектирование больших интегральных схем (VLSI design) Др.

Пример: кластеры функций системы и покрытие цепочками (покрытие вершин) F5 F6 F1 F2 F3 F4 F1 F2 F3 F4 F5F6 Орграф кластеров функций системы ДЛИННЕЙШИЙ ПУТЬ Приложение: тестирование систем

Примерe: кластеры функций системы и покрытие цепочками (покрытие дуг) F5 F6 F1 F2 F3 F4 F1 F2 F3 F4 F5F6 F3 F1F3 F5 F3 Орграф кластеров функций системы ПРИЛОЖЕНИЕ: ТЕCТИРОВАНИЕ ИЗМЕНЕНИЙ

Иллюстрация: покрытие кликами a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Исходный граф Клики (версия): C 1 = { a 0, a 1, a 2 } C 2 = { a 3, a 5, a 4 } C 3 = { a 7, a 8, a 9 } C 4 = { a 2, a 4, a 6, a 7 } a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 a2a2 a7a7 a4a4 ПРИЛОЖЕНИЕ: РАЗМЕЩЕНИЕ СЕРВИСА (например, коммуникационные центры

Задача выравнивания (Alignment) (иллюстрация) СЛУЧАЙ 2 СЛОВ: A ABBDX A DACXZ Слово 1 Слово 2 ЗАДАЧА ВЫРАВНИВАНИЯ: минимальное число дополнительных элементов

СЛУЧАЙ 2 СЛОВ: A ABBDX A DACXZ Слово 1 Слово 2 A ABB DXZ Минимальная Надструктура C Задача выравнивания (Alignment) (иллюстрация)

СЛУЧАЙ 2 СЛОВ: A ABBDX A DACXZ Слово 1 Слово 2 A ABB DXZ Надструктура C A ABBD X A D A CXZ Задача выравнивания (Alignment) (иллюстрация)

СЛУЧАЙ 2 СЛОВ: A ABBDX A DACXZ Слово 1 Слово 2 ПРИЛОЖЕНИЯ: 1.Лингвистика 2.Биоинформатика (исследование генов и др.) 3.Обработка последовательностей кадров (обработка изображений) 4.Моделирование конвейерных систем A ABBD X A D A CXZ Задача выравнивания (Alignment) (иллюстрация)

ДРУГИЕ ВЕРСИИ ЗАДАЧИ: *СЛУЧАЙ N СЛОВ *СЛУЧАЙ 2 2-МЕРНЫХ СЛОВА *СЛУЧАЙ N 2-МЕРНЫХ СЛОВ *M-РАЗМЕРНЫЕ СЛУЧАИ *ДР. Задача выравнивания (Alignment) (иллюстрация)

Подструктура и надструктура (iиллюстрация) СЛУЧАЙ 2 ЦЕПЕЙ: A ABBDX A DACXZ Цепь 1 Цепь 2 A ABB DXZ Задача 2: Минимальная Надструктура C ADX Задача 1: Максимальная Подструктура A

Подструктура и надструктура (иллюстрация): случай 2 орграфов Максимальная Подструктура (по дугам) H1H H2H Примерно H 1 &H 2

Минимальная Надструктура Максимальная Подструктура H2H H1H Подструктура и надструктура (иллюстрация): случай 2 орграфов

ПРИЛОЖЕНИЯ: 1.Принятие решений / Экспертные суждения (отношение доминирования) 2.Информационные структуры (базы данных) 3.Информационные структуры (базы знаний) 4.Биоинформатика 5.Химические структуры 6.Сетевые системы (например, социальные сети, программы) 7.Образы, основанные на графовых моделях 8.Изображения (графовые модели для изображений) 9.Лингвистика 10.Организационные структуры 11.Инженерные системы 12.Архитектура 13.Поиск информации 14.Распознавание образов 15.Близость графо-подобных систем Др. Подструктура и надструктура (иллюстрация)

ДРУГИЕ ВЕРСИИ ЗАДАЧИ: *СЛУЧАЙ N ГРАФОВ (БИНАРНЫХ ОТНОШЕНИЙ) *СЛУЧАЙ ВЗВЕШЕННЫХ ГРАФОВ *СЛУЧАЙ СО СПЕЦИАЛЬНЫМИ ОГРАНИЧЕНИЯМИ *ДР. Подструктура и надструктура (иллюстрация)

Задачи составления календарных планов (Timetabling) ПРИЛОЖЕНИЯ: 1.Расписания в образовании (университеты, школы) 2.Расписания в медицине 3.расписания в спорте (например, баскетбол) ДР. СОСТАВНЫЕ АЛГОРИТМИЧЕСКИЕ СХЕМЫ На основе комбинации моделей: 1.Раскраска графов 2.Назначение / Размещение 3.Планирование эксперимента (Combinatorial design) 4.Традиционные модели теории расписаний Др.