МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ НА ГРАФЕ ГАМИЛЬТОНОВА ЦИКЛА Советский патент 1971 года по МПК G06G7/48 

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

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

До сих пор не разработаны достаточно эффективные методы решения этой важной задачи.

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

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

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

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

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

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

1 - распределитель импульсов; 2 - .м;причный индикатор экстремальных напряжений; 3 - блок управляемых ключей; 4 -- сумматор напряжений; 5 - блок формирования управляюш,его импульса; 6 - блок элементов управления и индикации; 7 - модель для обнаружения подциклов.

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