1) С чем работаю
Есть множество некоторых объектов — I.
На этом множестве определено отношение эквивалентности и "метрика".

2) Что должно быть
Есть подмножество I` исходного множества I и объект A — элемент I.
Необходимо найти в I` объект наиболее близкий а объекту А, с точностью до введенной "метрики".

3) В чем проблема.
Проблема в метрике. Не даром я писал её в кавычках.
Дело в том, что M(A,B) != M(B,A), М — та самая "метрика", A и B — соответственно элементы I.


Если бы не эта "метрика" я бы смог построить дерево, в котором бы и искал, а пока — действую простым перебором...

Есть ли способ эффективного (по сравнению с перебором) поиска?

Правда, в силу специфики ПО, довольно часто M(A,B) оказывается близкой к M(B,A), но не всегда…

Здравствуйте, Kir., Вы писали:

K>Дело в том, что M(A,B) != M(B,A), М — та самая "метрика", A и B — соответственно элементы I.

Т.е. у тебя фактически две метрики которые можно объединить в одну симметричную метрику:

M(A,B) := F(L(A,B),R(B,A))

Т.е. как бы мощность твоего множества вырастает в два раза.

Или я не понял чего?

Здравствуйте, Kir., Вы писали:

K>1) С чем работаю
K>Есть множество некоторых объектов — I.
K>На этом множестве определено отношение эквивалентности и "метрика".

K>2) Что должно быть
K>Есть подмножество I` исходного множества I и объект A — элемент I.
K>Необходимо найти в I` объект наиболее близкий а объекту А, с точностью до введенной "метрики".

K>3) В чем проблема.
K>Проблема в метрике. Не даром я писал её в кавычках.
K>Дело в том, что M(A,B) != M(B,A), М — та самая "метрика", A и B — соответственно элементы I.


K>Если бы не эта "метрика" я бы смог построить дерево, в котором бы и искал, а пока — действую простым перебором...

K>Есть ли способ эффективного (по сравнению с перебором) поиска?

K>Правда, в силу специфики ПО, довольно часто M(A,B) оказывается близкой к M(B,A), но не всегда…

Сталкивался с аналогичной задачей, занимаясь компрессией видеопотоков. Общего решения не нашел. Пробовал генетические алгоритмы — в моем случаи не помогли.
Немного помогли каскадные подходы и знания о поведении сигнала.


Все зависит от конкретной ситуации.

Здравствуйте, c-smile, Вы писали:

CS>Т.е. у тебя фактически две метрики которые можно объединить в одну симметричную метрику:
CS>M(A,B) := F(L(A,B),R(B,A))
CS>Т.е. как бы мощность твоего множества вырастает в два раза.
CS>Или я не понял чего?


Строго говоря у меня нет ни одной метрики.

У меня есть функция M(A,B) которая показывает степень близости между A и B, котроя достаточно близко подходит к мнению человека по данному вопросу.

Дело в том, что эта функция не удовлетворяет следующим условниям.
1) M(A,B) == M(B,A) (для любых A, B)
2) M(A,B) <= M(A,Z) + M(Z,B) (для любых A, B, Z)



У меня есть возможность воспользоваться другой метрикой (без кавычек), но тогда качество сравнения (а, соответстенно, и поиска) резко упадет. А, т.к. я создаю поисковую систему, это неприемлемо, точно так же неприемлема "потеря" объектов при поиске, которая возникнет, если я плюну на кавычки и воспользуюсь первой "метрикой".

Здравствуйте, Kir., Вы писали:

K>У меня есть функция M(A,B) которая показывает степень близости между A и B, котроя достаточно близко подходит к мнению человека по данному вопросу.

K>Дело в том, что эта функция не удовлетворяет следующим условниям.
K>1) M(A,B) == M(B,A) (для любых A, B)
K>2) M(A,B) <= M(A,Z) + M(Z,B) (для любых A, B, Z)

K>У меня есть возможность воспользоваться другой метрикой (без кавычек), но тогда качество сравнения (а, соответстенно, и поиска) резко упадет. А, т.к. я создаю поисковую систему, это неприемлемо, точно так же неприемлема "потеря" объектов при поиске, которая возникнет, если я плюну на кавычки и воспользуюсь первой "метрикой".

Интересно было бы узнать о физической природе объектов и о самой метрике...

Можно ли выделить в множестве такие подмножества, на которых наблюдалось бы правило треугольника (m(a,b)<=m(a,c)+m(c,b)) ? Можно ли выделить такие подмножества, в которых m(a,b)==m(b,a) ?
Тогда поиск сведётся к перебору этих подмножеств, в каждом из которых поиск будет направленным.

Здравствуйте, Kir., Вы писали:

K>Есть ли способ эффективного (по сравнению с перебором) поиска?

Есть.
Например на этапе инициализации для
каждого элемента хранить ссылку на самый "близкий" к нему.
Тогда поиск будет выполняться за константное время
А вообще можно попробовать и другие техники,
но для этого надо больше знать о метрике.