по
Программные системы и вычислительные методы
12+
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > Требования к статьям > Политика издания > Редакция > Порядок рецензирования статей > Редакционный совет > Ретракция статей > Этические принципы > О журнале > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала
ГЛАВНАЯ > Вернуться к содержанию
Статьи автора Галочкин Владимир Иванович
Программные системы и вычислительные методы, 2018-2
Галочкин В.И. - Поиск на графе k путей минимальной суммарной длины c. 60-66

DOI:
10.7256/2454-0714.2018.2.25124

Аннотация: Рассматривается задача поиска на взвешенном ориентированном графе k непересекающихся путей минимальной суммарной длины из заданной начальной вершины во все остальные вершины при неотрицательных весах дуг. Показывается, что нельзя использовать «жадный» подход, то есть находить лучший путь, удалять из графа вершины этого пути вместе с инцидентными дугами и повторять поиск. Задача сводится к поиску кратчайших путей на неявном графе из n^k вершин с некоторыми дополнительными ограничениями, где n – число вершин исходного графа. Разреженность неявного графа позволяет использовать рациональные структуры данных, уменьшая сложность алгоритма поиска путей. Выполнена программная реализация описанного алгоритма. В процессе тестирования генерировались полные графы с такими значениями весов дуг, при которых пути минимальной суммарной длины состояли из большого числа дуг. В практических целях и по вычислительным возможностям интерес представляют небольшие значения k. В этом случае корректно считать значение k константой, и сложность алгоритма оценивается величиной O(n^(k+1)log n). Необходимые затраты памяти составляют O(n^k). Время работы программы на различных тестах не противоречит полученным оценкам сложности алгоритма.
Программные системы и вычислительные методы, 2014-2
Галочкин В.И. - Перечисление решающих деревьев ограниченной стоимости на И-ИЛИ дереве

DOI:
10.7256/2454-0714.2014.2.11925

Аннотация: Рассматриваются И-ИЛИ деревья с заданной стоимостью дуг либо вершин, широко применяемые в системах искусственного интеллекта. Описывается алгоритм типа ветвей и границ, позволяющий перечислить все решающие деревья, стоимость которых не превышает наперед заданной константы. Трудоемкость получения очередного решающего дерева составляет O(N), где N – количество вершин И-ИЛИ дерева. Указывается способ стековой организации информации, позволяющий свести затраты памяти к величине O(N) без изменения прежней оценки трудоемкости. Выполнена программная реализация описанного алгоритма, подтвердившая при тестировании полученные теоретические оценки трудоемкости и объема необходимой памяти. Эффективность поиска повышена благодаря введенному понятию минимальной оболочки И-ИЛИ дерева по ограничению стоимости, что позволяет гарантировать наличие допустимых решающих деревьев при спуске по дереву решений. Решающие поддеревья перечисляются не по отдельности, а блоками в виде поддеревьев И-ИЛИ дерева, в которых все варианты допустимы.
Программные системы и вычислительные методы, 2012-11
Галочкин В.И. - Задачи заключительного тура международной интернет-олимпиады по информатике и программированию 2012 года для студентов вузов России и ближайшего зарубежья
Аннотация: Рассмотрены решения всех девяти задач олимпиады. Тематика задач связана с построением рациональных структур данных, целочисленной арифметикой, вычислительной геометрией, расчетами на графах, выбором эвристик, поиском экстремумов. Приведен алгоритм нахождения максимальной пропускной способности ребер графа по двум непересекающимся путям. Данный алгоритм практически без изменений может быть использован для поиска двух непересекающихся путей на графе минимальной суммарной стоимости. Указан способ для определения возможности разделения без вращения плоской геометрической фигуры по разрезу в форме ломаной. В одной из задач существенно увеличена размерность исходных данных по сравнению с известной задачей. Предложен подход, предусматривающий разные способы решения в зависимости от размерности исходных данных. Другие задачи внешне похожи на известные, но требуют иного решения. Такими являются задачи о расстановке ферзей на шахматной доске и оптимальному распилу бруса.
Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.