Моделирующее устройство для определения на графе гамильтонова цикла

Союз Советских Социалистических РеспуоликЗависимое от авт. свидетельстваЗаявлено 04.Н.1969 ( 1353277/18-24)с присоединением заявки-ПриоритетОпубликовано 25 Н.1971. Бюллетень17Дата опубликования описания 07.Н 11.1971 МПК 6 06 д 7/48 Комитет по делам иаобретдиий и открытий при Совете 1 т 1 инистрав СССРУДК 681.332,4(088.8) Авторыизобретения А. Г. Тимошенко и Э. 3. Трайнин Институт кибернетики АН Украинской ССРЗаявитель МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ НА ГРАФЕ ГАМИЛЬТОНОВА ЦИКЛАНастоящее изобретение относится к области электронного моделирования задач математического программирования и может быть использовано при построении модели для решения задач о коммивояжере, о назначении, о наладке станка и т. д.Задача заключается в построении на полном графе, заданном матрицей расстояний между вершинами, гамильтонова цикла, сумма звеньев которого - минимальная.До сих пор не разработаны достаточно эффективные методы решения этой важной задачи,Одним из известных решений, дающих хороший результат, является последовательный выбор среди множества ребер графа такого, который на данном шаге является оптимальным (по определенному критерию) и присоединение которого к уже выбранным ребрам не образует подцикла, т. е. меньше гамильтонова цикла,Такое устройство позволяет реализовать основные этапы поиска элемента, включаемого в решение, с автоматическим преобразованием матрицы расстояний, а также позволяет на каждом шаге определять величину напряжения, соответствующего нижней границе длин путей без ручных вычислений.Однако оно имеет следующие недостатки: отсутствует контроль возникновения подциклов; имеются специальные устройства дляприведения матрицы (в количестве 2 и), усложняющие модель; необходимо определятьдиоды, напряжение на которых равно нулю,5 Цель изобретения - повышение быстродействия предлагаемого устройства,Положительный эффект достигается за счетавтоматического непрерывного контроля возникновения подциклов с помощью электричс 10 ской цепи матричной структуры и за счст изменения схемы матричного индикатора экстремальных напряжений.На чертеже изображена блок-схема усгройства, где обозначены;15 1 - распределитель импульсов; 2 - мат.ричпый индикатор экстремальных напряжений; 3 - блок управляемых ключей; 4 - сумматор напряжений; 6 - блок формированияуправляющего импульса; 6 - блок элементов20 управления и индикации; 7 - модель для обнаружения подциклов. Матричный индикатор экстремальных напряжений представляет собой электричсскуго 25 цепь матричной структуры с ветвями, содержащими последовательное соединение регулируемого источника э.д,с., ключа на два положения и диода.Блок 6 элементов управления и индикации 30 состоит из устройств, каждое из которых со 30460550 55 60 65 дсржит трехустойчивыи элемент пам 51 ти и схеМь. СовпаДЕНИЯ.Модель 7 для обнаружения подциклов представляет собой электрическую цепь матричнои структуры, в которой между горизонтальыми и вертикальными шинами вклочены управляемые ключи, а диагональные элементы выполнены в виде последовательно соединенных источников тока и первичных обмоток трансформаторов. ри замыкании группы ключей, ооразующих замкнутый контур, через первичные обмотки соответствующих транс 1 рорм 1 горов потечет ток. Во вторичных обмотках этих трансформаторов наведутся импульсы напряжения, поступающие на вход блока фор.51 ироваР 1 ия управляюще 1 о импульса.ринцип работы устроиства заключается в автоматическом преоОразовании исходной матрицы расстоянии к виду, когда в каждой строке ее и в каждом столоце имеется по райней мере один элемент, равный нулю, путем вычитания минимальных элеьентов из строк исходной матрицы и затем из столбцов матрицы, приведенной по строкам; в получении суммы констант приведения (вычитаемых элементов преобразованной матрицы), равной нижней границе всех решении; в поОчередном испытании каждого элемента матрицы одовремеппо на оптимальность и цикличность 51 утем временного Исключения этого э;Смснта из матрицы.Критерием оптимальности элемента является максимальное увеличение нижней границы при исклкгчении опрашиваемого элемента.Цикличность элемента (возникновение подцикла при включении этого элемента в решепис) контролируется моделью для обнаружен 51 ПОДЦР 1 КЛОВ.Преобразование исходной матрицы расстояний к требуемому виду осуществляется с помошью матричного индикатора 2 экстремальнь 1 х напряжений. После установки (с помощью регулируемых источников э.д.с,) напряжений, моделируОщих расстояния между узлами графа, это устройство (2) автоматически моделирует преобразованную матрицу.При этом источники напряжения и диоды образуют индикаторы минимальных напряжений по строкам, На горизонтальных шинах установятся напряжения, соответствующиеэлементам каждоиходной матрицы, На диодах установятся потещиалы, равные разности между минимальным элементом и остальными элементами строки. Полученные потенциалы с помощью диодов, включеных на соответствующие вертикальные шины, сравниваются между собой. В результате па вертикальных шинах установятся (с отрицательным знаком) напряжения, соответствующие минимальным элеьентам столбцов привсдспной по строкам матрицНапряжения шин матричного индикатора экстремальных напряжений поступают на входы сумматора 4. На выходе сумматора уста 5 10 15 20 25 30 35 40 45 новится напряжение, равное сумме потенциалов строк, сложенной с инвертированной суммой потенциалов столбцов, что соответствует нижней границе всех решений. На каждом такте генератора импульсов происходит отключение (на время одного такта) какои-либо ветви матричного индикатора экстремальных напряжений, Если Отключаемая ветвь экстре- вальна, опа соответствует нулевому элементу преобразовашой матрицы расстояний, Это значит, что либо э.д.с, этой ветви является минимальной среди всех э,д.с. Соответствующей горизонтальной шины блока индикатора 2, либо потенциал анода диода этой ветви является минимальным среди всех потенциалов соответствующей вертикальной шины индикатора. При отключении такой ветви экстремальной становится друггая ветвь, в которой либо ее э.д.с либо падение напряжения на диоде в общем случае больше соответствующих величин отключаемой ветви. Поэтому возрастет напряжение на соответствующих шинах блока индикатора 2 и на выходе сумматора 4. Таким образом, отключение некоторых (экстремальных) ветвей блока индикатора вызывает увеличение напряжения на выходе сумматора, Отключение первой такой ветви сопровождается возрастанием напряжения на выходе устройства аналоговой памяти и возникновением импульса в блоке 5. Возросшее напряжение фиксируется блоком 5. Теперь только приращение напряжения на выходе сумматора 4, большее, чем все предыдущие, вызовет изменение напряжения в блоке 5.Таким образом, последний импульс на выходе блока 5 появится при испытании оптимального (на данном цикле опроса) элемента, отключение ветви которого сопровождается максимальным увеличением напряжения на выходе сумматора 4. Зтот элемент включается в решение, если при этом он в совокупности с другими элементами (включенными в решение на предыдущих циклах опроса) не образует подцикла. Контроль возникновения иодциклов осуществляется с помощью моде. ли 7. Предмет изобретения Моделирующее устройство для определенияа графе гамильтонова цикла, содержащее матричный индикатор экстремальных напряжений, подключенный через блок управляемых ключей к сумматору напряжений, и распределитель импульсов, Отличающееся тем, что, с целью повышения быстродействия устройства, в нем дополнительно установлены блок формирования управляющего импульса, блок управления и индикации и модель для обнаружения подциклов, причем выходы распределителя импульсов подключены к матричному индикатору и модели для обнаружения подциклов, выход которой подключен к5блоку управления и индикации, два других входа которого подключены к сумматору напряжений через блок формирования управля. 304605 ющего импульса и к распределителю импульсов, а выход - к матричному индикатору имодели для обнаружения подциклов.Составитель В. К. Оверовредактор Б. С. Нанкина Техред А. А. Камышникова Корректор Л. А. ЦарьковаЗаказ 1905/13 Изд. М 800 Тираж 473 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5 Типография, пр. Сапунова, 2