Hardprob/Minimum Vehicle Scheduling On Tree — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)\s*:\s*(\w)\s*→\s*(\w)</m> на <em>\1: \2 → \3</em>) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \ldots на …) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 9: | Строка 9: | ||
Найти расписание автомобильного объезда, которое | Найти расписание автомобильного объезда, которое | ||
| − | * стартует в < | + | * стартует в <em>v<sub>0</sub></em>, |
* посещает все вершины в <m>T</m> | * посещает все вершины в <m>T</m> | ||
| − | * возвращается в < | + | * возвращается в <em>v<sub>0</sub></em> |
* для любой вершины <m>v_{i}</m> | * для любой вершины <m>v_{i}</m> | ||
** обработка стартует не раньше <m>r(v_i)</m>. | ** обработка стартует не раньше <m>r(v_i)</m>. | ||
| − | Т.е. найти перестановку <m>\pi</m> вершин <m>1, | + | Т.е. найти перестановку <m>\pi</m> вершин <m>1, …, \vert V\vert</m>, и функция ожидания <em>w</em>, такую что для любого <em>i</em> |
<m> | <m> | ||
\begin{displaymath} | \begin{displaymath} | ||
Текущая версия на 22:45, 17 апреля 2023
- Дерево с выделенным корнем ,
- на ребрах заданы времена проезда в
- прямом f: E → N
- обратно направлении b: E → N
- на вершинах
- время отгрузки-загрузки r: V → N
- время обработки h: V → N
- на ребрах заданы времена проезда в
Найти расписание автомобильного объезда, которое
- стартует в v0,
- посещает все вершины в
- возвращается в v0
- для любой вершины
- обработка стартует не раньше .
Т.е. найти перестановку вершин , и функция ожидания w, такую что для любого i где d(u,v) означает длину уникального пути из u в v.
Минимизировать полное время выполнения, т.е.
Задача в лаб17 (рид-онли просмотр)