Реализация алгоритма устойчивых паросочетаний со списками и массивами
Вероятно, у вас уже имеется некоторый опыт реализации базовых алгоритмов со структурами данных. В этой книге структуры данных будут рассматриваться в контексте реализации конкретных алгоритмов, поэтому в ней вы встретите разные структуры данных в зависимости от потребностей разрабатываемого алго- ритма. Для начала мы рассмотрим реализацию алгоритма устойчивых паросочета- ний Гейла-Шепли; ранее было показано, что алгоритм завершается максимум за n2 итераций, а наша реализация обеспечивает соответствующее худшее время вы- полнения O(n2) с подсчетом фактических вычислительных шагов вместо простого количества итераций.
Чтобы получить такую границу для алгоритма устойчивых паросочетаний, достаточно использовать две простейшие структуры данных: списки и массивы. Таким образом, наша реализация также предоставит хорошую возможность познакомиться с использованием этих базовых структур данных.В задаче устойчивых паросочетаний у каждого мужчины и каждой женщины должны существовать оценки всех членов противоположного пола. Самый первый вопрос, который необходимо обсудить, — как будут представляться эти оценки? Кроме того, алгоритм ведет учет паросочетаний, поэтому на каждом шаге он дол- жен знать, какие мужчины и женщины свободны и кто с кем находится в паре. Для реализации алгоритма необходимо решить, какие структуры данных будут использоваться для всех этих задач.
Следует учесть, что структура данных выбирается проектировщиком алго- ритма; для каждого алгоритма мы будем выбирать структуры данных, обеспечи-
вающие эффективную и простую реализацию. В некоторых случаях это может потребовать предварительной обработки входных данных и их преобразования из заданного входного представления в структуру, лучше подходящую для решаемой задачи.
Еще по теме Реализация алгоритма устойчивых паросочетаний со списками и массивами:
- Номер один в списке неправильных действий
- 18.5. Права и обязанности держателя (обладателя) по работе с массивами персональных данных
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ УДАЧИ
- 4.2. Хорошие и устойчивые вопросы
- Уровень устойчивого, продолжительного счастья
- АЛГОРИТМ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Методика повышения психологической устойчивости.
- Методика повышения психологической устойчивости.
- Специальную значимость имеетморально-психологическая устойчивость
- Алгоритм исцеления:
- Статья 220. Сокрытие устойчивой финансовой несостоятельности
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Психология личности в любом возрасте при всей ее устойчивости непрерывно меняется (принцип развития).
- Практическая реализация.