Реализация алгоритма устойчивых паросочетаний со списками и массивами

Мы рассмотрели общий подход к выражению границ времени выполнения алго- ритмов. Чтобы проанализировать асимптотическое время выполнения алгоритмов, выраженных на высоком уровне (например, алгоритма поиска устойчивых паросо- четаний Гейла-Шепли в главе 1), следует не писать код, компилировать и выпол- нять его, а думать над представлением и способом обработки данных в алгоритме, чтобы получить оценку количества выполняемых вычислительных действий.

Вероятно, у вас уже имеется некоторый опыт реализации базовых алгоритмов со структурами данных. В этой книге структуры данных будут рассматриваться в контексте реализации конкретных алгоритмов, поэтому в ней вы встретите разные структуры данных в зависимости от потребностей разрабатываемого алго- ритма. Для начала мы рассмотрим реализацию алгоритма устойчивых паросочета- ний Гейла-Шепли; ранее было показано, что алгоритм завершается максимум за n2 итераций, а наша реализация обеспечивает соответствующее худшее время вы- полнения O(n2) с подсчетом фактических вычислительных шагов вместо простого количества итераций. Чтобы получить такую границу для алгоритма устойчивых паросочетаний, достаточно использовать две простейшие структуры данных: списки и массивы. Таким образом, наша реализация также предоставит хорошую возможность познакомиться с использованием этих базовых структур данных.

В задаче устойчивых паросочетаний у каждого мужчины и каждой женщины должны существовать оценки всех членов противоположного пола. Самый первый вопрос, который необходимо обсудить, — как будут представляться эти оценки? Кроме того, алгоритм ведет учет паросочетаний, поэтому на каждом шаге он дол- жен знать, какие мужчины и женщины свободны и кто с кем находится в паре. Для реализации алгоритма необходимо решить, какие структуры данных будут использоваться для всех этих задач.

Следует учесть, что структура данных выбирается проектировщиком алго- ритма; для каждого алгоритма мы будем выбирать структуры данных, обеспечи-

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация алгоритма устойчивых паросочетаний со списками и массивами:

  1. Номер один в списке неправильных действий
  2. 18.5. Права и обязанности держателя (обладателя) по работе с массивами персональных данных
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ УДАЧИ
  5. 4.2. Хорошие и устойчивые вопросы
  6. Уровень устойчивого, продолжительного счастья
  7. АЛГОРИТМ
  8. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  9. Методика повышения психологической устойчивости.
  10. Методика повышения психологической устойчивости.
  11. Специальную значимость имеетморально-психологическая устойчивость
  12. Алгоритм исцеления:
  13. Статья 220. Сокрытие устойчивой финансовой несостоятельности
  14. Алгоритм избавления от боли
  15. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  16. 2. Специфика и алгоритмы работы с источниками.
  17. Алгоритм обработки результатов.
  18. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  19. Психология личности в любом возрасте при всей ее устойчивости непрерывно меняется (принцип развития).
  20. Практическая реализация.