Н.В. Ногина, А.В. Билык.- Алгоритм поиска экстремального пути в графе с отметками на дугах и вершинах методом локальной редукции.

Аннотация

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

Общая постановка проблемы

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

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

В данной работе предложен алгоритм, позволяющий формировать пометку и стоимость по выбранному критерию экстремального пути посредством поэтапного синтеза регулярного выражения в результате последовательного удаления вершин и дуг помеченного графа. Определяется экстремальный путь и его длина из начальной вершины в одну из финальных, в то время как алгоритм из [1] позволяет находить множество всех путей из начальной вершины во все финальные.

Список использованной литературы

1. Ногина Н.В. Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Искусственный интеллект. – 2012. – №3.

2. Ногина Н.В. Построение кратчайшего пути в помеченном графе при помощи локальной редукции графа / Н.В. Ногина, А.В. Билык // Сучасна інформаційна Україна: інформатика, економіка, філософія: матеріали доповідей конференції, 26 квітня 2012 року. – Донецьк, 2012. – С. 76–79.