Узлы

Узлы в дереве решений обозначают отдельные шаги в задаваемом деревом алгоритме.
В коде узлы представлены классами пакета its.model.nodes.

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

Ветви мысли, ThoughtBranch

Если не углубляться в отдельные узлы дерева решений, в нем можно выделить отдельные ветви мысли. Сами по себе ветви представляют некоторую логически завершенную часть полного алгоритма, и отвечают на какой-то конкретный вопрос.
В аналогии с обычными языками программирования ветви мысли соответствуют отдельным функциям/процедурам.

В коде ветви мысли представлены классом ThoughtBranch, и имеют ссылку на узел, представляющий их начало - ThoughtBranch.start.

Результаты ветвей мысли

Аналогично любой функции, ветвь мысли должна выдавать результат - ответ на соответствующий ей вопрос. В этом смысле все дерево является одной большой ветвью мысли (которое зачастую разделяется на более мелкие) - поскольку выдает ответ на основной вопрос задачи.
По результату своего выполнения, ветви мысли могут иметь следующие результаты, представленные в коде перечислением BranchResult

  • Правильно/верно/true (BranchResult.CORRECT) - с точки зрения данной ветви все выполнено правильно, ответ на вопрос ветви "Да".
  • Неправильно/ошибка/false (BranchResult.ERROR) - с точки зрения данной ветви была допущена ошибка, ответ на вопрос ветви "Нет".
  • Неизвестно/невозможно определить корректность/null (BranchResult.NULL) - данная ветвь не смогла выдать определенный ответ; либо ситуация слишком неожиданная, либо ветвь решает "передать управление" далее по дереву.

Выдаваемый ветвью результат определяется в последнем узле, в который пришло его выполнение. В коде классы узлов, которые могут так выдавать результаты, реализовывают интерфейс EndingNode - это либо узлы результатов, либо узлы агрегации.

Узлы результатов, BranchResultNode

Узлы результатов представляют собой основной способ завершить ветвь мысли и вернуть из нее какой-то результат.
nodes_BranchResultNode.png
В коде они представлены классом BranchResultNode, и содержат следующую информацию:

  • BranchResultNode.value - результат, возвращаемый узлом.
  • BranchResultNode.actionExpr (может отсутствовать) - выражение, задающее действие, которое необходимо выполнить по достижении этого узла.

Поведение при прорешивании:

  1. Если оно есть, то выполняется выражение BranchResultNode.actionExpr
  2. Текущая ветвь мысли считается завершенной с результатом BranchResultNode.value.

Валидация:

  • Выражение BranchResultNode.actionExpr должно быть валидным, и соответствовать известной в дереве на данный момент информации.

Связующие узлы и переходы между узлами

Основное множество узлов, имеющих собственную внутреннюю логику, называются "связующими", поскольку предполагают переход к другим узлам (а то есть связь с ними).
В коде такие узлы наследуются от класса LinkNode.

Основной отличительной чертой таких узлов является набор переходов, представленный в коде полем LinkNode.outcomes. Данное поле имеет тип Outcomes, и по сути представляет собой соответствие ключа перехода и узла, к которому должен быть совершен переход. Данное соответствие представлено коллекцией единичных переходов (объектов класса Outcome), каждый из которых хранит соответствующие ключ Outcome.key и узел Outcome.node.
В процессе прорешивания из узла совершается тот переход, чей ключ соответствует ответу узла (тип этого ответа и ключей переходов зависит от конкретной специфики узла).

Стоит отметить, что каждый отдельный переход Outcome в контейнере Outcomes наследуется от класса DecisionTreeElement, а значит может иметь метаданные. Это бывает полезно, поскольку бывают случаи привязки метаданных не к узлу в общем, а к конкретному переходу из него.

Вопросы

Большинство узлов в типичном дереве решений является узлами вопросов. Данные узлы представляют собой необходимость выполнить некоторые рассуждения над ситуацией (задаться некоторым вопросом), и в зависимости от результата этих рассуждений (ответа на вопрос) совершить переход к различным следующим узлам.

Обычный вопрос, QuestionNode

nodes_QuestionNode.png
Обычный узел вопроса представлен классом QuestionNode, и содержит следующую информацию:

  • QuestionNode.expr - выражение, представляющее рассуждения (вопрос) в этом узле
  • QuestionNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является результат выражения QuestionNode.expr.
  • QuestionNode.trivialityExpr (может отсутствовать и в большинстве случаев отсутствует) - предикат тривиальности: булево выражение, возвращающее true, если узел должен считаться тривиальным. Тривиальные узлы считаются очевидными, и на них не должно заостряться внимание пользователя. При прорешивании тривиальность напрямую не используется, а является вспомогательной информацией для сторонних проектов.
  • QuestionNode.isSwitch (может отсутствовать и в большинстве случаев отсутствует) - флаг, означающий, что узел это тривиальная развилка ("switch"). Аналогично QuestionNode.trivialityExpr, но константа.

