Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования и искусственный интеллект
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2015.
Исследование алгоритмов поиска максимального паросочетания в двудольном графе
УДК: 004
Аннотация:
Сегодня, в мире информационных технологий, обновление информации происходит с очень большой скоростью, поэтому необходимо всегда понимать актуальность изучения и применения знаний, которые добываются в процессе исследования. Изучение теории графов является актуальной темой, так как имеет большой спектр применения: в химии, для описания структур и путей сложных реакций, в информатике, граф-схема алгоритма, в транспортных системах, в логистике, поиск кратчайших путей и многое другое. Задача поиска максимального паросочетания в двудольном графе, также известная как задача о назначениях, это задача о наилучшем распределении некоторого числа работ между некоторым числом исполнителей. Существует несколько алгоритмов решения для данной задачи. Наиболее популярными являются - «Венгерский алгоритм» и «Алгоритм Куна».