Hardprob/Minimum Geometric Steiner 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 (обсуждение | вклад) (Массовая правка: замена \subseteq на ⊆) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор точек на плоскости <m> | + | * Набор точек на плоскости <m>P⊆ Z\times Z</m>. |
| − | * Найти конечный набор точек Штейнера, <m> | + | * Найти конечный набор точек Штейнера, <m>Q⊆ Z\times Z</m>. |
* Минимизировать полный вес минимального остовного дерева для набора вершин <m>P\cup Q</m>, где вес ребра <m>\left<(x_1,y_1),(x_2,y_2)\right></m> это округленная евклидова длина <m>\begin{displaymath}\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil.\end{displaymath}</m> | * Минимизировать полный вес минимального остовного дерева для набора вершин <m>P\cup Q</m>, где вес ребра <m>\left<(x_1,y_1),(x_2,y_2)\right></m> это округленная евклидова длина <m>\begin{displaymath}\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil.\end{displaymath}</m> | ||
Версия 11:08, 17 апреля 2023
- Набор точек на плоскости .
- Найти конечный набор точек Штейнера, .
- Минимизировать полный вес минимального остовного дерева для набора вершин , где вес ребра это округленная евклидова длина
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND13»
- Задача в википедии