Штучний інтелект

Анотація: Запропоновано новий метод пошуку найкоротших шляхів у дворівневому графі з поміченими вершинами і дугами. Він дозволяє знаходити один або декілька оптимальних шляхів між заданими вершинами, помітки та якість цих шляхів. Метод орієнтований на дворівневий граф, де кожна вершина графа першого рівня є графом другого рівня. Метод заснований на локальній редукції графа, тобто на послідовному виключені його вершин та дуг.

Ключові слова: метод побудови найкоротших шляхів, дворівневий граф, локальна редукція графа.

Посилання:

1. Робертс Ф.С. Дискретные математические модели с приложениями к социальным биологическим иэкологическим задачам / Ф.С. Робертс ; [ред. А.И. Тейман; пер. с англ. А.М. Раппопорта, С.И. Травкина]. –М. : Наука, 1986. – 496 с.
2. Droste M. Handbook of Weighted Automata / M. Droste, W. Kurich, H. Vogler. – Berlin, Heidelberg : SpringerVerlag,2009 – 610 p.
3. Кристофидес Н. Теория графов: алгоритмический подход / Кристофидес Н. – М. : Мир, 1978. – 430 с.
4. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М. : Мир,1979. – 536 с.
5. Батищев Д.И. Многоуровневая декомпозиция гиперграфовых структур / Д.И. Батищев, Н.В. Старостин,А.В. Филимонов // Прилож. к журналу «Информационные технологии». – 2008. – № 5(141). – М. : Новыетехнологии. – 32 с.
6. Ногина Н.В. Синтез регулярного выражения языка, порожденного помеченным графом, методом еголокальной редукции / Н.В. Ногина, И.С. Грунский // Искусственный интеллект. – 2012. – №3. – С. 348-353.
7. Ногина Н.В. Построение кратчайшего пути в помеченном графе при помощи локальной редукции графа /Н.В. Ногина, А.В. Билык // Сучасна інформаційна Україна: інформатика, економіка, філософія : матеріалидоповідей конференції, 26 квітня 2012 року. – Донецьк, 2012. – 316 с. – С. 76-79.
8. Білик Г.В. Метод побудови найкоротших шляхів у дворівневому графі / Г.В. Білик, І.С. Грунський,Н.В. Ногіна // Інформаційні управляючі системи та комп’ютерний моніторинг (ІУС КМ – 2013) :IV Всеукраїнська науково-технічна конференція студентів, аспірантів та молодих вчених, 24 – 25 квітня2013 р., м. Донецьк : зб. доп. : в 2 тт. / Донец. націонал. техн. ун-т ; редкол. В.А. Світлична. – Донецьк :ДонНТУ, 2013. – Т. 1. – 765 с. – С. 474–478.
9. Білик Г.В. Пошук найкоротших шляхів в графі дворівневої структури / Г.В. Білик, І.С. Грунський,Н.В. Ногіна // Інтелектуальні системи в промисловості і освіті : тези доповідей Четвертої міжнародноїнауково-практичної конференції. – Суми : Вид-во СумДУ, 2013. – (у друці).