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

Давайте рассмотрим несколько определений и гипотез предыдущих недель. Канал удаления – это функция, которая принимает дерево и вероятность удаления узла q и возвращает модифицированное дерево с удаленными некоторыми узлами. Канал TED сужает границу между дочерними и родительскими узлами удаленного узла, сохраняя порядок узлов слева направо. Левый канал распространения рекурсивно удаляет узел, заменяя этот узел его крайним левым дочерним элементом и продолжая этот процесс до листа.

Гипотеза, которую я предложил несколько недель назад, состоит в том, что, учитывая глубину дерева как d, примерно O((1-q)^-d) следов достаточно для восстановления произвольных деревьев. Это утверждение, вероятно, не соответствует действительности. Недавно я обнаружил, что существуют два простых дерева, которые можно различить, только если просмотреть оба дерева полностью. Первый — это просто связанный список с N узлами. Второй — это связанный список с N-2 узлами и «разделенный конец», содержащий оставшиеся 2 узла. Эти структуры показаны ниже.

Давайте рассмотрим крайний случай, когда деревья помечены всеми нулями. Обратите внимание, что в канале удаления с левым распространением, если хотя бы один узел удаляется из любого дерева, мы не можем сказать, какому дереву принадлежит трасса. Поскольку маркировка не дает нам информации о том, к какому дереву принадлежит трасса, мы должны видеть все дерево, чтобы определить, является ли он связным списком или раздвоенным. Это означает, что в общем случае мы не можем ожидать, что алгоритм реконструирует дерево с количеством следов менее O((1-q)^-N), что не лучше, чем ожидание полного дерева, которое будет возвращено из канала удаления.

Мы можем расширить этот результат двумя способами. Первый заключается в определении класса алгоритмов удаления, которые я называю рекурсивными каналами распространения удаления. Эти алгоритмы удаления обобщают левое распространение, позволяя выбирать произвольный дочерний элемент в рекурсивной процедуре, а не только левый дочерний элемент. Структура связанного списка и дерева с раздвоенными концами достаточно проста, поэтому любой из этих рекурсивных алгоритмов, удаляющий только один узел, приводит к тому же связанному списку (N-1) длины. Таким образом, с любым из этих каналов рекурсивного удаления вы не можете построить алгоритм реконструкции трасс, который может гарантировать использование трасс менее чем O((1-q)^-N)) для восстановления произвольных деревьев.

Другой способ обобщить этот результат — взглянуть на класс деревьев, который я называю цветами. Цветок (n, b) состоит из связанного списка, такого как «стебель», с n-b узлами, и «головки цветка», состоящей из b узлов, соединенных с последним узлом связанного стебля. Легко показать, что при распространении слева (да и при любом канале рекурсивного удаления) невозможно различить (n,b) цветок и (n,c) цветок, когда в любом из цветов удалено max(b,c) узлов. . Это связано с тем, что удаление «головы» цветка приводит к связанному списку, неотличимому от других цветов.

И это почти все. У меня есть 2 новых результата и несколько новых направлений для изучения. Я надеюсь углубиться в алгоритмы реконструкции TED, но на первый взгляд это кажется сложным из-за того, как TED искажает древовидную структуру. Возможно, пришло время изучить другие каналы удаления.

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

Наконец, есть возможность исследовать метки среднего дерева. Здесь мы не можем позволить себе роскошь предположить, что дерево имеет метку, состоящую только из 0, и вместо этого предположим, что метка выбирается случайным образом из всех возможных n-битных двоичных строк. Я чувствую, что мой анализ все еще может быть выполнен, если метки на деревьях эквивалентны, но я не нашел доказательства этого, кроме подхода грубой силы к 3 конечным узлам обоих деревьев. Предполагая, что этот анализ верен, мы отложили бы идею о том, что рекурсивные каналы удаления имеют какое-либо применение в общей проблеме реконструкции дерева.