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

Союз Советских

Социалистических

Респуелик

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства №

Заявлено 04.Н!!!.1969 (№ 1353277/18-24) с присоединением заявки №вЂ”

Приоритет

Опубликовано 25 Н.1971. Бюллетень № 17

Дата опубликования описания 07Х11.1971

МПК 6 06д 7/48

Комитет по делам иаобретеиий и открытий при Совете 1т1ииистрав

СССР

УДК 681.332.4(088.8) Авторы изобретения

А. Г. Тимошенко и Э. 3. Трайнин

Институт кибернетики АН Украинской ССР

Заявитель

МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

НА ГРАФЕ ГАМИЛЬТОНОВА ЦИКЛА

Настоящее изобретение относится к области электронного моделирования задач математического программирования и может быть использовано при построении модели для решения задач о коммивояжере, о назначении, о наладке станка и т. д.

Задача заключается в построении на полном графе, заданном матрицей расстояний между вершинами, гамильтонова цикла, сумма звеньев которого — минимальная.

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

Однако оно имеет следующие недостатки: отсутствует контроль возникновения подциклов; имеются специальные устройства;t,.l)1 приведения матрицы (в количестве 2и), усложняющие модель; необходимо определять диоды, напряжение на которых равно нулю.

5 Цель изобретения — повышение быстродействия предлагаемого устройства.

Положительный эффект достигается за счет автоматического непрерывного контроля возникновения подциклов с помощью электри,е10 ской цепи матричной структуры и за счст изменения схемы матричного индикатора экстремальных напряжений.

На чертеже изображена блок-схема усгройства, где обозначены:

15 1 — распределитслo :ùïóëü00â; 2 — матричный индикатор экстремальных напряжений; 8 — блок управляемых ключей; / — - сумматор напряжений; 6 — блок формирования управляющего импульса; 6 — блок элементов

20 управления и индикации; 7 — модель для обнаружения подциклов.

Матричный индикатор экстремальных иапряжений представляет собой электри сскуго

25 цепь матричной структуры с ветвями, содержащими последовательное соединение регулируемого источника э.д.с., ключа на два положения и диода.

Блок 6 элементов управления и индикации

30 состоит из устройств, каждое из которых 0о304605

65 держит трехустойчивыи элемент г(ам((ти и схеМь. СОВllаДЕНИЯ.

Модель 7 для обнаружения подциклов представляет собой электрическую цепь матричнои структуры, в которой между горизонтальными и вертикальными шинами вкл!очены управляемые ключи, а диагональные элеме(ITbl выполнены В виде пос;Iедовательно соединенных источников тока и первичных обмоток трансформаторов. iiðè замыкании группы ключей, ооразующих замкнутый контур, через первичные обмотки соответствующих транс(рормагоров потечет ток. Во вторичных обмотках этих трансформаторов наведутся импульсы напряжения, поступающие на вход блока формирования у правляюще(0 импульса. ! (ринцип работы устроиства заключается в автоматическом преоОразовании исходной матрицы расстоянии к виду, когда в каждой строке ее и в каждом столоце имеется по

«райней мере один элемент, равный нулю, (Iyтем вычитания минимальных элементов из строк исходной матрицы и затем из столбцов матрицы, приведенной по строкам; в получении суммы констант приведения (вычитаемых элементов преобразов IHHoH матрицы), равной нижней границе всех решении; в поочередном испытании каждого элемента матрицы одновременно на оптимальность и цикЛИЧНОСТЬ ПУТЕМ ВРЕМЕННОГО ИСКЛЮЧЕНИЯ ЭТОГО элемента из матрицы.

Критерием оптимальности элемента является максимальное увеличение ни?кней границы при исключении опрашиваемого элемента.

Цикличность элемента (возникновение подцикла при включении этого элемента в решепие) контролируется моделью для обнаружени(1 и!Одциклов.

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

При этом источники напряжения и диоды образуют индикаторы минимальных напряжений по строкам. На горизонтальных шинах установятся напряжения, соответствующие минимальным элементам каждои стрОки исходной матрицы. На диодах установятся поте(щиалы, равные разности между минимальным элементом и остальными элементами строки. Полученные потенциалы с помощью диодов, включенных на соответствующие вертикальные шины, сравниваются между собой.

В результате па вертикальных шинах установятся (с отрицательным знаком) напряжения, соответствующие минимальным элеъ(ентам столбцов приведепной по строкам матриЦЫ.

Напряжения шин матричного индикатора экстремальных напряжений поступают на входы сумматора 4. На выходе сумматора уста5

45 новится напряжение, равное сумме потенциалов строк, сложенной с инвертированной суммой потенциалов столбцов, что соответствует нижней границе всех решений. На каждом такте генератора импульсов происходит отключение (на время одного такта) какои-либо ветви матричного индикатора экстремальных напряжений, Если Отключаемая ветвь экстрев(альна, опа соответствует нулевому элементу преобразова(шой матрицы расстояний. Это значит, что либо э.д.с, этой ветви является минимальной среди всех э.д.с. соответству(oщсй горизонтальной шины блока индикатора 2, либо потенциал анода диода этой ветви является минимальным среди всех потенциалов соответствующей вертикальной шины индикатора. При отключении такой ветви экстремальной становится дручгая ветвь, в которой либо ее э.д.с., либо падение напряжения на диоде в общем случае больше соответствующих величин отключаемой ветви. Поэтому возрастет напряжение на соответствующих шинах блока индикатора 2 и на выходе сумматора 4. Таким образом, отключение некоторых (экстремальных) ветвей блока индикатора вызывает увеличение напряжения на выходе сумматора. Отключение первой такой ветви сопровождается возрастанием напряжения на выходе устройства аналоговой памяти и возникновением импульса в блоке 5. Возросшее напряжение фиксируется блоком 5.

Теперь только приращение напряжения на выходе сумматора 4, большее, чем все предыдущие, вызовет изменение напряжения в блоке 5.

Таким образом, последний импульс на выходе блока 5 появится при испытании оптимального (на данном цикле опроса) элемента, отключение ветви которого сопровождается максимальным увеличением напряжения на выходе сумматора 4. Зтот элемент включается в решение, если при этом он в совокупности с другими элементами (включенными в решение на предыдущих циклах опроса) не образует подцикла. Контроль возникновения подциклов осуществляется с помощью модели 7.

Предмет изобретения

Моделирующее устройсчво для определения на графе гамильтонова цикла, содержащее матричный индикатор экстремальных напря?кений, подключенный через блок управляемых ключей к сумматору напряжений, и распределитель импульсов, отличающееся тем, что, с целью повышения быстродействия устройства, в нем дополнительно установлены блок формирования управляющего импульса, блок управления и индикации и модель для обнаружения подциклов, причем выходы распределителя импульсов подключены к матричному индикатору и модели для обнаружения подциклов, выход которой подключен к

5 блоку управления и индикации, два других входа которого подключены к сумматору напряжений через блок формирования управля304605 ющего импульса и к распределителю импульсов, а выход — к матричному индикатору и модели для обнаружения подциклов.

Составитель В. К. Оверов редактор Б. С. Нанкина Техред А. А. Камышникова Корректор Л. А. Царькова

Заказ 1905/13 Изд. М 800 Тираж 473 Подписное

UHHH1IH Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2