Поведение при прорешивании:

  1. Вычисляется выражение QuestionNode.expr
  2. Среди переходов QuestionNode.outcomes находится тот, чей ключ соответствует результату вычисления выражения
    • Если такого нет, то выкидывается ошибка
  3. Решение переходит к узлу, соответствующему найденному переходу.

Валидация:

  • Вложенные выражения должны быть валидными, и соответствовать известной в дереве на данный момент информации.
  • Типы ключей всех переходов QuestionNode.outcomes должны соответствовать типу возвращаемого значения выражения QuestionNode.expr
  • Тип возвращаемого значения выражения QuestionNode.trivialityExpr должен быть булевым значением.

Вопрос с кортежем (с несколькими частями), TupleQuestionNode

nodes_TupleQuestionNode.png
Узел вопроса с кортежем или вопроса с несколькими частями отличается от обычного тем, что совершает несколько проверок одновременно, и совершает переход в зависимости от комбинаций ответов на них.

Узел вопроса с кортежем представлен классом TupleQuestionNode, и содержит следующую информацию:

  • TupleQuestionNode.parts - список отдельных частей данного вопроса. Каждая такая часть представлена классом TupleQuestionPart и содержит следующую информацию:
    • TupleQuestionPart.expr - выражение, представляющее рассуждения (вопрос) в этой части узла
    • TupleQuestionPart.possibleOutcomes - вспомогательный список ожидаемых результатов вычисления выражения TupleQuestionPart.expr. При прорешивании напрямую не используются, а являются вспомогательной информацией для сторонних проектов.
  • TupleQuestionNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является объект ValueTuple - кортеж значений, составляемый из результатов вычислений выражений TupleQuestionPart.expr всех частей TupleQuestionNode.parts данного узла.

Поведение при прорешивании:

  1. Для всех частей TupleQuestionNode.parts вычисляется их выражение TupleQuestionPart.expr
  2. Из полученных результатов составляется кортеж ValueTuple
  3. Среди переходов TupleQuestionPart.outcomes находится тот, чей ключ (кортеж) соответствует полученному на предыдущем шаге кортежу результатов
    • Если такого нет, то выкидывается ошибка
  4. Решение переходит к узлу, соответствующему найденному переходу.

Валидация:

  • В узле должно быть как минимум две части TupleQuestionNode.parts (иначе нужно использовать QuestionNode)
  • Для каждой части TupleQuestionNode.parts:
    • Вложенные выражения должны быть валидными, и соответствовать известной в дереве на данный момент информации.
    • Типы ожидаемых результатов TupleQuestionPart.possibleOutcomes должны соответствовать типу возвращаемого значения выражения TupleQuestionPart.expr
  • Ключи всех переходов TupleQuestionPart.outcomes должны быть кортежами ValueTuple, а также количество и типы значений в этих кортежах должны соответствовать количеству и типу выражений в частях узла.

Действия

Узлы действий представляют собой некоторую манипуляцию с данными о задаче - необходимо либо изменить ситуацию, либо получить и запомнить некоторую информацию.

Действие поиска (найти объект и запомнить), FindActionNode

nodes_FindActionNode.png
Узел действия поиска по своей сути аналогичен оператору присвоения в обычном языке программирования - он получает (находит) некоторый объект, и запоминает его как некоторую переменную дерева мысли.
Данная переменная впоследствии доступна из всех выражений в узлах этой ветви мысли (но не за пределами этой ветви мысли).

