Hardprob/Minimum Vehicle Scheduling On Tree — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \rightarrow на →) |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)\s*:\s*(\w)\s*→\s*(\w)</m> на <em>\1: \2 → \3</em>) |
||
| Строка 2: | Строка 2: | ||
* Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>, | * Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>, | ||
** на ребрах заданы времена проезда в | ** на ребрах заданы времена проезда в | ||
| − | *** прямом < | + | *** прямом <em>f: E → N</em> |
| − | *** обратно направлении < | + | *** обратно направлении <em>b: E → N</em> |
** на вершинах | ** на вершинах | ||
| − | *** время отгрузки-загрузки < | + | *** время отгрузки-загрузки <em>r: V → N</em> |
| − | *** время обработки < | + | *** время обработки <em>h: V → N</em> |
Найти расписание автомобильного объезда, которое | Найти расписание автомобильного объезда, которое | ||
Версия 22:16, 17 апреля 2023
- Дерево с выделенным корнем ,
- на ребрах заданы времена проезда в
- прямом f: E → N
- обратно направлении b: E → N
- на вершинах
- время отгрузки-загрузки r: V → N
- время обработки h: V → N
- на ребрах заданы времена проезда в
Найти расписание автомобильного объезда, которое
- стартует в ,
- посещает все вершины в
- возвращается в
- для любой вершины
- обработка стартует не раньше .
Т.е. найти перестановку вершин , и функция ожидания w, такую что для любого i где d(u,v) означает длину уникального пути из u в v.
Минимизировать полное время выполнения, т.е.
Задача в лаб17 (рид-онли просмотр)