Моделирование комбинаторных задач с помощью непрерывной логики

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