Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Сборник тезисов

Конференция:VI Всероссийский конгресс молодых ученых

Раздел:Информационные и интеллектуальные системы и технологии

Рубрика:Технологии программирования, искусственный интеллект, биоинформатика

Год:2016

Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Моклев Вячеслав Владимирович, Ульянцев Владимир Игоревич

Шалыто Анатолий Абрамович

УДК:004.832.25

Скачать PDF

Аннотация

Одной из техник решения NP-полных задач поиска графов является сведение к задаче выполнимости булевой формулы (Boolean satisfiability problem, SAT). Однако такое сведение порождает симметрии, которые существенно замедляют поиск решения. Для устранения подобных симметрий предложены различные методы излома симметрии. В работе представляется подход к излому симметрий в задачах поиска графов, основывающийся на работе по излому симметрий в конечных автоматах. Этот подход основывается на обходе в ширину (Breadth-first search, BFS). В работе изначальный подход существенно совершенствуется, дополняясь специфичными для графов приемами излома симметрий. Корректность полученного подхода формально доказывается.

Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Аннотация

Постоянный URL

Материалы конференций

Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину

Аннотация

Постоянный URL

Поделиться

Материалы конференций