Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования, искусственный интеллект, биоинформатика
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2017.
Пример заполнения выходных данных:
Моклев В.В., Ульянцев В.И., Шалыто А.А. Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину // Сборник тезисов докладов конгресса молодых ученых. Электронное издание [Электронный ресурс]. - Режим доступа: ссылка на страницу с тезисом, своб.
Разработка методов нарушения симметрий в графовых задачах на основе обхода в ширину
УДК: 004.832.25
Аннотация:
Одной из техник решения NP-полных задач поиска графов является сведение к задаче выполнимости булевой формулы (Boolean satisfiability problem, SAT). Однако такое сведение порождает симметрии, которые существенно замедляют поиск решения. Для устранения подобных симметрий предложены различные методы излома симметрии. В работе представляется подход к излому симметрий в задачах поиска графов, основывающийся на работе по излому симметрий в конечных автоматах. Этот подход основывается на обходе в ширину (Breadth-first search, BFS). В работе изначальный подход существенно совершенствуется, дополняясь специфичными для графов приемами излома симметрий. Корректность полученного подхода формально доказывается.