Divog wrote:
> родство двух животных. Вроде в каком колене у них там где общий предок
> или потомок одного где-то родственник предка другого и т.п.
> Делать это с помощью рекурсивного просмотра всех возможных путей, очень
> накладно.

Интересует проверить родство (найти общего предка) или узнать точный
путь? Это разные задачи.

Если родство - можно гнать волну вверх по дереву. Точнее две волны, по
одной из каждого узла. Для этого узлы, составляющие фронт волны
объединяется в список. Кроме того, к каждому узлу добавляется цвет
(белый=не видели, красный=видели из узла a, синий=видели из узла b). На
каждом шаге фронт волны распространяется вверх к предкам. Для этого
проверяется цвет вершины предка - белая попадает в новый фронт и
перекрашивается, вершина соответствующая своему цвету - игнорируется,
вершина чужого цвета - ближайший общий предок.

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

>
> В связи с чем прошу пнуть в верном направлении, про какие деревья, их
> представления да алгоритмы почитать, чтобы понять, как пооптимальнее
> решить эта задачу.

Оптимальность зависит от условий. Как вариант - найти транзитивное
замыкание отношения предок для каждого из узлов и взять их пересечение.
Posted via ActualForum NNTP Server 1.4

Divog wrote:

>> Оптимальность зависит от условий. Как вариант - найти транзитивное
>> замыкание отношения предок для каждого из узлов и взять их пересечение.
>
> Сейчас так и делаю, однако построение оного, при моей схеме хранения
> данных оч. накладно, да и великоватое оно получается, если там предков
> 20 колен. 2*2^20 пар id-шников.

А как находите путь? Замыкания ведь недостаточно. Просто поиск по
отношению прямой предок до заданного предка?

Пофантазирую еще. Может скрестить транзитивное замыкание отношения
прямой предок и волновой поиск? Отношение предок позволяет относительно
быстро проверить существование общего предка для двух особей, но не
показывает пути. И в вашей задаче это отношение можно строить по мере
роста. Скрещивание будет заключаться в том, что на каждой итерации волна
распространяется только на те узлы, у которых есть общий предок со
второй особью. Таким образом все сторонние ветви отмирают сразу.

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

>
> Думал, может что пооптимальнее есть. Вы мне дайте ключевых слов, я в
> инете найду доки, почитаю :)

Не, с ключевыми словами - сложно. Очевидно, что задача из области
дискретной математики и теория графов, но это слишком общо. Приведенный
волновой алгоритм применяется в области трассировки печатных плат.
Можно, конечно еще покопаться в ней, возможно что-нибудь найдете:
<http://algolist.manual.ru/maths/graphs/shortpath/smartmove.php>

Опять-же, если бы у вас и в самом деле было дерево, а не ациклический
орграф, можно было бы подумать о множественной модели представления
дерева <http://www.sedinko.ru/algo/doc1.php>. Вот пожалуй и все, что
приходит в голову.
Posted via ActualForum NNTP Server 1.4

apapacy wrote:
> Почему ацикличный?

А как вы себе представляете цикл в данном случае? Как можно быть прямым
или косвенным предком самого себя?
Posted via ActualForum NNTP Server 1.4