Узел действия поиска представлен классом FindActionNode, и содержит следующую информацию:

  • FindActionNode.varAssignment - основное объявление/присвоение переменной. Имеет тип DecisionTreeVarAssignment, содержащий следующую информацию:
    • DecisionTreeVarAssignment.variable - информация о переменной. Содержит тип (TypedVariable.className) и имя (TypedVariable.varName) переменной.
    • DecisionTreeVarAssignment.valueExpr - выражение для вычисления значения переменной. Должно вернуть объект.
  • FindActionNode.errorCategories - вспомогательный список категорий ошибок. При прорешивании напрямую не используются, а являются вспомогательной информацией для сторонних проектов. Каждая категория ошибок имеет тип FindErrorCategory, и содержит следующую информацию:
    • FindErrorCategory.priority - приоритет данной категории ошибок. Eсли объект соответствует нескольким категориям, то будет выбрана категория с наивысшим приоритетом (1 считается наивысшим приоритетом, и далее 2, 3.. по убыванию)
    • FindErrorCategory.selectorExpr - выражение предикат поиска: булево выражение, которое должно вернуть true, если объект соответствует данной категории ошибки. Проверяемый объект в данном выражении представлен контекстной переменной с именем "checked".
  • FindActionNode.secondaryAssignments - т.н. "вторичные" объявления/присвоения переменных. Представляют собой список присвоений DecisionTreeVarAssignment (данный класс уже был описан выше). Данные присвоения выполняются только в случае, если основное FindActionNode.varAssignment было успешно выполнено. Также, во вторичных присвоениях также можно ссылаться на основную переменную узла. Таким образом, вторичные присвоения можно использовать, если в одном узле необходимо объявить сразу несколько связанных переменных. При этом предполагается, что внимание студента заостряется только на основном присвоении.
  • FindActionNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является булево значение - true, если основное присвоение успешно выполнено (объект найден), false в противном случае. Переход с ключом false может отсутствовать, если предполагается, что объект всегда будет найден; переход с ключом true должен быть обязательно.

Поведение при прорешивании:

  1. Для основного присвоения FindActionNode.varAssignment вычисляется выражение DecisionTreeVarAssignment.valueExpr
  2. Если значение основного присвоения не было найдено, то решение переходит к узлу, соответствующему переходу с ключом false
  3. Если значение основного присвоения было найдено, то данный объект-значение запоминается в переменную дерева, соответствующую описанию переменной DecisionTreeVarAssignment.variable в основном присвоении FindActionNode.varAssignment
  4. Аналогично основному присвоению выполняются все вторичные присвоения FindActionNode.secondaryAssignments: вычисляются объекты-значения, запоминаются переменные
    • Если на данном этапе какое-либо из вторичных присвоений не удается (объект-значение не найден), то выкидывается ошибка - предполагается, что такая ситуация невозможна.
  5. Решение переходит к узлу, соответствующему переходу с ключом true. Здесь и далее в этой ветви мысли переменные, объявленные в узле поиска, доступны в виде переменных дерева.

Валидация:

  • Вложенные выражения должны быть валидными и соответствовать известной в дереве на данный момент информации.
  • Выражения в присвоениях FindActionNode.varAssignment и FindActionNode.secondaryAssignments должны иметь возвращаемый тип Объект, соответствующий классу, заявленному для соответствующей переменной.
  • Тип возвращаемого значения выражений в FindActionNode.errorCategories должен быть булевым значением
  • Ключи всех переходов FindActionNode.outcomes должны быть булевыми значениями; переход с ключом true должен быть обязательно.

Другие действия

Note

На данный момент действие поиска - единственный узел действий в системе, поскольку до сих пор не возникало необходимости выполнять какие-то еще другие действия в "середине" решения.
Однако весьма вероятно, что в какой-то момент также понадобится узел выполнения произвольных выражений над операцией. На данный момент такие действия возможны только в рамках узлов результатов BranchResultNode - но они, закономерно, могут выполняться только в конце конкретной ветви мысли.

Агрегация и узлы агрегации

Аналогично же функциям, более высокоуровневые ветви мысли могут "вызывать" более низкоуровневые. Это происходит в случаях, если для определения ответа на вопрос высокоуровневой ветви нужны некие отдельные ответы на более низкоуровневые вопросы.

На данный момент в проекте выделено 4 вида агрегации (5, если считать последовательность). В коде эти виды представлены перечислением AggregationMethod. Рассмотрим их:

Независимые проверки по логическому И, SIM:AND
SIM от слова SIMultaneous, одновременно
nodes_sim_and.png
Применяется, когда необходимо сделать несколько проверок независимо друг от друга и отобразить их результат. При этом любая ошибка во вложенных ветвях приводит к ошибке в основной ветви.
Результат для основной ветви вычисляется так:

  1. null, если все ветви такие
  2. true, если все ветви либо true либо null
  3. false иначе
    При этом, из узла агрегации по SIM:AND всегда должен быть переход по true результату, т.к. в этом случае решение продолжается.

