Анализ алгоритма

Удалось ли нам достичь своей цели — создать кластеры, разделенные максимально возможным интервалом? Следующее утверждение доказывает этот факт.

(4.26) Компоненты C1, C2, ..., Ck, образованные удалением k - 1 ребер минималь- ного остовного дерева T с максимальной стоимостью, образуют k-кластеризацию с максимальным интервалом.

Доказательство. Пусть C — кластеризация C1, C2, ..., Ck. Интервал C в точности равен длине d * (k - 1)-го ребра с максимальной стоимостью в минимальном остов- ном дереве; это длина ребра, которое алгоритм Крускала добавил бы на следующем шаге (в тот момент, когда мы его остановили).

Возьмем другую k-кластеризацию C', которая разбивает U на непустые множе- ства C'1, C'2, ..., C'k. Требуется показать, что интервал C' не превышает d *.

Так как две кластеризации C и C' не совпадают, из этого следует, что один из кластеров Cr не является подмножеством ни одного из k множеств C's в C'. Следова- тельно, должны существовать точкир,р. C, принадлежащие разным кластерам в C', — допустим, р C's и Рj C't ф C's.

Теперь взгляните на рис. 4.15. Так как р. и р. принадлежат одной компоненте C, алгоритм Крускала должен был добавить все ребрар-р. пути P перед его останов- кой. В частности, это означает, что длина каждого ребра P не превышает d * Мы знаем, чтор.

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

Еще по теме Анализ алгоритма:

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