43
Целият алгоритъм FastMap може да се реализира чрез следния рекурсивен алгоритъм:
Алгоритъм
FastMap(k, D(), O) Вход
Множество O от
N обекта
Функция за разстояние D()
Желания брой на размерности
k на целевото пространство Начало
Глобални променливи:
X[] –
N x k масив – в края на работата на алгоритъма i-ят ред на масива ще съдържа k-мерния образ на i-я обекта
PA[] - 2 x k масив – съхранява идентификатори на опорните обекти – по една двойка за всяко рекурсивно извикване. int j = 0 – указател на текущата колонка в X[]
1) АКО k ≤ 0 Край
ИНАЧЕ
j = j + 1 2) /* Избор на опорни обекти */
Нека O
a и O
b са резултат от работата на алгоритъма избери_обекти(O, D())
по избор на опорни обекти, описан по-горе;
3) /* Записване на идентификатори на опорните обекти */
PA[1, j] = a;
PA[2, j] = b;
4) АКО D(O
a
,O
b
) = 0
X[i, j] = 0 за
всички i и Край /* всички разстояния между обекти са 0 */
5) /* проектиране на обекти върху линията (O
a
,O
b
) */
За всеки обект Oi
Изчисли x i съгласно формула (1) и обнови глобалния масив:
X[i, j] = x i
6) /* проектиране на
обекти върху хипер-равнина, перпендикулярна на линията
(O
a
,O
b
); функцията за разстояние D’() между двете проекции се задава с формула (2)
Рекурсивно
извикване
: FastMap(k – 1, D’(), O)Край
При всяко рекурсивно извикване алгоритъмът определя координатите на
N обекта върху новата ос. Така i-тият обект се изобразява в точката Pi = (X[i, 1], X[i, 2], …, X[i, k]).