Независимые проверки по логическому ИЛИ, SIM:OR
nodes_sim_or.png
Применяется, когда необходимо сделать несколько проверок независимо друг от друга и отобразить их результат. При этом, если хотя бы одна из вложенных ветвей выполнена корректно, то и основная ветвь считается выполненной корректно.
Результат для основной ветви вычисляется так:

  1. null, если все ветви такие
  2. true, если хотя бы одна ветвь true
  3. false иначе
    При этом, из узла агрегации по SIM:OR всегда должны быть переходы по false и null результатам, т.к. эти случаи возникают только при рассмотрении всех ветвей вместе, поэтому рассматривать данные результаты нужно на верхнем уровне.

Взаимоисключающие проверки, MUTEX
MUTEX от слов MUTually EXclusive, взаимно исключающий
nodes_mutex.png
Применяется, когда необходимо сделать несколько проверок независимо друг от друга и отобразить результат одной из них - предполагается, что в любой ситуации только одна из данных проверок даст какой-либо определенный результат (true либо false), а все остальные выдадут неопределенность (null).
Результат для основной ветви вычисляется так:

  1. Если среди ветвей есть результат true или false, то берется он
  2. null иначе
    Обязательных переходов из узла агрегации по MUTEX нет, но чаще всего из него реализуется переход по null - "Если не выполнилось ничего из перечисленного то переходить сюда".

Гипотезы, HYP
HYP от слова HYPothesis, гипотеза
nodes_hyp.png
Применяется, когда системе необходимо делать предположения (гипотезы) о том, как мог бы рассуждать обучаемый, чтобы прийти к своему ответу, потому что сам ответ не дает однозначной информации для этого.
Результат для основной ветви вычисляется так:

  1. true, если хотя бы одна ветвь true
  2. false, если хотя бы одна ветвь false
  3. null иначе
    При этом, из узла агрегации по HYP всегда должны быть переходы по null результату, т.к. этот случай может возникнуть только при рассмотрении всех ветвей вместе, поэтому рассматривать его нужно на верхнем уровне.

Последовательность, SEQ
SEQ от слова SEQuence, последовательность
nodes_seq.png
Последовательность является особым видом агрегации, который на первый взгляд может даже не казаться агрегацией. Он применяется, когда необходимо последовательно выполнить несколько проверок и вернуть первый определенный (true или false) результат.

  • Учитывая эту формулировку, технически можно сказать, что большинство узлов в дереве объединяются агрегацией SEQ, поскольку идут последовательно друг за другом, и выполнение завершается на первом встреченном результате.
  • В то же время, агрегацию SEQ по ветвям нельзя реализовать аналогично остальным типам агрегации, поскольку он требует задания некоторого порядка, в котором проверяются ветви. Подробнее об этом см. WhileCycleNode. В связи с этим, SEQ отсутствует в перечислении AggregationMethod.
    Результат для основной ветви вычисляется так:
  1. Берется результат первой из ветвей, чей результат не null (true или false); последующие ветви не выполняются.
  2. Если все ветви выдали null, то null
    При этом, из узла агрегации по SEQ всегда должны быть переходы по null результату, т.к. именно в нем необходимо определить действия, выполняемые после завершения последовательности.

Узел агрегации по ветвям, BranchAggregationNode

nodes_BranchAggregationNode.png
Узел агрегации по ветвям предполагает агрегацию нескольких различных (непохожих друг на друга) проверок, представленных несколькими отдельными ветвями мысли. Это одна из двух основных форм агрегации, вторая - CycleAggregationNode

В коде данный узел представлен классом BranchAggregationNode и содержит следующую информацию:

  • BranchAggregationNode.aggregationMethod - метод агрегации результатов ветвей в данном узле.
  • BranchAggregationNode.thoughtBranches - список агрегируемых ветвей мысли.
  • BranchAggregationNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является результат агрегации вложенных ветвей BranchResult.

Поведение при прорешивании:

  1. Выполняются все вложенные ветви мысли BranchAggregationNode.thoughtBranches, их результаты запоминаются
  2. На основе метода агрегации BranchAggregationNode.aggregationMethod в данном узле, а также результатов вложенных ветвей, вычисляется результат BranchResult данного узла.
  3. Если у данного узла есть переход с ключом, соответствующим полученному результату, то решение переходит к узлу, соответствующему данному переходу. Иначе текущая ветвь мысли считается завершенной с результатом, соответствующим полученному.

Валидация:

  • Список агрегируемых ветвей BranchAggregationNode.thoughtBranches не должен быть пустым.
  • Переходы из узла должны содержать переходы с обязательными ключами, соответствующими виду агрегации.

Узел агрегации в цикле по объектам, CycleAggregationNode

