Hardprob/Maximum Common Embedded Sub-Tree — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --> * Деревья <m>T_1</m> и <m>T_2</m> с метками на вершинах. * Найти общее встроенное поддерево,…»)
 
(Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
<!-- start -->
+
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Деревья <m>T_1</m> и <m>T_2</m> с метками на вершинах.
+
* Деревья <em>T<sub>1</sub></em> и <em>T<sub>2</sub></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>, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).  
+
* Максимизировать размер общего поддерева, <em>|T'|</em>.
* Максимизировать размер общего поддерева, <m>\vert T'\vert</m>.
+
  
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 +
<!-- * {{has-testdata-and-visualization}} -->
 +
<!-- * {{has-pyomo-model}} -->
 +
<!-- * {{has-npc-reduction}} -->
 +
<!-- * {{add-random-fuzzing-tests}} -->
 
----
 
----
 
<small>
 
<small>

Текущая версия на 22:33, 17 апреля 2023

  • Деревья T1 и T2 с метками на вершинах.
  • Найти общее встроенное поддерево, т.е. помеченное дерево T', которое можно встроить в оба исходных дерева. Встраивание из T' в T, это инъективная функция от вершин T' в вершины T, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
  • Максимизировать размер общего поддерева, |T'|.

Задача в лаб22 (рид-онли просмотр)