Hardprob/Minimum Schedule Length

Ссылки сюда (2) →

• Сеть , где
  • граф G=(V,E)
  • емкость на вершинах b: V → N
  • емкость на ребрах c: E → N
  • T — набор токенов , где , и p — это либо путь из u в v или пустое множество.

• Найти расписание S, т.е. последовательность f₀, …, f_l конфигурационных функций , таких что
  • для любого токена , и .
  • для любого и для любого токена t,
    • если и , то
      • (u,v)∈ E
• Минимизировать длину расписания, l.

---

Код в «minimum-schedule-length.ipynb» на гитлаб или живьем в лабе

---

• Задача в базе NP-полных задач Вигго Кана

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.