§ 2. Алгоритм λ-KRAB-2

Сейчас уже имеются эффективные алгоритмы построения -КНП. Однако если количество исходных точек  превышает несколько тысяч, этап построения -КНП становится затруднительным.

Дополнительные сложности возникают и в тех случаях, когда требуется получить большое число таксонов . Тогда нужно разорвать не одно, а  граничное ребро. Перебор всех возможных вариантов, количество которых равно числу сочетаний из  по , может потребовать неприемлемо больших машинных ресурсов. Для сокращения объема вычислений в этом случае можно воспользоваться модификацией базового алгоритма -KRAB — алгоритмом -KRAB-2.

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

На этапе выбора граничных ребер объем вычислений можно сократить, если из рассмотрения исключить короткие ребра -КНП, оставив для оценки  лишь  самых длинных ребер (например, ). Среди них практически всегда находятся ребра, разрыв которых обеспечивает получение наилучшей таксономии.