УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРШРУТОВ

Заявляемая полезная модель относится к области вычислительной техники, а именно, к устройствам для моделирования маршрутов графа, используемых, например, при решении задач, условия которых могут быть выражены в виде графов и их матриц, в частности, задачи поиска гамильтоновых маршрутов.
Известно устройство для моделирования маршрутов, описанное в газете «Вперед» №9(7489), 20 января 1990 г., г.Ленинград - Пушкин, стр.4. Устройство по прототипу содержит модели звеньев, снабженные каналами связи во встречных направлениях. Первые и/или вторые окончания каналов связи этих моделей звеньев соединены в соответствии с топологией графа и/или маршрутов соответственно со вторыми и/или первыми окончаниями каналов связи моделей смежных звеньев. Как минимум, в одной модели звена канал связи снабжен регистратором прохождения сигналов во встречных направлениях, выход которого соединен с выходом этой модели. То есть выход модели, в данном случае, является выходом ее регистратора.
Недостатком прототипа устройства для моделирования маршрутов является экспоненциальный рост затрат на моделирование маршрутов при увеличении количества вершин в графе.
Задача, положенная в основу полезной модели, заключается в снижении затрат на моделирование маршрутов, за счет моделирования одним сигналом всего множества маршрутов.
Поставленная задача решается тем, что устройство для моделирования маршрутов содержит модели звеньев, снабженные каналами связи во встречных направлениях. Причем первые и/или вторые окончания каналов связи моделей звеньев соединены, согласно топологии графа и/или маршрутов, соответственно со вторыми и/или первыми окончаниями каналов связи моделей смежных звеньев. По меньшей мере, в одной модели звена канал связи снабжен регистратором прохождения сигналов во встречных направлениях, выход которого соединен с выходом модели звена.
Новым является то, что заявляемое устройство дополнительно снабжено определителем соответствия смоделированных маршрутов требованиям моделирования, вход которого соединен с выходом, как минимум, одной модели звена.
Указанная совокупность признаков первого независимого пункта формулы представляет собой устройство, являющееся моделью маршрутов Р-го порядка, например, первого. При минимальных требованиях моделирования оно позволяет решить поставленную задачу с затратами, равными кубу количества вершин в графе.
Кроме того, в соответствии со вторым пунктом формулы в заявляемом устройстве, по меньшей мере, одна модель звена дополнительно снабжена устройством для моделирования маршрутов по п.1. /модель маршрутов (Р+1)-го порядка, например, второго/, выход определителя которого соединен с управляющим входом ключа, которым снабжен канал связи указанной модели звена. Это позволяет решить поставленную задачу при максимальных требованиях моделирования с затратами седьмой степени.
Использование заявленного устройства (первого порядка) позволяет использовать ее по отношению к отдельным звеньям маршрутов, что, в свою очередь, позволяет в этом дополнительном использовании (второго порядка) вновь дополнительно использовать в устройстве (третьего порядка) и т.д.
Принцип «матрешки», когда целое содержит часть, подобную целому, а эта часть содержит подчасть, подобную целому, и т.д., иллюстрирует технические решения.
Полезная модель поясняется следующими чертежами.
Фиг.1 и 2 - примеры графов. Фиг.3 - устройство для моделирования маршрутов Р-го порядка. Фиг.4 - модель звена-вершины Р-го порядка в модели маршрутов Р-го порядка, снабженная моделью (Р+1)-го порядка. Фиг.5 - модель звена-ветви Р-го порядка в модели маршрутов Р-го порядка, снабженная моделью маршрутов (Р+1)-го порядка. Фиг.6 - модель маршрутов графа, изображенного на фиг.2. Фиг.7 - график, иллюстрирующий снижение затрат на моделирование маршрутов.
На фигурах и в тексте описания применяются следующие обозначения для моделей звеньев. Модели звеньев-вершин обозначены трехзначными индексами, на первой позиции которых находится цифра 2 - обозначение, общее для всех моделей звеньев-вершин, на второй позиции - номер вершины, которая моделируется данной моделью, на третьей позиции - номер пункта, который моделируется данной моделью звена-вершины. Модели звеньев-ветвей обозначены четырехзначными индексами, на первой позиции которых находится цифра 3 - обозначение, общее для всех моделей звеньев-ветвей, на второй позиции - номер вершины, из которой исходит ветвь, моделируемая данной моделью звена-ветви, на третьей позиции - номер пункта, из которого исходит ветвь, моделируемая данной моделью, на четвертой позиции - номер вершины, в которую входит ветвь, моделируемая данной моделью звена-ветви. Номера вершин и пунктов обозначены цифрами и буквами.
Пример моделирования маршрутов графа с произвольным количеством вершин и ветвей (фиг.1). Устройство 1/Р/ (фиг.3) содержит модели звеньев-вершин 2 и модели звеньев-ветвей 3, снабженных каналами связи 4, причем первые 5 и/или вторые 6 окончания каналов связи 4 этих моделей звеньев 2, 3 соединены в соответствии с топологией графа и/или маршрутов соответственно со вторыми 6 и/или первыми 5 окончаниями каналов связи 4 моделей смежных звеньев 2, 3. По крайней мере, в одной модели звена 2, 3 канал связи 4 снабжен регистратором 7, выход 8 которого соединен с выходом 9 этой модели звена 2, 3. Кроме того, устройство 1/Р/ снабжено определителем 10, выполненным, например, в виде элемента «И», вход 11 которого соединен с выходом 9, по крайней мере, одной модели звена 2, 3.
На вхождения каналов связи 4 в устройство 1/Р/ посылают потоки любого вида энергии, например, переменный электрический ток. Если потоки энергии проходят во встречных направлениях через канал связи 4 модели звена, например, 2.A.1., то регистратор 7, расположенный на этом канале связи 4 приводят в рабочее состояние и с его выхода 8 посылают сигнал на выход 9 модели звена 2.A.1. На вход 11 определителя 10 посылают все необходимые импульсы из выходов 9 моделей звеньев 2, 3, и если определитель 10 приводят в рабочее состояние, то сохраняют совокупность всех импульсов на выходах 9 моделей звеньев 2, 3, представляющих собой один сформированный сигнал из импульсов, каждый из которых указывает на наличие определенных звеньев, по крайней мере, в одном из смоделированных маршрутах, что может быть зафиксировано в любой форме.
Другой пример представлен устройством, где, по крайней мере, одна модель звена 2, 3 снабжена заявляемым устройством 1/Р+1/ (фиг.4, 5), выход 12 (фиг.3) определителя 10 которого соединен с управляющим входом 13 (фиг.4) ключа 14 (фиг.4), которым снабжен канал связи 4 указанной модели звена 2, 3, следующим образом.
На вхождения каналов связи 4 в устройство 1/Р+1/, например, в звеньях 2.Е.К. (фиг.4) и 3.К-1.Е. (фиг.5), посылают потоки энергии, из сработавших регистраторов 7 через выходы 9 соответствующих моделей 2, 3 посылают импульсы на входы 11 определителя 10. Если определитель принял все необходимые импульсы (например, как элемент «И»), то его приводят в рабочее состояние и с его выхода 12 посылают сигнал на управляющий вход 13 ключа 14 соответствующего звена 2, 3 (2.Е.К. или 3.С.К-1.Е.) устройства 1/Р/, ключ 14 приводят в рабочее состояние, что позволяет каналу связи 4 данного звена 2, 3 пропускать энергию во встречных направлениях и регистратор 7 приводят в рабочее состояние, в результате чего с выхода 8 регистратора 7 через выход 9 данного звена 2, 3 посылают импульс на вход 11 определителя 10 устройства 1/Р/. Это позволяет моделировать маршруты с различными требованиями, например, исключая маршруты не проходящие данные звенья.
При необходимости передачи сформированного в устройстве 1/Р/ сигнала далее (за его пределы, например, на табло), выход 12 определителя 10 может быть соединен с управляющим входом 15 (фиг.3) триггера 16, сигнальный вход 17 которого соединен с выходом 9 соответствующей модели звена 2, 3, например, 2.Е.n+1. В этом случае, в результате приведения в рабочее состояние регистратора 7 канала связи 4 модели звена 2. 3 и определителя 10, приводят в рабочее состояние и соответствующий триггер 16, что обеспечит возможность вывода сформированного сигнала за пределы устройства 1/Р/ в виде совокупности импульсов на выходах 18 триггеров 16. Кроме того, описанное устройство и его элементы при необходимости, например, при решении задачи коммивояжера могут быть снабжены известными устройствами для ввода-вывода и обработки информации о параметрах маршрутов и их звеньях, что позволяет дополнительно осуществлять операции ввода-вывода и обработки соответствующей информации. В силу тривиальности описанного в данном абзаце его содержание не включено в формулу изобретения.
Для решения задачи о гамильтоновости графа приводится следующий пример устройства для моделирования маршрутов и его работа при моделировании маршрутов в графе G на четырех вершинах (фиг.2). Следует определить существует ли в графе G хотя бы один замкнутый маршрут, включающий в себя все вершины в точности по одному разу.
Это устройство 1/1/ (фиг.6) содержит модели звеньев 2.A.1, 3.А.1.С., 3.Е.2.С., 3.В.3.С. и 3.В.4.А., соединенные каналами связи 4 в соответствии с топологией графа G. В каждой модели звена 2, 3 ее канал связи 4 снабжен регистратором 7, выход 8 которого соединен с выходом 9 этой модели 2, 3, который соединен со входом 11 определителя 10. Кроме того, звенья 3 снабжены устройствами 1/2/, выходы 12 определителей 10 которых соединены с управляющими входами 13 ключей 14, которыми снабжены каналы связи 4 указанных моделей звеньев 3.
В свою очередь, модель маршрутов 1/2/ звена 3.А.1.С. устройства 1/1/ содержит модели звеньев 3.А.1.С. и 3.В.2.А., соединенные каналами связи 4 в соответствии с топологией графа G. Каналы связи 4 этих моделей звеньев 3 снабжены регистраторами 7, выходы 8 которых, через выходы 9 этих моделей звеньев 3 соединены с соответствующими входами 11 определителя 10.
Аналогично построены устройства 1/2/ других моделей звеньев 3 устройства 1/1/, с тем лишь отличием, что содержат иные модели звеньев 2, 3. Так модель маршрутов второго порядка 1/2/ модели звена 3.Е.2.С.устройства 1/1/ содержит модели звеньев 2.A.L, 3.Е.2.С., 2.С.3. и 3.В.4.А., устройство 1/2/ модели звена 3.В.3.С. устройства 1/1/ содержит модели звеньев 3.С.2.В. и 3.В.3.С., а устройство 1/2/ модели звена 3.В.4.А. устройства 1/1/ содержит модели звеньев 2.A.L, 3.Е.2.С., 2.С.3., 3.В.3.С., 3.В.4.А. и 3.А.1.С.. Причем последняя модель звена снабжена устройством 1/3/, выход определителя 10 которого соединен с управляющим входом 13 ключа 14, которым снабжен канал связи 4 этой модели звена 3.А.1.С. Модель маршрутов 1/3/ модели звена 3.А.1.С. устройства 1/2/ модели звена 3.В.4.А. устройства 1/1/ содержит модели звеньев 3.А.1.С.и 3.В.2.А., соединенные каналами связи 4 в соответствии с топологией графа G. Каналы связи 4 этих моделей звеньев 3 снабжены регистраторами 7, выходы 8 которых, через выходы 9 этих моделей звеньев 3 соединены с соответствующими входами 11 определителя 10.
Для обеспечения работы всего устройства 1/1/ от одного источника питания, в моделях звеньев 3, которые снабжены устройствами 1/2/ и 1/3/, введены дополнительные пути 19 (фиг.6) каналов связи 4, обходящие регистраторы 7 и ключи 14.
Поскольку в графе G четыре вершины, то все определители 10 устройства 1/1/ выполнены в виде элементов «И» с четырьмя входами 11, каждый из которых соответствует вхождению определенной вершины, по меньшей мере, в один смоделированный маршрут. Если срабатывает определитель 10, то каждое звено, с модели 3 которого поступил сигнал на вход 11 определителя 10, входит во множество маршрутов, посещающих все вершины графа G. Работа описанного устройства 1/1/ происходит следующим образом. На вхождения каналов связи 4 в модель маршрутов 1/1/ посылают, например, переменный ток, который проходит через все модели звеньев 2, 3. Регистраторы 7 тех моделей звеньев 2, 3, в которых отсутствуют ключи 14 каналов связи 4, срабатывают сразу и из выходов 8 регистраторов 7, через выходы 9 этих моделей звеньев 3, посылают импульсы на соответствующие входы 11 определителей 10. Работа остальных регистраторов 7 происходит только в том случае, если сработал соответствующий определитель 10, с выхода 12 которого, посылают импульс на вход 13 управляющего ключа 14, которым (вместе с регистратором 7) снабжен канал связи 4 соответствующей модели звена 3.
Таким образом, в устройстве 1/1/ только с выхода 8 регистратора 7 модели звена 2.А.1. через ее выход 9 сразу посылают импульс на соответствующий вершине А вход 11 определителя 10, а в остальных моделях звеньев 3 происходит работа моделей маршрутов 1/2/ и 1/3/ аналогичным образом. В результате, в моделях звеньев 3.А.1.С. и 3.В.3.С. устройств 1/1/ и 3.А.1.С. устройства 1/2/ не сработали регистраторы 7, поскольку ключи 14 не пришли в рабочее состояние, в силу того, что не сработали определители 10 устройств 1/2/ и 1/3/, т.к. не на все их входы 11 поступили импульсы от регистраторов 7 моделей звеньев 3.
В модели звена 3.Е.2.С. устройства 1/1/ все составляющие приводят в рабочее состояние, в частности, определитель 10 устройства 1/2/, и с выхода 8 регистратора 7 через выход 9 этой модели звена 3.Е.2.С. посылают импульсы на соответствующие вершинам Е и С входы 11 определителя 10 устройства 1/1/.
В модели звена 3.В.4.А. в его устройстве 1/2/ не сработали регистраторы 7 моделей звеньев 3.В.3.С.и 3.А.1.С., причем в последнем, по причине того, что его ключ 14 не мог быть приведен в рабочее состояние из-за отсутствия срабатывания определителя 10 его устройства 1/3/, поскольку на его входы 11 поступило только три импульса из четырех необходимых. В остальных моделях звеньев 2.А.1., 3.Е.2.С., 2.С.3. и 3.В.4.А. регистраторы 7 приведены в рабочее состояние и из их выходов 8, через выходы 9 этих моделей звеньев 2, 3, посылают импульсы на соответствующие входы 11 определителя 10, чем приводят его в рабочее состояние и из его выхода 12 посылают сигнал на управляющий вход 13 ключа 14 модели звена 3.В.4.А. устройства 1/1/, чем приводят ключ 14 в рабочее состояние и в результате срабатывания регистратора 7 с его выхода 8, через выход 9 этой модели звена 3.В.4.А., посылают сигнал на соответствующие вершинам А и В входы 11 определителя 10 устройства 1/1/, чем приводят его в рабочее состояние.
Возникший в итоге импульс на выходе 12 определителя 10 устройства 1/1/ свидетельствует о том, что граф G гамильтонов и его единственный гамильтонов маршрут: А-Е-С-В-А, поскольку регистраторы 7 были приведены в рабочее состояние только в моделях звеньев этого маршрута - 2.А.1., 3.Е.2.С. и 3.В.4.А. устройства 1/1/. Совокупность импульсов на выходах 9 указанных моделей звеньев представляет собой сформированный и сохраненный (в виде записи) сигнал.
На графике (фиг.7) показаны затраты при реализации известных технических решений /2 в степени n/ и затраты при реализации заявляемых технических решений /n в седьмой степени/. Этим обусловлен технико-экономический эффект достигаемый заявляемым устройством, который выражается в уменьшении количества конструктивных элементов в специализированных устройствах, количества операций в универсальных вычислительных устройствах и тому подобного.
Возможность многократного использования полезной модели в любых переборных задачах, например, при решении задач коммивояжера, о сумме подмножеств, о гамильтоновости и других, обеспечивает промышленную применимость полезной модели. Она может быть реализована самым различным образом с использованием любых форм исполнения моделей звеньев и всего устройства, любых форм каналов связи - электрических, оптических, звуковых и т.д. Например, в качестве моделей звеньев могут быть использованы приемопередающие и обрабатывающие радиосигналы устройства, различные топологии интегральных микросхем как отдельных моделей звеньев, так и всего устройства.