Системный анализ сложных объектов.Принципы динамического программирования в системном анализе сложных объектов

ЛЕКЦИИ-1-2. СИСТЕМНЫЙ АНАЛИЗ СЛОЖНЫХ ОБЪЕКТОВ. ПРИНЦИПЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В СИСТЕМНОМ АНАЛИЗЕ СЛОЖНЫХ ОБЪЕКТОВ ИСТОРИЯ ВОПРОСА Норберт Винер (1894 - 1964), основоположник кибернетики и теории искусственного интеллекта.. Уильям Росс Эшби (1903 -1972), «Кибернетика рассматривает не вещи, а способы поведения». Закон О Требуемом Разнообразии, названный его именем (закон Эшби): «управление может быть обеспечено только в том случае, если разнообразие средств управляющего (в данном случае всей системы управления) по крайней мере не меньше, чем разнообразие управляемой им ситуации». Принцип самоорганизации. Феликс Петрович Тарасенко (1932— 2021), фр. Прикладной системн ый анализ. Никита Николаевич Моисеев (1917—2000). Труды по динамике твёрдого тела с жидкостью, численным методам математической физики, теории оптимизации управления и др. Математическая модель экологических последствий ядерной войны («ядерная зима»), повлиявшая на заключение договоров между СССР и США об ограничении гонки ядерных вооружений 2 Р. Декарт, Ф. Бэкон, И. Кант, И. Ньютон, Ф. Энгельс, А.И. Берг, А.А. Богданов, Н. Винер, Л. Берталанфи, Ч. Дарвин, И. Пригожин, Э. Эшби, А.А. Ляпунов, Н.Н. Моисеев и другие ИСТОРИЯ ВОПРОСА Сложная система (>40 опр.)–система, состоящая из множества взаимодействующих составляющих (подсистем), вследствие чего сложная система приобретает новые свойства, которые отсутствуют на уровне рассмотрения свойств отдельных подсистем, и, следовательно, свойства всей системы не могут состоять из «арифметической» суммы свойств ее составляющих подсистем. Сложный объект, с одной стороны, есть объект, из которого может быть выделен другой объект (см. определение сложной системы). Здесь мы будем вкладывать в понятия «сложная система» и (или) «сложный объект» следующий смысл. Объект (система) является сложным, если он обладает следующими чертами (характеристиками), при этом имея в наличии хотя бы одну из нижеперечисленных: 1) отсутствие полного математического описания (т. е. наличия алгоритма F, реализующеготриаду из теории автоматов «вход – состояние – выход», или вычисления состояния объекта Y по наблюдениям его входов Х); 2)«зашумленность» объекта (системы), реализуемая неожиданностью поведения объекта для исследователя; 3) «нетерпимость» к управлению; 4) нестационарность системы (дрейф характеристик во времени); 5) невоспроизводимость экспериментов; 6) многомерность, многосвязность его характеристик; 7) нелинейность описания. Термины «система» и «объект» имеют весьма условное различие, зависящее от качества и степени интереса исследователя. Понятия «сложная система» и «сложный объект управления» не имеют строгого определения в научной литературе. 3 ИСТОРИЯ ВОПРОСА. Сущность системного анализа 1. Классификация проблем • • • • • • • • • • хорошо структурированные (well-structured), или количественно сформулированные проблемы, в которых существенные зависимости выяснены очень хорошо; слабо структурированные (ill-structured), или смешанные проблемы, которые содержат как качественные элементы, так и малоизвестные, неопределенные стороны, которые имеют тенденцию доминировать; неструктурированные (unstructured), или качественно выраженные проблемы, содержащие лишь описание важнейших ресурсов, признаков и характеристик, количественные зависимости между которыми совершенно неизвестны. 2. Методы решения. Методология исследования операций: 1) построение адекватной математической модели (ЛП, НЛП, ДП, ТМО, ТИ,…) и применении методов для отыскания оптимальной стратегии управления целенаправленными действиями. 2) методы и процедуры: абстрагирование и конкретизация анализ и синтез, индукция и дедукция формализация и конкретизация композиция и декомпозиция линеаризация и выделение нелинейных составляющих структурирование и реструктурирование макетирование 3. Процедура принятия решений • • • • • • • • реинжиниринг алгоритмизация моделирование и эксперимент программное управление и регулирование распознавание и идентификация кластеризация и классификация экспертное оценивание и тестирование верификация….. 4 ИСТОРИЯ ВОПРОСА. Сущность системного анализа 1. Процедура принятия решений Системы Поддержки Принятия Решений (СППР). Процедура принятия решений согласно включает следующие основные этапы: 1. формулировка проблемной ситуации; 2. определение целей; 3. определение критериев достижения целей; 4. построение моделей для обоснования решений; 5. поиск оптимального (допустимого) варианта решения; 6. согласование решения; 7. подготовка решения к реализации; 8. утверждение решения; 9. управление ходом реализации решения; 10. проверка эффективности решения. Для сложных проблем: 1.решение простых маломерных задач; 2.рекурсивный анализ вытекающих проблем из уже найденных путей; 3.оценка всех найденных путей решений по критериям исходящих подпроблем, сведенным к материальной или иной общей стоимости. 5 МОТИВАЦИЯ ДЛЯ СОЗДАНИЯ АЛГОРИТМОВ, СОКРАЩАЮЩИХ ПЕРЕБОР Справка. Класс P (polynomial time) (класс «быстро решаемых» задач за полиномиальное время): при обработке входных данных из n битов число шагов должно быть ограничено некоторой степенью числа n (полиномом). Класс полно-переборных задач называют NP (Non-deterministic Polynomial-Time Turing machines). Проблема: Сделать задачу с полиномиально проверяемым свойством. Большие задачи 1. Оптимальное решение задачи коммивояжёра. С ростом количества узлов время, затрачиваемое на полный перебор, растёт экспоненциально. Пример: на машине с 4-ядерным процессором 2,67 ГГц 10 узлов обсчитывается в среднем за 5 миллисекунд, 20 узлов – за 15 минут, а на расчёт оптимального пути для 60 узлов уйдёт более 6 триллионов лет… 2. Разложение многозначного целого числа на простые множители (алгоритмы криптографии). 25 3. C100 = 242519269720337121015504. Отбор 25-ти наиболее информативных признаков приемников сигналов из 100 каждые 10 минут. 4. Задача Гольбаха: любое четное число представить в сумме простых чисел. 5. Задача расписания. 6. Анализ генома. Геном –наследственная информация в четырех буквах А Т Г Ц. По анализу крови восстановить, какой геном крови (7 млрд букв) у каждого данного человека, а потом понять, что записано в нем (наши способности – к бегу, к математике, к музыке). Мы с вами живем примерно 3 млрд секунд. 7. .................................................................................................................................................................... 6 ИДЕОЛОГИЯ ДП. ОСНОВНЫЕ ПЛОЖЕНИЯ Задачи выбора наилучшего (оптимального) варианта решения при наличии нескольких возможных вариантов. 25 - полный перебор вариантов; = 1080 ?,= C100 ? - много или мало? - решение задачи большей размерности при помощи решения подзадач меньшей размерности (метод динамического программирования). Условия для применения ДП 1) в исходной основной задаче можно выделить подзадачи аналогичной структуры меньшего размера; 2) среди выделенных подзадач есть подзадача, имеющая тривиальное решение; 3) вложенность задач: оптимальное решение подзадачи большего размера может быть построено из оптимальных решений подзадач; решения подзадач запоминаются в таблицы разумного размера. Два типа задач, решаемых на основе ДП 1. Подсчет количества вариантов решения. 2. Поиск самого оптимального решения (оптимизация целевой функции). В этом случае выбирают лучшее среди всех решений подзадач. Примеры прикладных задач, решаемых на основе ДП ◊ ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ◊ ОПТИМАЛЬНАЯ ТРАЕКТОРИЯ (ЗАДАЧА КОММИВОЯЖЕРА) ◊ КОЛИЧЕСТВО ВСЕВОЗМОЖНЫХ РАЗЛИЧНЫЙ КОМБИНАЦИЙ (РЕШЕНИЙ) ИЗ УКАЗАННОГО ПРАВИЛА ИХ ГЕНЕРАЦИИ ◊ ............................................................................................. 7 Примеры вложений задач. ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ По ряду Фибоначчи устроена шишка, F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 , n > 1. ракушка, ананас, Необходимо найти Fn по номеру n. подсолнух, ураган, паутина, молекула ДНК, яйцо, стрекоза, ящерица… Рекурсия без сохранения промежуточных результатов Решение задачи «с конца» уменьшение n, пока не дойдем до известных значений int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); } При n >= 40 работает долго; одни и те же промежуточные данные вычисляются по несколько раз - число операций нарастает экспоненциально Рекурсия с сохранением промежуточных результатов int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } } Повторное использование сохраненных результатов уменьшает число операций. Алгоритм динамического программирования Решение «с начала». Сначала заполняем известные значения, затем все последующие. F[0] = 1; F[1] = 1; for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2]; Решили все подзадачи: Fi для i < n, затем, зная решения подзадач, нашли ответ: Fn = Fn – 1 + Fn – 2, где Fn – 1 , Fn – 2 уже найдены. 8 ПРИМЕР. ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n. Некоторые элементы последовательности вычисляются повторно несколько раз Цена вопроса. ДП предполагает сохранения результатов решения «мелких» подзадач («плата» памятью - мемоизация - ради экономии времени решения) 9 ОДНОМЕРНЫЕ ЗАДАЧИ ДП 1. Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом Из частных примеров: к каждой последовательности длиной (N-1) можно приписать 0 в любом случае (два способа) и 1 только в том случае, если она заканчивается на 0 (по условию задачи, один способ). Возникает динамическое правило: каждая последовательность длины (N-1) может быть продолжена либо одним, либо двумя способами. Пусть i - длина последовательности. F(i) – количество последовательностей длины i, удовлетворяющих условиям. Начальные значения (база динамики) динамики: F[1]=2; F[2]=3. Правило динамики F(i+1)=F(i)+F(i-1). Ответ к задаче - число F(N). Алгоритмическая сложность решения O(N). 10 ОДНОМЕРНЫЕ ЗАДАЧИ ДП 2. Требуется подсчитать длину наибольшей возрастающей подпоследовательности. Входные данные. В первой строке входных данных задано число N - длина последовательности (1 ≤ N ≤1000). Во второй строке задается сама последовательность - целые числа X, |X|≤10000. Выходные данные. 1) длина наибольшей строго возрастающей подпоследовательности; 2) сама наибольшая возрастающая подпоследовательность. 1) Определим ∀i – номера элемента исходной последовательности наибольшую возрастающую подпоследовательность [a0,..,ai], заканчивающуюся элементом ai. 2) Определим массив d, где d[i] = количество элементов в [a0,..,ai] 3) База динамики: d[0]=1. 4) Правило динамики. Пусть {d[k], k≤i} - известны. Для определения d[i+1]: o выбрать из {d[k], k≤i} наибольший элемент d[k*(i)], для которого выполнится a[k*(i)]