DOI: 10.7256/2454-0714.2016.4.20851

Аннотация: Рассматриваются широко применяемые в системах искусственного интеллекта И-ИЛИ деревья с заданными значениями показателей в терминальных дугах либо вершинах. Показатели рекурсивно определены на решающих деревьях с помощью непрерывных и монотонных по каждому аргументу функций свертки. Ставится задача перечисления решающих деревьев, удовлетворяющих системе ограничений на показатели. Для случая единственного аддитивного показателя ранее предложен линейный по сложности и памяти алгоритм, но уже для двух показателей не существует полиномиальных алгоритмов решения задачи. Предлагаются два алгоритма типа ветвей и границ. Первый алгоритм реализует последовательное выделение поддеревьев допустимых решений по ограничениям на отдельные показатели. Второй алгоритм позволяет эффективно отсекать недопустимые поддеревья. В основе обоих алгоритмов лежит введенное понятие минимальной оболочки И-ИЛИ дерева по монотонному ограничению. Первый алгоритм более применим при наличии большого числа решений системы неравенств, поскольку позволяет выбирать допустимые варианты не по отдельности, а блоками в виде поддеревьев И-ИЛИ дерева. Второй алгоритм ориентирован на случай, когда система неравенств имеет небольшое число решений.

DOI: 10.7256/2454-0714.2014.2.11925

Аннотация: Рассматриваются И-ИЛИ деревья с заданной стоимостью дуг либо вершин, широко применяемые в системах искусственного интеллекта. Описывается алгоритм типа ветвей и границ, позволяющий перечислить все решающие деревья, стоимость которых не превышает наперед заданной константы. Трудоемкость получения очередного решающего дерева составляет O(N), где N – количество вершин И-ИЛИ дерева. Указывается способ стековой организации информации, позволяющий свести затраты памяти к величине O(N) без изменения прежней оценки трудоемкости. Выполнена программная реализация описанного алгоритма, подтвердившая при тестировании полученные теоретические оценки трудоемкости и объема необходимой памяти. Эффективность поиска повышена благодаря введенному понятию минимальной оболочки И-ИЛИ дерева по ограничению стоимости, что позволяет гарантировать наличие допустимых решающих деревьев при спуске по дереву решений. Решающие поддеревья перечисляются не по отдельности, а блоками в виде поддеревьев И-ИЛИ дерева, в которых все варианты допустимы.

Аннотация: Рассмотрены решения всех девяти задач олимпиады. Тематика задач связана с построением рациональных структур данных, целочисленной арифметикой, вычислительной геометрией, расчетами на графах, выбором эвристик, поиском экстремумов. Приведен алгоритм нахождения максимальной пропускной способности ребер графа по двум непересекающимся путям. Данный алгоритм практически без изменений может быть использован для поиска двух непересекающихся путей на графе минимальной суммарной стоимости. Указан способ для определения возможности разделения без вращения плоской геометрической фигуры по разрезу в форме ломаной. В одной из задач существенно увеличена размерность исходных данных по сравнению с известной задачей. Предложен подход, предусматривающий разные способы решения в зависимости от размерности исходных данных. Другие задачи внешне похожи на известные, но требуют иного решения. Такими являются задачи о расстановке ферзей на шахматной доске и оптимальному распилу бруса.