Розглянуто найвідоміші алгоритми пошуку найбільшого паросполучення на дводольному графові, які або виконують пошук найбільшого паросполучення на незваженому дводольному графові, або вибирають із множини найбільших паросполучень одне, яке має найбільшу суму вагів ребер. Ці алгоритми активно вживаються під час розв'язання різних оптимізаційних задач, але на практиці є також потреба в інших постановках і алгоритмах пошуку найбільшого паросполучення на дводольних графах. Мета роботи - розглянути нові постановки завдання щодо знаходження найбільшого паросполучення на зваженому дводольному графові, алгоритми розв'язання цієї задачі, а також використання цих алгоритмів за розпізнавання папілярних зображень. У роботі використано модифіковані версії пошуку найбільшого паросполучення M на дводольному графові на основі пошуку та аугментації M - збільшуючих шляхів на цьому графові. Розглянуто нову постановку пошуку найбільшого паросполучення на зваженому дводольному графові, ваги ребер якого набувають два значення (наприклад, 0 і 1): знайти всі паросполучення, що мають найбільшу кількість ребер з вагою 1, і вибрати серед них таке паросполучення, що має найбільшу кількість ребер. Запропоновано два алгоритми пошуку найбільшого паросполучення у цій постановці зі складністю <$EO(m sqrt n )>. Розглянуто приклади вживання цих алгоритмів для усунення розривів ліній та пошуку відповідності особливих точок на порівнюваних відбитках пальців під час розв'язання задачі розпізнавання папілярних зображень. Висновки: запропоновано нові алгоритми пошуку найбільшого паросполучення на зваженому дводольному графові. Використання запропонованих алгоритмів призводить до пришвидчення та зростання надійності розпізнавання зображень відбитків пальців.

  Повний текст PDF - 364.665 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"