Обробка бази даних акустичних матеріалів у системі САПР за алгоритмом Хопкрофта-Карпа для зіставлення дводольних графів

Анотація

Розвиток промисловості потребує наявності великого різноманіття промислових приміщень з особливими вимогами до їх акустичних характеристик. Як наслідок, внутрішнє оздоблення промислових приміщень потребує використання акустичних оздоблювальних матеріалів, які в кінцевому підсумку визначають акустику всього виробничого комплексу. Однак, на етапі проектування промислових приміщень, особливо при використанні спеціалізованого програмного забезпечення, виникає ряд труднощів з обґрунтованим вибором для цього акустичних оздоблювальних матеріалів. Враховуючи на те, що існуючі на тепер програми дозволяють лише приблизно розрахувати акустику приміщень і жодна з них не дає відповідь на питання, чи задовольняє отримана модель приміщення вимогам законодавства і замовника існує потреба в розробці нового програмного забезпечення, яке вирішує цю проблему. При розробці нового програмного забезпечення такого типу завжди виникає проблема зберігання та ефективної обробки довідкової інформації, що організована у вигляді бази даних. В роботі запропоновано моделювання потрібної бази даних у вигляді математичного апарату, якій уявляє собою граф. Вирішенні поставленої задачі проведено на моделюванні бази даних акустичних матеріалів дводольними графами. Виходячи з цього, обробка інформації такої бази, з метою пошуку потрібної інформації у найменший час, проведена з використанням одного з алгоритмів для зіставлення дводольних графів. У якості алгоритму використано алгоритм Хопкрофта-Карпа. На основі прикладу установлено, що прийнятий алгоритм не завжди дає вірне рішення, оскільки усуває у прийнятій графовій моделі бази даних ребра із загальними кінцевими точками і створює інцендентні ребра. Виходячи з отриманих результатів дослідження запропоновано і реалізовано у системі AUTOCAD на мові AUTOLISP базу даних акустичних матеріалі, що відповідає графовій моделі у вигляді орієнтованого графового дерева, обробка якого алгоритмами обходу графів DFS и BFS дає вірне рішення з найменшими витратами часу.