nodes_CycleAggregationNode.png
Узел агрегации в цикле по объектам предполагает агрегацию нескольких однотипных проверок, применяющихся к нескольким объектам в задаче. Это вторая из двух основных форм агрегации, первая - BranchAggregationNode.

В коде данный узел представлен классом CycleAggregationNode и содержит следующую информацию:

  • CycleAggregationNode.aggregationMethod - метод агрегации результатов ветвей в данном узле.
  • CycleAggregationNode.thoughtBranch - ветвь мысли, представляющая тело цикла.
  • CycleAggregationNode.variable - переменная перебора цикла. Данная переменная доступна как переменная дерева в теле цикла (но не вне его).
  • CycleAggregationNode.selectorExpr - выражение предикат поиска: булево выражение, которое должно вернуть true для всех объектов, которые должны перебираться в цикле; проверяемый объект подставляется в предикат как контекстная переменная с именем и типом соответствующими переменной CycleAggregationNode.variable
  • CycleAggregationNode.errorCategories - вспомогательный список категорий ошибок. При прорешивании напрямую не используются, а являются вспомогательной информацией для сторонних проектов. Каждая категория ошибок имеет тип FindErrorCategory, который был подробно описан в разделе о FindActionNode
  • CycleAggregationNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является результат агрегации вложенных ветвей BranchResult.

Поведение при прорешивании:

  1. Перебираются объекты типа, объявленного для переменной цикла CycleAggregationNode.variable. Из них оставляются те, для которых предикат поиска CycleAggregationNode.selectorExpr выдает true
  2. Для каждого найденного объекта выполняется тело цикла CycleAggregationNode.thoughtBranch, результаты каждой итерации запоминаются. В теле цикла соответствующий объект доступен как переменная дерева с именем и типом, соответствующим переменной цикла CycleAggregationNode.variable.
  3. На основе метода агрегации CycleAggregationNode.aggregationMethod в данном узле, а также результатов итераций для объектов, вычисляется результат BranchResult данного узла.
  4. Если у данного узла есть переход с ключом, соответствующим полученному результату, то решение переходит к узлу, соответствующему данному переходу. Иначе текущая ветвь мысли считается завершенной с результатом, соответствующим полученному.

Валидация:

  • Вложенные выражения должны быть валидными и соответствовать известной в дереве на данный момент информации.
  • Тип возвращаемого значения выражения предиката поиска CycleAggregationNode.selectorExpr, а также выражений в CycleAggregationNode.errorCategories должен быть булевым значением
  • Переходы из узла должны содержать переходы с обязательными ключами, соответствующими виду агрегации.

Узел последовательной агрегации, WhileCycleNode

nodes_WhileCycleNode.png
Узел последовательной агрегации по сути аналогичен обычному циклу "while" в языках программирования. Поскольку агрегацию по SEQ невозможно выполнить в узлах агрегации по ветвям или по объектам, она вынесена в данный узел.
Данный узел во многом похож на цикл по объектам, но выполняет свое тело, пока выполняется некоторое условие, или пока не найден определенный (true или false) результат. Предполагается, что результат условия будет меняться из-за доп. действий в неопределенных узлах-результатах внутри тела цикла.

В коде данный узел представлен классом WhileCycleNode, и содержит следующую информацию:

  • WhileCycleNode.conditionExpr - выражение условия: булево выражение, которое должно выдавать true, если цикл должен продолжаться.
  • WhileCycleNode.thoughtBranch - ветвь мысли, представляющая тело цикла.
  • WhileCycleNode.outcomes (наследуется от LinkNode) - переходы к следующим узлам; ключом перехода является результат агрегации вложенных ветвей BranchResult.

Поведение при прорешивании:

  1. Пока выполяется условие цикла WhileCycleNode.conditionExpr, выполняется тело цикла WhileCycleNode.thoughtBranch.
  2. Если очередная итерация завершилась с результатом true или false, то этот результат считается итоговым, и цикл завершается. Иначе если WhileCycleNode.conditionExpr не выполняется (выдает false), то цикл считается завершенным с результатом null.
  3. Если у данного узла есть переход с ключом, соответствующим полученному результату, то решение переходит к узлу, соответствующему данному переходу. Иначе текущая ветвь мысли считается завершенной с результатом, соответствующим полученному.

Валидация:

  • Вложенные выражения должны быть валидными и соответствовать известной в дереве на данный момент информации.
  • Тип возвращаемого значения выражения условия цикла WhileCycleNode.conditionExpr должен быть булевым значением.
  • Переходы из узла должен содержать переход с ключом null.