Hardprob/Shortest Weight-Constrained Path — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, длина <m>l:E \rightarrow N</m>, и вес <m>w:E \rightarrow N</m> ребер, выделенные ве…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена \ldots на …) |
||
| (не показано 8 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | <!-- start --> | + | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> |
| − | * Граф < | + | * Граф <em>G=(V,E)</em>, длина <em>l: E → N</em>, и вес <em>w: E → N</em> ребер, |
| − | выделенные вершины <m>s,t | + | выделенные вершины <m>s,t ∈ V</m> и целое <em>W</em>. |
| − | * Найти простой путь в <em>G</em> весом не больше <em>W</em>, т.е. последовательность различных вершин <m>s=v_1,v_2, | + | * Найти простой путь в <em>G</em> весом не больше <em>W</em>, т.е. последовательность различных вершин <m>s=v_1,v_2,…,v_m=t</m>, таких, что <m>∀ i, 1 ≤ i ≤ m-1, (v_i ,v_{i+1}) ∈ E</m> и <m>\sum_{i=1}^{m-1}w(v_i,v_{i+1}) ≤ W</m>. |
| − | * Минимизировать длину этого пути, т.е. <m>\sum_{i=1}^{ | + | * Минимизировать длину этого пути, т.е. <m>\sum_{i=1}^{m-1}l(v_i,v_{i+1})</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:45, 17 апреля 2023
- Граф G=(V,E), длина l: E → N, и вес w: E → N ребер,
выделенные вершины и целое W.
- Найти простой путь в G весом не больше W, т.е. последовательность различных вершин , таких, что и .
- Минимизировать длину этого пути, т.е. .
Код в «shortest-weight-constrained-path.ipynb» на гитлаб или живьем в лабе
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND30»