Нахождение расстояния между двумя полиномами (представленными в виде деревьев)

20

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


Рассмотрим два полинома, которые представлены деревьями их выражений. Например, и показаны ниже:x32x+1x2+4

Правила:

  1. Каждый узел является либо именем переменной ( ), числом , либо операцией (+, -, ×).x,y,z,
  2. Упорядоченный обход дерева должен привести к правильному многочлену.
  3. Операционные узлы имеют степень 2. Другие узлы имеют степень 0. Все узлы имеют выходную степень 1 (кроме корня, у которого выходная степень равна 0).

На узле N дерева определите основную операцию следующим образом:

  1. Базовая операция может изменить метку узла. Например, можно изменить на 3 или + можно изменить на .x×
  2. Базовая операция может построить дерево выражений поверх N (см. Пример ниже).

Стоимость базовой операции типа 1 равна 1. Стоимость типа 2 равна количеству операций {+, -, ×} во вновь построенном дереве выражений.

Пример для типа 2: стоимость следующей базовой операции равна 2, поскольку дерево выражений, построенное поверх узла N, использует две операции (- и ×).

Пусть T1 и T2 - два дерева выражений, представляющих многочлены. Определите расстояние T1 и T2 следующим образом: минимальная стоимость основных операций для преобразования T1 в T2. Обратите внимание, что нам не требуется, чтобы преобразованное дерево имело ту же структуру, что и T2. Мы просто хотим, чтобы он вычислял тот же полином, что и T2. (См. Комментарии для примера.)

Проблема: учитывая T1 и T2, представьте алгоритм, который вычисляет их расстояние.

Пример 1. Пусть T1 и T2 - два дерева, показанные в начале этого поста. Чтобы преобразовать правое дерево в левое дерево, можно построить дерево стоимостью 3 сверху × и изменить 4 на 1 (общая стоимость равна 4).

Пример 2: Пусть T1 = будет представлено следующим деревом. Чтобы преобразовать T1 в T2 = , достаточно добавить 1 к каждому из узлов , чтобы получить = T2. Это можно сделать, добавив дерево выражений cost-1 поверх каждого узла . Этот пример показывает, что поэтапное преобразование (которое я назвал жадным подходом в начале этого поста) не является оптимальным подходом. То есть, если кто-то хочет создать термины в T2, которых нет в T1 (то есть , , и 1), стоимость будет намного выше.x4x4+4x3+6x2+4x+1x(x+1)4x4 х 3 6 х 2 4 х4x36x24x

М.С. Дусти
источник
2
Если операция «удалить» не разрешена, то расстояние не является расстоянием. Например: дерево T1 = (x * x) +4 не может быть преобразовано в T2 = x, но T2 может быть преобразовано в T1, добавив (* x) и затем (+4) поверх x. Это нормально ? Или вы должны определить расстояние как минимальные операции, необходимые для преобразования T1 в T2 или T2 в T1.
Марцио Де Биаси
4
Стоимость равна 0 тогда и только тогда, когда две приведенные (без деления) арифметические формулы представляют один и тот же многочлен. Если я правильно помню, это типичная проблема в coRP (при случайном назначении), которая, как известно, отсутствует в P.
Tsuyoshi Ito
4
@ Tsuyoshi: О, я вижу. Вы указываете на проблему проверки полиномиальной идентичности . (Хорошие ссылки: [1 ] и [2 ]). Я должен подумать об этом. Между тем, любое предложение приветствуется.
MS Dousti
4
Да это оно. Кажется, что в типичной версии задачи проверки полиномиальной идентичности два входных полинома задаются в виде схем, а не формул. Поэтому моя формулировка о том, что версия формулы является «типичной», была, вероятно, неточной. В любом случае, даже введение версии формулы в P кажется открытой проблемой.
Цуёси Ито
2
@Vor: В текущей формулировке вход T1 действительно является деревом, а вход T2 является полиномом, который просто дается как дерево, в следующем смысле. Изменение T1 на другое дерево, которое представляет один и тот же многочлен, может изменить ответ в целом, тогда как изменение T2 аналогичным образом не меняет.
Цуёси Ито

Ответы:

10

Расстояние редактирования дерева - это обобщение расстояния редактирования строки. Расстояние между двумя деревьями - это минимальное количество вставок узлов \ удалений \ и релабелей, необходимых для превращения одного дерева в другое. (когда мы удаляем узел v, потомки v становятся потомками parent (v)). Проблема NP-трудна, когда деревья неупорядочены, но когда они упорядочены (т. Е. Между братьями и сестрами есть порядок слева направо), проблема разрешима за O (n ^ 3) времени (как в статье, где Садек упоминается). Хороший опрос, который описывает это: http://portal.acm.org/citation.cfm?id=1085283

Авив
источник
1
Спасибо, Авив. Будет здорово, если вы объедините свои ответы (я думаю, у вас есть проблемы с использованием вашей предыдущей учетной записи). Вы можете воспользоваться советами в этом посте (Специально по этой ссылке ).
MS Dousti
Как этот подход будет покрывать разные деревья с помощью эквивалентных полиномов
Нарек Божикян