Метод дерева решений и другие методы на основе графов
Дерево решений и метод дерева решений
Метод дерева решений применяется в задачах классификации и прогнозирования, когда решения приходится принимать в условиях риска, неопределённости и исход событий зависит от вероятностей. На каждое решение влияют какие-то определённые факторы, и у каждого решения есть свои последствия, которым присущ вероятностный характер. В этих условиях процесс принятия решений является последовательным и метод дерева решений предполагает определять, какие действия следует предпринять в каждой вершине дерева.
Дерево решений - математическая модель, которая задаёт процесс принятия решений так, что будут отображены каждое возможное решение, предшествующие и последующие этим решениям события или другие решения и последствия каждого конечного решения.
Дерево решений состоит из следующих элементов: дуг, узлов решений, узлов событий и конечных узлов (исходов).
Рассмотрим сначала простейший пример применения метода дерева решений и решим следующую задачу.
Пример 1. Решить методом дерева решений, какую сумму вы потратите на продукты в определённый день.
Решение. Альтернативные события на первом этапе: гости придут и гости не придут. Отображаем эти события в дереве решений в виде вершин событий (кружочков). Примем, что, если гости придут, на продукты придётся потратить крупную сумму. Это один из исходов (конечных узлов в дереве решений) в данной задаче.
В случае, если гости не придут, возможны два альтернативных события: в доме много продуктов и в доме мало продуктов. Отображаем эти события в дереве решений в виде вершин событий (кружочков), к которым ведут дуги из события "гости не придут". В случае, если в доме много продуктов, вы потратите на продукты малую сумму. В случае, если в доме мало продуктов, вы потратите на продукты среднюю сумму.
Дерево решений для этой задачи будет следующим:
Но даже для этой только что рассмотренной задачи альтернативные события могут быть связаны с некоторыми вероятностями. В частности, вы можете по своему опыту или же от одного из возможных гостей знать вероятность того, что гости к вам придут. Предположим, вероятность этого события равна 0,3. Тогда от единицы отнимем 0,3 и получим 0,7 - вероятность того, что гости не придут. События, следующие из этого события также могут быть связаны с вероятностями.
Предположим вы находитесь не дома и не имеете возможности посмотреть в холодильник и кухонные шкафы. Или вообще, все эти события произойдут только через несколько дней. Но вы эксперт по своему домашнему хозяйству, а это значит, что вы перед походом в магазин уже оцениваете вероятности этих двух альтернативных событий. Предположим, вероятность того, что в доме много продуктов, равна 0,4. Тогда 1 - 0,4 = 0,6 - вероятность того, что в доме мало продуктов. Итак, имея оценки вероятностей альтернативных событий, мы решая ту или иную задачу методом дерева решений, можем прогнозировать исходы. Как это сделать, мы узнаем, когда рассмотрим второй пример.
Построение дерева решений
Продолжим двигаться к более сложным примерам. Определим дерево решений более подробно. Дерево решений строится в виде графа-дерева, обладающего следующими свойствами:
- имеются вершины альтернативных решений, которые обычно отображаются в виде прямоугольников;
- имеются вершины событий, которые обычно отображаются с помощью окружностей;
- имеются вершины конечных решений (листья), которые обычно отображаются с помощью прямоугольников, имеющих другой цвет, чем вершины альтернативных решений;
- вершина альтернативных решений вместе с дугами, выходящими из данной вершины, называется вилкой решений;
- вершина событий вместе с дугами, выходящими из данной вершины, называется стохастической вилкой (стохастической - имеющей вероятностный характер, так как в процессе принятия решения учитываются вероятности каждого из событий);
- каждой дуге вилки решений приписаны весы, которые характеризуют приобретения или убытки при реализации данного решения;
- каждой дуге стохастической вилки приписываются весы, которые характеризуют вероятность соответствующего события, а также приобретения и убытки при реализации данного события.
Построить дерево решений можно с помощью бесплатного конструктора графиков и диаграмм Canva.
Анализ дерева решений
При решении прикладных задач методом дерева решений поступают следующим образом:
- на первом шаге проходят от начальной вершины к такой конечной вершине (листу), которой соответствует наибольшее приобретение, не учитывая при этом вероятности событий, предшествующих решениям;
- на втором шаге учитывают вероятности событий, предшествующих решениям; приобретения на вершинах, отображающих конечные решения, рассчитывают с учётом вероятностей событий, предшествующих решениям.
Пример 2. Решить методом дерева решений задачу прогнозирования приобретений и убытков при альтернативах решений.
Строительная фирма собирается принять решение о строительстве жилого комплекса (ЖК) в элитном районе. Сначала требуется принять решение: проводить ли информационно-рекламную кампанию. Она стоит 500000 условных единиц (у.е.). Опыт показывает, что лишь в 25 % случаев этот шаг обеспечивает успех на рынке.
Если информационно-рекламная кампания успешна, требуется принять решение: строить ли большой или малый ЖК. Строительство малого ЖК обойдётся в 50000000, при этом можно построить 300 квартир. Строительство большого ЖК обойдётся в 200000000, при этом можно построить 900 квартир.
Имеются исследования прогноза спроса. Они показывают, что существует вероятность в 40 % того, что произойдёт падение спроса на элитное жильё.
По предварительным расчётам, средние цены на квартиры будут определяться следующим образом:
| Большой ЖК | Малый ЖК | |
| Спрос снизится | 100 000 | 150 000 |
| Спрос не снизится | 250 000 | 400 000 |
Рассчитано, что расходы фирмы перед и в период продажи всех квартир в ЖК составят 5000000, независимо от величины ЖК.
Требуется принять решение: проводить ли информационно-рекламную кампанию и начинать строительство ЖК.
Решение.
Строим дерево решений:
Последствия альтернативных решений получены при расчётах, которые приведены ниже.
Шаг 1 (не учитываются вероятности событий).
Малый ЖК
Спрос не снизится
| Доходы | Расходы | Прибыль |
| 400000 * 300 = 120000000 | 50000000 + 5000000 = 55000000 | 120000000 - 55000000 = 65000000 |
Спрос снизится
| Доходы | Расходы | Прибыль |
| 150000 * 300 = 45000000 | 50000000 + 5000000 = 55000000 | 45000000 - 55000000 = -10000000 |
Большой ЖК
Спрос не снизится
| Доходы | Расходы | Прибыль |
| 250000 * 900 = 225000000 | 200000000 + 5000000 = 205000000 | 225000000 - 205000000 = 20000000 |
Спрос снизится
| Доходы | Расходы | Прибыль |
| 100000 * 900 = 90000000 | 200000000 + 5000000 = 205000000 | 90000000 - 205000000 = -115000000 |
Шаг 2 (учитываются вероятности событий).
На этом шаге прогнозируемые приобретения фирмы рассчитываются с учётом вероятности событий, предшествующих альтернативам решений.
| Расходы | |
| Малый ЖК | 0,60 * 65000000 + 0,40 * (-10000000) = 35000000 |
| Большой ЖК | 0,60 * 20000000 + 0,40 * (-115000000) = -34000000 |
Теперь следует рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию). Для этого нужно рассчитать приобретения при вершинах 4 (неуспешная информационно-рекламная кампания) и 5 (успешная информационно-рекламная кампания).
Наступление события при вершине 5 (строительство ЖК) означает максимальную прибыль 35000000, которую только можно получить при выборе данного решения. Наступление события при вершине 4 (неуспешная информационно-рекламная кампания) означает убытки в 500000.
Теперь можно рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию): 0,25 * 35000000 + 0,75 * (-500000) = 8750000 - 375000 = 8375000.
В результате применения метода дерева решений выбирается следующая альтернатива: начать информационно-рекламную кампанию и готовиться к строительству ЖК, отдавая предпочтение малому ЖК.
Следует отметить, что на практике при выборе решения методом дерева решений в случае инвестиционных проектов строятся пессимистический и оптимистический прогнозы. Они отличаются соотношениями вероятностей благоприятного и неблагоприятного исходов событий. Для каждого исхода, таким образом, рассчитываются оптимистические и пессимистические значения.
Построить дерево решений можно с помощью бесплатного конструктора графиков и диаграмм Canva.
Дерево игры
Дерево игры очень похоже на дерево решений.
Теория игр вообще занимается попыткой выразить особенности столкновения интересов через действия, которые имеют место в салонных играх. Правила любой салонной игры устанавливают последовательность вполне определённых ходов, причём каждый ход для данного игрока соответствует выбору одной из множества альтернатив.
В игре нужно учитывать все ходы, предшествующие данному ходу, и все возможные ходы, следующие за ним. Таким образом, значение каждого хода в игре зависит от других ходов. Если создать отвлечённое представление всех ходов игры и указать, какие выборы привели к каждому ходу, то можно узнать отвлечённую связь каждого хода со всеми другими ходами, которые повлияли на него или на которые он может повлиять.
Пример 3. В некоторой игре (на каком-то этапе партии) игроку 1 нужно выбрать между королём червей, двойкой пик и валетом бубен, а в другой игре игрок, также называемый игроком 1, должен выбрать между тем, чтобы пасовать, назначать игру или вистовать. В обоих случаях нужно выбрать между тремя альтернативами. Это можно представить на рисунке ниже.
Пример 4. Число, связанное с каждым ходом, указывает, какой игрок делает выбор на данном ходе. Следовательно, если имеется n игроков, то будут употребляться числа от 1 до n. Пусть n=4, тогда каждый ход, за исключением первого, назначается одному из игроков. Первому ходу приписывается обозначение "0". Ход с обозначением "0" является случайным ходом, как, например, тасовка карт перед партией покера. С каждым случайным ходом, который необязательно должен быть первым ходом, нужно связать распределение вероятностей или весов по нескольким альтернативным выборам. Если случайным ходом является бросание уравновешенной монеты, то в ходе имеются две альтернативы, и каждая из них может осуществиться с вероятностью 1/2.
Типы и принципы построения математических моделей в виде графов
Математические модели создаются с целью лучшего понимания изучаемого явления. Достаточно сложные системы невозможно анализировать без помощи упрощённых моделей. Исследование системы с перенесением его свойств на модель называется моделированием. Математическое моделирование позволяет абстрагироваться от физических и прочих специфических свойств объекта. Математическая модель - это упрощённое и самодостаточное в понятийном плане отображение реальности.
Определение 1. Математическая модель - задание системы или явления любого происхождения и любой природы в виде математических объектов и взаимосвязей.
Определение 2. Математическая модель - приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики.
Любая математическая модель предполагает наличие объектов и взаимосвязей между ними.
Сформулируем основные принципы моделирования.
- Выбор модели существенно влияет на процесс решения задачи и на само решение.
- Степени детализации модели могут быть разными.
- Более подробная детализация означает бОльшую сложность модели.
- Лучшие модели - те, которые лучше отображают реальность.
- Желательно использовать одновременно несколько моделей.
Есть бесчисленное множество примеров, когда в явлении, системе или процессе усмотрели отношения в виде графа, реализовали математическую модель на основе этих отношений и эта реализация сделала анализ задачи и решение более эффективными. Приведём основные типы математических моделей в виде графов:
- вершины и рёбра - физические объекты, объекты-рёбра физически связывают вершины;
- вершины - физические или нефизические объекты, рёбра связывают вершины в зависимости от структурных или функциональных свойств вершин;
- вершины - физические или нефизические объекты, возможно, в различных состояниях, зависящих от времени и развития, рёбра показывают временнУю, эволюционную или причинно-следственную связь между вершинами.
Есть два условия создания эффективной математической модели системы в виде графа:
- определены важнейшие подсистемы или состояния моделируемой системы, которые отображаются в виде вершин графа;
- определены важнейшие отношения между объектами-вершинами.
Чаще используются модели, в которых основную роль играют вершины графа, а не его рёбра.
Есть, однако, системы, для которых невозможно построить модели в виде графа. Обычно это системы, свойства которых непрерывны, например, атмосферные явления, потоки жидкостей и т.п. Таким образом, главное условие возможности построения модели в виде графа - дискретный (конечный, прерывный) характер системы, являения или процесса.
Системы со свойствами непрерывности целесообразнее моделировать с помощью уравнений математической физики.
Но и системы с дискретным характером не всегда уместно моделировать с помощью графов. Например, если цель решения задачи - оптимизация, то для этого больше подходит составление и решение задачи математического программирования, в частности, линейного программирования, не требующей анализа взаимосвязей между объектами.
Виды математических моделей в виде графа
Вместе с рассмотренными моделями дерева решений и дерева игры используются следующие математические модели в виде графа.
- Блок-схема компьютерной программы (вершины - команды, рёбра - переходы между команды), используемая для разработки и тестирования самой программы.
- Граф подпрограмм (вершины - подпрограммы, рёбра - порядок вызова подпрограмм), используемый для проектирования и анализа компьютерных программ.
- Граф структуры данных (вершины - данные или простейшие типы данных, рёбра - отношения между данными), используемый для проектирования и оптимизации структур данных.
- Граф зависимости команд машинного кода (вершины - команды, рёбра - зависимости между командами), используемый в оптимизационном компилировании и конвейеризации работы процессора.
- Граф процессов операционной системы (вершины - процессы операционной системы, рёбра - акты генерирования процессов), используемый в моделировании работы операционной системы.
- Граф конечного автомата (вершины - состояния автомата, рёбра - переходы), используемый в исследовании конечных автоматов и языков и в инженерии программного обеспечения.
- Граф утверждений математической теории (вершины - утверждения, рёбра - отношения логического следования), используемый для доказательства математических заключений и анализа математических теорий.
- Функциональный граф (вершины - элементы множества, рёбра - отношения логического следования), имеющий широкое использование в математике.
- Граф величин-зависимостей (вершины - численные величины и взаимосвязи между ними, рёбра - отношения вовлечённости величины), используемый в решении различных математических задач.
- Граф метрики (вершины - любые физические или нефизические объекты или их множества, рёбра - геометрическая, структурная, функциональная или эволюционная близость этих объектов), используемый для анализа больших множеств.
- Дерево решений (вершины - критические состояния, рёбра - решения), используемый в принятии решений в экономике, управлении, диагностике инженерных систем.
- Системный граф (вершины - компоненты системы, рёбра - взаимодействие компонент), используемый в проектировании и анализе систем.
- Граф обратных связей (вершины - параметры какого-либо процесса, ориентированные рёбра с весами "+" или "-" - зависимость изменений параметров, соответствующих вершинам), используемый в исследованиях изменений составных частей процессов или объектов.
- Граф причинно-следственных связей (вершины - состояния какой-либо системы, ориентированные рёбра - причинно-следственные связи), используемый в исследованиях больших систем и сложных процессов.
- Граф конфликтов (вершины - состояния какой-либо системы, рёбра - конфликты между состояниями), используемый в анализе систем.
- Граф игры (вершины - игровые состояния, рёбра - разрешённые правилами игры переходы между состояниями (ходы)), используемый в разработке победных стратегий в играх.
- Компьютерная сеть (вершины - компьютеры или коммуникационные узлы, рёбра - линии связи), используемая в проектировании и анализе компьютерных сетей.
- Социальный граф (вершины - люди или множества людей, рёбра - отношения знакомства, экономические отношения или другие отношения), используемый в анализе общества и планировании развития.
- Организационный граф (вершины - люди или множества людей, рёбра - отношения, характеризующие организации, например, частные фирмы, иерархии), используемый в создании организаций и управлении ими.
- Граф проекта (вершины - работы или состояния проекта, рёбра - отношения между работами или работы, соединяющие состояния), используемый в руководстве проектами.
- Генеалогическое древо (вершины - люди, рёбра - отношение "родители-дети"), используемый в личных исследованиях.
- Граф экономических агентов (вершины - экономические агенты - люди, фирмы и др., рёбра - экономические отношения), используемый в экономических исследованиях и планировании.
- Макроэкономический граф финансового потока (вершины - отрасли экономики, рёбра - финансовые потоки), используемый в экономических исследованиях и планировании.
- Граф дорог (вершины - города, рёбра - дороги), используемый в развитии транспортной сети.
- Граф улиц (вершины - перекрёстки, рёбра - улицы), используемый в анализе и планировании потока городского транспорта.
- Граф электрической цепи (вершины - электромагнитно-активные элементы, рёбра - провода и контакты), используемый в построении и анализе электрических счем.
- Цепь питания (вершины - породы животных, рёбра - отношения питания), используемый в анализе биосистем.
- Дерево эволюции (вершины - породы или популяции, рёбра - отношения эволюционного происхождения), используемый в биологии.
- Граф химических реакций (вершины - векторы количества химических веществ, рёбра - химические реакции), используемый в анализе химических реакций.
- Граф предшественников химического вещества (вершины - химические вещества, полученные в процессе производства, рёбра - изменения веществ-предшественников в процессе производства), используемый в химической промышленности.
- Граф реакционной способности химических веществ (вершины - химические вещества, рёбра - способности к реакции), используемый в анализе сложных химических реакций.
- Граф взрывоопасности (вершины - химические вещества, рёбра - возможности взрывной реакции между ними), используемый для нужд безопасности труда.
- Граф помех радиосвязи (вершины - радиостанции, рёбра - взаимное перекрытие полос радиоволн), используемый в планировании радиосвязи.
- Политический граф (вершины - государства, рёбра - границы), используемый в геополитике.
- Граф кровеносных сосудов (вершины - узлы кровеносных сосудов, рёбра - кровеносные сосуды), используемый в медицине.
- Граф нейронов (вершины - нейроны, рёбра - места соприкосновения нейронов), используемый в медицине.
- Граф приготовления кулинарного изделия (вершины - состояния готовности кулинарного изделия, рёбра - переходы между состояниями в процессе приготовлении), используемый в кулинарии.
| Назад<<< | Листать | Вперёд>>> |
