Hardprob/Maximum Common Embedded Sub-Tree — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}} <!-- * {{has-testdata-and-visualization}} --> <!-- * {{has-pyomo-model}} --> <!-- * {{has-npc-reduction}} --> <!-- * {{add-random-fuzzing-tests}} -->) |
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>\vert T'\vert</m> на <em>|T'|</em>) |
||
| Строка 2: | Строка 2: | ||
* Деревья <m>T_1</m> и <m>T_2</m> с метками на вершинах. | * Деревья <m>T_1</m> и <m>T_2</m> с метками на вершинах. | ||
* Найти общее встроенное поддерево, т.е. помеченное дерево <em>T'</em>, которое можно встроить в оба исходных дерева. Встраивание из <em>T'</em> в <em>T</em>, это инъективная функция от вершин <em>T'</em> в вершины <em>T</em>, которая сохраняет метки и отношения предшествования (пропускать предшественников можно). | * Найти общее встроенное поддерево, т.е. помеченное дерево <em>T'</em>, которое можно встроить в оба исходных дерева. Встраивание из <em>T'</em> в <em>T</em>, это инъективная функция от вершин <em>T'</em> в вершины <em>T</em>, которая сохраняет метки и отношения предшествования (пропускать предшественников можно). | ||
| − | * Максимизировать размер общего поддерева, < | + | * Максимизировать размер общего поддерева, <em>|T'|</em>. |
---- | ---- | ||
Версия 06:13, 17 апреля 2023
- Деревья и с метками на вершинах.
- Найти общее встроенное поддерево, т.е. помеченное дерево T', которое можно встроить в оба исходных дерева. Встраивание из T' в T, это инъективная функция от вершин T' в вершины T, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
- Максимизировать размер общего поддерева, |T'|.
Задача в лаб22 (рид-онли просмотр)