Разработка и анализ жадного алгоритма
После разработки жадного алгоритма будет рассмотрен чуть более сложный алгоритм назначения цены для версии с пропускными способностями. Интересно, что алгоритм назначения цены работает намного эффективнее простого жадного алгоритма, даже если пропускная способность c ненамного выше 1.
Greedy-Disjoint-Paths:
Присвоить I = 0
Пока удается найти новые пути
Пусть Pi - кратчайший путь, не пересекающийся по ребрам с ранее выбранными путями и соединяющий пару (s ,t ), которая еще не была соединена
Добавить i в I и выбрать путь Р для соединения s с t.
Конец Пока
Длинный путь ИЗ Si в t\ заблокирует все остальные пути V_______________________ J
Рис. 11.9. В этом случае критично, чтобы жадный алгоритм выбора непересекающихся путей отдавал предпочтение коротким путям перед длинными |
Еще по теме Разработка и анализ жадного алгоритма:
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.