RUS  ENG
Полная версия
ЖУРНАЛЫ // Автоматика и телемеханика // Архив

Автомат. и телемех., 1982, выпуск 12, страницы 85–96 (Mi at5676)

Развивающиеся системы

Экономный алгоритм построения кратчайшего обхода одноцветного связного чертежа

С. А. Вичес

Москва

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

УДК: 681.327.21/22-003.6


Поступила в редакцию: 24.02.1982


 Англоязычная версия: Automation and Remote Control, 1982, 43:12, 1569–1579

Реферативные базы данных:


© МИАН, 2024