Open Classic Hard Problems — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<templatedpagelist> showtotal=yes namespace=Main limit=500 order=creation desc output=template template=IncludeCard redirect=no category=ClassicHardProblems notca…»)
(нет различий)

Версия 21:59, 5 апреля 2023

Всего страниц найдено: 209.

----


  • Набор инструкций, формирующих некий блок без переходов,
    • N доступных регистров,
    • стоимость S_i, \ \ 1≤i≤N чтения и записи в регистр i.
  • Порядок резервирования регистров для этой последовательности инструкций.
  • Минимизировать полную стоимость чтения-записи в регистры.

Задача в лаб22 (рид-онли просмотр)


  • Направленный ациклический граф G=(V,A)
  • Найти вычисление на G, которое использует k регистров, т.е.
    • порядок v1, …, vn на вершинах V
    • последовательность S0, …, Sn подмножеств V, удовлетворяющих
      • \vert S_i\vert ≤ k
      • S0 — пустое
      • Sn — содержит все вершины с нулевой входящей степенью в G
      • 1 ≤ i ≤ n, v_i ∈ S_i, S_i - \{v_i\} ⊆ S_{i-1}, и S_{i-1} содержит все вершины u, для которых (v_i,u) ∈ A
  • Минимизировать число регистров,т.е. k.

Задача в лаб22 (рид-онли просмотр)


  • Группа G перестановок из n символов.
  • Найти базу для G, т.е. последовательность точек b1, …, bk, такой, что единственный элемент в G фиксирующий все эти bi это идентичное преобразование.
  • Минимизировать размер базы, т.е. k.

Задача в лаб22 (рид-онли просмотр)


  • Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
    • префикса и суффикса x длины j-1,
    • набора подстрок x длины j.
  • Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
  • Минимизировать значение порядка, т.е. j.

Задача в лаб22 (рид-онли просмотр)


  • Недетерминированная машина Тьюринга M, двоичная входная строка x.
  • Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
  • Минимизировать длину кратчайшей из этих строк,т.е. \min(\vert c\vert,\vert x\vert) → \min.

Задача в лаб22 (рид-онли просмотр)


  • Недетерминированная машина Тьюринга M, двоичная входная строка x.
  • Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
  • Максимизировать длину кратчайшей из этих строк,т.е. \min(\vert c\vert,\vert x\vert) → \max.

Задача в лаб22 (рид-онли просмотр)


  • Два конечных множества P, N двоичных строк.
  • Найти детерминированный конечный автомат \left(Q,\{0,1\},\delta,q_0,F\right), который принимает все строки из P и отвергает все строки из N.
  • Минимизировать число состояний в автомате.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, коллекция C скобок-конъюнкций не больше чем из трех литералов.
  • Найти переименовываемую хорнову подформулу C' от C, т.е. подмножество C'⊆ C, т.к. здесь существует подмножество S ⊆ U, таких переменных, что перестановка литералов в S ∪ \bar{S} делает C' хорновой булевой формулы, где \bar{S} = \{\bar{u} \mid u ∈ S\}.
  • Максимизировать размер подформулы, т.е. |C'|.

Задача в лаб22 (рид-онли просмотр)


  • M — набор булевых значений для n переменных.
  • Найти «Horn core» от M, т.е. подмножество M' ⊆ M, такое, что M' набор булевых значений удовлетворяющих формулу Хорна, [1].
  • Размерность ядра, т.е. |M'|.

Задача в лаб22 (рид-онли просмотр)


  • Доказательство Фреге π для некоторой тавтогологии φ.
  • Найти более короткое доказательство Фреге π' для φ, более короткое чем π, т.е. содержащая не больше символов чем π.
  • Минимизировать число символов в π'.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, коллекция C конъюнкций, не больше k литералов (литерал — переменная или ее отрицание),
  • Найти присваивание переменным из U.
  • Максимизировать число выполненных скобок-дизъюнкций.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, коллекция C равенств, т.е. пар литералов над переменными из U.
  • Найти присваивание переменным U.
  • Минимизировать число невыполненных равенств.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, коллекция C 3CNF-формул.
  • Найти присваивание переменным U.
  • Минимизировать число выполненных формул.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, коллекция C 3CNF-формул.
  • Найти присваивание переменным U.
  • Максимизировать число выполненных формул.

Задача в лаб22 (рид-онли просмотр)


  • Набор булевых переменных U, булевое выражение F над U, неотрицательное число-ограничение B ∈ N,
    • для каждой переменной u ∈ U, задан вес w(u)∈ N, такой что B\le\sum\limits_{u∈ U} w(u)≤2\,B.
  • Найти значения переменных для U, т.е. выбор подмножества U'⊆ U переменных которых выставили в «истину», а остальные U-U' соответственно выставлены в «ложь». Значение решения R будет
    • либо B, если F ложно
    • либо \displaystyle\sum\limits_{v∈ U'} w(v), если F истинно.
  • Максимизировать R.

Задача в лаб22 (рид-онли просмотр)


  • Непересекающиеся множества булевых переменных X,Z, коллекция C дизъюнкций не больше чем три литерала, где каждый литерал переменная или отрицание из X∪Z.
  • Найти присваивание для X и Z, чтобы все скобки в C выполнялись.
  • Минимизировать число переменных из Z, которые будут установлены в «истину».

Задача в лаб22 (рид-онли просмотр)


  • Непересекающиеся множества булевых переменных X,Z, коллекция C дизъюнкций не больше чем три литерала, где каждый литерал переменная или отрицание из X∪Z.
  • Найти присваивание для X и Z, чтобы все скобки в C выполнялись.
  • Максимизировать число переменных из Z, которые будут установлены в «истину».

Задача в лаб22 (рид-онли просмотр)


  • Множество переменных U,
  • Коллекция C скобок-конъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше 3.
  • Найти присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб22 (рид-онли просмотр)


  • Множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше 3.
  • Найти истинное присваивание для U, и подмножество скобок C'⊆ C, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.
  • Максимизировать размер этого подмножества |C'| → max

Задача в лаб22 (рид-онли просмотр)


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб22 (рид-онли просмотр)


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Максимизировать число выполненных скобок.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.
  • Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.


  • Множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание.
  • Найти истинное присваивание для U.
  • Максимизировать число скобок.

Задача в лаб22 (рид-онли просмотр)


  • Простой многоугольник P и многоугольник видимости V внутри P, где робота станет видно.
  • Найти схему движения робота до момента, когда его станет видно.
  • Минимизировать расстояние пройденного роботом.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E),
    • стартовая вершина s ∈ V, где изначально размещается робот,
    • целевая вершина t ∈ V
    • подмножество вершин W⊆V где изначально находятся препятствия.
  • Найти схему движения робота и этих препятствий. На каждом шагу, либо робот, либо одно препятствие можно переместить на незанятую вершину. Надо переместить робота в целевую вершину.
  • Минимизировать число шагов.

Задача в лаб22 (рид-онли просмотр)


  • Простое число q, набор P=\{p_1(x), p_2(x),…,p_m(x)\} полиномов степени не большей 2, над полем GF[q] от n переменных. Эти полиномы не должны содержать мономов {x_i}^2 \ ∀i.
  • Найти в подмножество полиномов P'⊆ P, у которых будет некий общий корень.
  • Максимизировать размер этого подмножества, т.е. P'.

Задача в лаб22 (рид-онли просмотр)


  • K непересекающихся выпуклых компактных множеств, блоков B^k
  • M неотрицательных непрерывных выпуклых функций f^k_m: B^k→ R.
  • Найти положительное число λ, такое что

\begin{displaymath} \sum_{k=1}^K f^k_m(x^k)\le\lambda \mbox{ for }1≤m≤M, \mbox{ и }x^k∈ B^k\mbox{ for }1≤k≤K. \end{displaymath}

  • Минимизировать λ.

Задача в лаб22 (рид-онли просмотр)


  • Базис в решетке \{b_1,…,b_m\}, где b_i∈ Z^k, точка b_0∈ Q^k и положительное целое p.
  • Найти вектор b в решетке, не совпадающий с заданным b≠b_0, но ближайший к нему.
  • Минимизировать расстояние между b0 и b, по норме \ell_p.

Задача в лаб22 (рид-онли просмотр)


  • n размеров заданных вектором U ∈ N^n, m рюкзаков разных размеров и числом отсеков заданных векторами V ∈ N^m, C ∈ N ^m, причем \sum_i U_i = \sum_j V_j.
  • Найти размещение заданных элементов в эти рюкзаки, заданный двумя n×m матрицами,

I ∈ \{0,1\}^{n× m}, Q ∈ N ^{n× m}, такой, что

    • \sum_i Q_{i,j} ≤V_j \ \ ∀j
    • \sum_i I_{i,j} ≤C_j \ \ ∀j
    • \sum_j Q_{i,j} ≤U_i \ \ ∀i
    • I_{i,j}=0 \Rightarrow Q_{i,j}=0 \ \ ∀i,j
  • Максимизировать число упакованных элементов 
\sum_i \sum_j Q_{i,j} → \max.


Задача в лаб22 (рид-онли просмотр)


  • Неотрицательные целочисленные m×k матрицы A, C ∈ N^{m\cdot k}, неотрицательное целое b∈ N.
  • Найти
    • неотрицательный целочисленный n-вектор x∈ N^n,
    • функция f: [1..n] → [1..k]
    • такие, что \displaystyle\sum\limits_{i=1}^{n} a_{i,f(i)} x_i≤b.
  • Максимизировать 
\displaystyle\sum\limits_{i=1}^{n} c_{i,f(i)} x_i → \max.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.


  • Неотрицательная целочисленная m×n матрица A∈ N^{m\cdot n}
    • неотрицательный целочисленный вектор m-вектор b∈ N^m.
  • Найти неотрицательный целочисленный n-вектор x∈ N^n, такой что Ax≤b.
  • Максимизировать скалярное произведение c и x, т.е., \displaystyle\sum\limits_{i=1}^{n} c_i x_i → \max.


Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Maximum-knapsack.png
  • Конечное множество U, для каждого u ∈ U задан
    • вес-размер s(u)∈ Z^+
    • ценность v(u)∈ Z^+
  • Положительное целое B∈ Z^+ — размер рюкзака.
  • Выбрать подмножество U' ⊆ U, не превышающее емкость рюкзака: \displaystyle\sum\limits_{u∈ U'} s(u)≤B
  • Максимизировать ценность выбранных элементов, \displaystyle\sum\limits_{u∈ U'} v(u) → \max.


Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Временно желательно не брать — там сложный случай, работаем, чтобы заставить ЦЛП-солвер решать постановку.


  • Конечные множества P и N целочисленных n-мерных векторов.
    • P — положительные примеры
    • N — отрицательные примеры.
  • Найти гиперплоскость заданную вектором нормали w∈ Q^n и смещением w0.
  • Максимизировать число примеров, удовлетворяющих этой гиперплоскости:
\vert\{x∈  P: wx>w_0\}\vert+\vert\{x∈  N: wx.

Задача в лаб22 (рид-онли просмотр)


  • Система линейных уравнений Ax=b, где A целочисленная m×n—матрица, и целочисленный m-вектор b.
  • Найти рациональный n-вектор x∈ Q^n.
  • Минимизировать число уравнений, которые не выполняются найденным x.

Задача в лаб22 (рид-онли просмотр)


  • Система линейных уравнений Ax=b, где A целочисленная m×n—матрица, и целочисленный m-вектор b.
  • Найти рациональный n-вектор x∈ Q^n.
  • Максимизировать число уравнений, которые выполняются найденным x.

Задача в лаб22 (рид-онли просмотр)


  • Целочисленная m×n матрица A∈ Z^{m\cdot n}, целый m-вектор b∈Z^m.
  • Рациональный n-вектор x∈ Q^n, такой что Ax=b.
  • Минимизировать число ненулевых элементов в x.

Задача в лаб22 (рид-онли просмотр)


  • Коллекция C из n записей,
    • для каждой записи c ∈ C задана некоторая вероятность p(c), 0≤p(c)≤1.
  • Найти для каждой записи из c ∈ C размещение z(c) на плоскости, заданное целочисленными координатами, так, что все записи расположены на разных точках этой плоскости.
  • Минимизировать 
\displaystyle\sum\limits_{c_1∈  C} \displaystyle\sum\limits_{c_2∈  C} p(c_1) p(c_2) d(z(c_1),z(c_2)) → \min,

где d(z(c_1),z(c_2)) — дискретное евклидово расстояние между точками z(c_1) и z(c_2).

Задача в лаб22 (рид-онли просмотр)


  • Неотрицательная целая n×n-матрица C∈ N^{n\cdot n}, неотрицательная целая m×m-матрица D ∈ N^{m\cdot m}.
  • Найти бинарную матрицу n× m-матрицу X∈ \{0,1\}^{n\cdot m}, такую, что в каждой строке не большое одной единицы, и точно одна единица в каждой колонке.
  • Минимизировать 
\displaystyle\sum\limits_{i,j=1\atop i\not=j}^{n} \displaystyle\sum\limits_{k,l=1\atop k\not=l}^{m} C_{i,j} D_{k,l} X_{i,k} X_{j,l} → \min.

Задача в лаб22 (рид-онли просмотр)


  • Целая m×n-матрица A∈ Z^{m\cdot n}, целый m-вектор b∈ Z^m и целая m×n-матрица C∈ \{0,1\}^{m\cdot n}.
  • Найти m×n-матрицу X∈ \{0,1\}^{m\cdot n}, в которой только одна единица в каждой колонке, и

\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j}≤b_i \ \ \ ∀i∈ [1..m].

  • Минимизировать 
\displaystyle\sum\limits_{i=1}^{m} \displaystyle\sum\limits_{j=1}^{n}  C_{i,j} X_{i,j} → \min.

Задача в лаб22 (рид-онли просмотр)

Maximum-quadratic-programming.png
  • Положительное целое n, набор линейных ограничений заданных в виде m×n матрицы, и m-вектора b, задающие область S⊆ R^n ограничениями S=\{x∈ [0,1]^n: Ax≤b\}.
  • многомерный многочлен f, максимальной степени не больше 2. Имея
    • Q — симметричная положительно-полуопределенная матрица,
    • c — вектор линейных коэффициентов
  • Можно представить его в виде: f(x) = x^{T} Q x + c^{T} x
  • Максимизировать значение f в области заданной линейными ограничениями, т.е. f(x)_{x∈S} → \max.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺

Minimum-covering-integer-programming.png
  • Рациональная m×n-матрица A∈[0,1]^{m\cdot n}, рациональный m-вектор b∈ [1,∞)^m, рациональный n-вектор c∈ [0,1]^n.
  • Найти рациональный n-вектор x∈ \{0,1\}^n, такой что Ax≥b.
  • Минимизировать скалярное произведение c и x, т.е., \displaystyle\sum\limits_{i=1}^{n} c_i x_i → \min.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Maximum-packing-integer-programming.png
  • Рациональная m×n-матрица A∈[0,1]^{m\cdot n}, рациональный m-вектор b∈ [1,∞)^m, рациональный n-вектор c∈ [0,1]^n.
  • Найти рациональный n-вектор x∈ \{0,1\}^n, такой что Ax≤b.
  • Максимизировать скалярное произведение c и x, т.е., \displaystyle\sum\limits_{i=1}^{n} c_i x_i → \max.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Maximum-bounded-0-1-programming.png
  • Целая m×n-матрица A∈ Z^{m\cdot n}, целый m-вектор b∈ Z^m, неотрицательный бинарный n-вектор c∈ \{0,1\}^n.
  • Найти двоичный n-вектор x∈ \{0,1\}^n, такой что Ax ≤ b.
  • Максимизировать скалярное произведение c и x, т.е., \displaystyle\sum\limits_{i=1}^{n} c_i x_i → \max.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Minimum-0-1-programming.png
  • Целая m×n-матрица A∈ Z^{m\cdot n}, целый m-вектор b∈ Z^m, неотрицательный целый n-вектор c∈ N^n.
  • Найти двоичный n-вектор x∈ \{0,1\}^n, такой что Ax≥b.
  • Минимизировать скалярное произведение c и x, т.е., \displaystyle\sum\limits_{i=1}^{n} c_i x_i.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.


  • Дерево с выделенным корнем T=\left(V,E,v_0\right),
    • на ребрах заданы времена проезда в
      • прямом f: E → N
      • обратно направлении b: E → N
    • на вершинах
      • время отгрузки-загрузки r: V → N
      • время обработки h: V → N

Найти расписание автомобильного объезда, которое

  • стартует в v0,
  • посещает все вершины в T
  • возвращается в v0
  • для любой вершины v_{i}
    • обработка стартует не раньше r(v_i).

Т.е. найти перестановку \pi вершин 1, …, \vert V\vert, и функция ожидания w, такую что для любого i 

\begin{displaymath}

d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] ≥ r(v_{\pi(i)}) \end{displaymath} где d(u,v) означает длину уникального пути из u в v.


Минимизировать полное время выполнения, т.е.

d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi(j)}) + d(v_{\pi(j)},v_{\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0) → \min.

Задача в лаб22 (рид-онли просмотр)


  • Сеть N=\left(V,E,b,c\right), где
    • граф G=(V,E)
    • емкость на вершинах b: V → N
    • емкость на ребрах c: E → N
    • T — набор токенов t=\left(u,v,p\right), где u,v ∈ V, и p — это либо путь из u в v или пустое множество.
  • Найти расписание S, т.е. последовательность f0, …, fl конфигурационных функций f_i:T → V, таких что
    • для любого токена t=\left(u,v,p\right), f_0(t)=u и f_l(t)=v.
    • для любого 0 ≤ i ≤ l-1 и для любого токена t,
      • если f_i(t)=v и f_{i+1}(t)=w, то
        • (u,v)∈ E
        • \vert\{t':f_i(t')=w\}\vert < b(w)
        • \vert\{t':f_{i+1}(t')=w\}\vert ≤ b(w)
        • \vert\{t':f_i(t')=v ∧ f_{i+1}(t')=w \}\vert ≤ c(v,w)
  • Минимизировать длину расписания, l.

Задача в лаб22 (рид-онли просмотр)


  • Граф передачи файла, т.е. граф G=(V,E), ограничения пропускной способности на вершинах, p: V → N и функция длины файлов на ребрах L: E → N.
  • Найти расписание передачи файла, т.е. функция s: E → N, такая что для каждой вершины v и для каждого момента t ∈ N, 
\begin{displaymath}\vert\{u : (u,v) ∈  E \wedge s(e) ≤ t ≤ s(e)+L(e)\}\vert ≤ p(v). \end{displaymath}
  • Минимизировать время выполнения расписания, т.е. 
\max_{e ∈  E}(s(e)+L(e))

Задача в лаб22 (рид-онли просмотр)


  • m∈ Z^+ процессоров (станков, рабочих мест и т.п.), набор работ J, каждая работа j∈J
    • состоит из последовательности из nj операций o_{i,j} с 1 ≤ i ≤ n_j, для каждой такой операции
      • требуется процессор p_{i,j}∈ [1..m]
      • и длина l_{i,j}∈ N.
  • Найти «расписание работы цеха» для J, набор однопроцессорных расписаний, f_p : \{o_{i,j} : p_{i,j}=p\} → N, такое, что
    • из f_p(o_{i,j}) > f_p(o_{i',j'}) следует f_p(o_{i,j}) ≥ f_p(o_{i',j'})+l_{i',j'}
    • f_p(o_{i+1,j}) ≥ f_p(o_{i,j})+l_{i,j}
  • Минимизировать время выполнения расписания, т.е.
\max\limits_{j∈  J} f_p(o_{n_j,j})+l_{n_j,j} → \min.

Задача в лаб22 (рид-онли просмотр)


такой, что для если две операции o_{i,j} и o_{i,j'}, с f_i(j) < f_i(j') распланированы последовательно (т.е. нет другой операции o_{i,j"}, для которой f_i(j) < f_i(j") < f_i(j')), и требуют разных компиляторов (т.е. k(j)\neq k(j')), то f_i(j') ≥ f_i(j) + l_{i,j} + s_i(k(j')).

  • Минимизировать время выполнения расписания, т.е.
\max\limits_{j∈  J} f_2(j)+l_{2,j} → \min.

Задача в лаб22 (рид-онли просмотр)


  • m∈ Z^+ процессоров, множество J работ, каждый j ∈ J состоит
    • m операций o_{i,j}, 1 ≤ i ≤ m (o_{i,j} должна выполняться на процессоре i)
    • для каждой такой операции есть длительность l_{i,j}∈ N.
  • Найти «расписание работы цеха» для J (см. Hardprob/Minimum_Open-Shop_Scheduling), такая что, для каждого j ∈ J, и 1≤i, f_{i+1}(j)≥ f_i(j)+l_{i,j}.
  • Минимизировать время выполнения расписания, т.е.
\max\limits_{j∈  J} f_m(j)+l_{m,j} → \min


Задача в лаб22 (рид-онли просмотр)


  • m∈ Z^+ процессоров, множество J работ, каждый j ∈ J состоит
    • m операций o_{i,j}, 1 ≤ i ≤ m (o_{i,j} должна выполняться на процессоре i)
    • для каждой такой операции есть длительность l_{i,j}∈ N.
  • Найти «расписание работы цеха» для J, т.е. коллекцию однопроцессных расписаний f_i: J→ N, \ \ 1≤i≤m,
    • таких, что из f_i(j) > f_i(j') следует f_i(j) ≥ f_i(j') + l_{i,j'}, т.е. для каждого j ∈ J, интервалы [f_i(j),f_i(j)+l_{i,j}) не пересекаются.
  • Минимизировать время выполнения расписания, т.е.
\max\limits_{1≤i≤m, j∈  J} f_i(j)+l_{i,j} → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, набор P из 3 процессоров, каждая задача t ∈ T имеет
    • длительность l(t) ∈ Z^+
    • требуемое подмножество процессоров r(t)⊆P .
  • Найти расписание для T, т.е. функция возвращающая время старта s: T → Z^+, такую что для любых двух задач t1 и t2, у которых r(t_1) ∩ r(t_2) ≠ \emptyset, либо
    • s(t_1)+l(t_1) < s(t_2)
    • s(t_2)+l(t_2) < s(t_1)
  • Минимизировать полное время расписания
 \max_{t ∈  T}(s(t)+r(t)) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, m идентичных процессоров, каждая задача t ∈ T имеет
    • время выпуска r(t)∈ Z^+
    • длительность l(t)∈ Z^+.
    • вес w(t) ∈ Z^+ .
  • Найти m-процессорное расписание для T, удовлетворяющее ограничениям времени выпуска, т.е. функция f : T → N , такая что для всех u ≥ 0 и для любого процессора i, если S(u,i) это набор задач для которых f(t)_{1} ≤ u < f(t)_{1}+l(t) и f(t)_{2}=i, то

\vert S(u,i)\vert = 1 и для каждой задачи t, f(t)_{1} ≥ r(t).

  • Минимизировать взешенную сумму времен выполнения, т.е. 
\sum_{t∈  T} w(t)(f(t)_1+l(t)) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, m идентичных процессоров, каждая задача t ∈ T имеет время выпуска r(t)∈ Z^+ и длительность l(t)∈ Z^+.
  • Найти m-процессорное расписание для T, удовлетворяющее ограничениям времени выпуска, т.е. функция f : T → N , такая что для всех u ≥ 0 и для любого процессора i, если S(u,i) это набор задач для которых f(t)_{1} ≤ u < f(t)_{1}+l(t) и f(t)_{2}=i, то

\vert S(u,i)\vert = 1 и для каждой задачи t, f(t)_{1} ≥ r(t).

  • Минимизировать полное время расписания, т.е. 
\sum_{t ∈  T}\left(f(t)_{1}-r(t)\right) → \min


Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, m процессоров…
    • для каждой задачи t ∈ T есть длительность l(t)∈ Z^+
    • для каждого процессора i ∈ [1 … m] есть фактор скорости s(i)∈ Q, где s(1)=1 и s(i)≥ 1.
  • Найти m-процессорное расписание для T, т.е. функцию f: T→ [1..m].
  • Минимизировать время завершения расписания, т.е.
\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t)/s(i) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор компиляторов C, набор задач T, m процессоров, длительности задач l(t)∈ Z^+, нужный для задачи компилятор c(t)∈ C, время запуска-настройки для каждого компилятора s(c)∈ Z^+.
  • Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач t1, …, tk, такое что
    • \sum_{i=1}^k l(t_i) = l(t)
    • и есть некоторое назначение σ = (σ_1, σ_2), которое назначает каждой подзадаче ti пару неотрицательных целых (σ_1(t_i), σ_2(t_i)), таких, что
      • 1 ≤σ_1(t_i) ≤m
      • σ_2(t_{i+1}) ≥ σ_2(t_i) + l(t_i), \ \ 1 ≤i < k
    • Это расписание должно удовлетворять дополнительному ограничению:
      • Если два подзадачи ti от t и tj' от t', у которых σ_2(t_i) < σ_2(t_j') запланированы последовательно на одном процессоре (т.е. σ_1(t_i) = σ_1(t_j'), и нет другой подзадачи t_k", у которой σ_1(t_k") = σ_1(t_i) и σ_2(t_i) < σ_2(t_k") < σ_2(t_j'), то
        • σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t')) — если у них один и тот же компилятор (c(t) = c(t'))
        • σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t')) — если эти компиляторы разные.
  • Минимизировать общее время выполнения, т.е. максимум по всем подзадачам σ_2(t_i)+l(t_i)

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T с длинами l(t), m процессоров, число ресурсов r, ресурсные потребности задач r_i(t), \ 1 ≤ i ≤ r \ ∀t ∈ T и ресурсные ограничения bi.
  • Найти m-процессорное расписание для T, соблюдающую ресурсные ограничения, т.е. функцию f: T → Z, такую что
    • ∀ u ≤ 0, если S(u) будет набор задач t для которых f(t) ≤ u < f(t)+l(t), то \vert S(u)\vert ≤ m и

\begin{displaymath} ∀ i \ \sum_{t ∈ S(u)}r_i(t) ≤ b_i. \end{displaymath}

  • Минимизировать общую длительность расписания, т.е. 
\max_{t ∈  T}(f(t)+l(t)) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, m процессоров, единичная время-длина l(t)=1, \ \ ∀t∈ T, частичный подрядок предшествования на T.
  • Найти m-процессорное расписание для T, соблюдающую отношения предшествования, т.е. функцию f: T → N, такую что
    • ∀u ≥ 0 \ \ \vert f^{-1}(u)\vert ≤ m
    • из t < t' следует f(t') > f.
  • Минимизировать время выполнения расписания, т.е. 
\max\limits_{t∈  T} f(t) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, m процессоров, время выполнения l(t,i)∈ Z^+, \ \ ∀t∈ T, \ i∈ [1..m].
  • Найти m-процессорное расписание для T, т.е. функцию f: T→ [1..m].
  • Минимизировать время выполнения расписания, т.е. 
\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t,i) → min

Задача в лаб22 (рид-онли просмотр)


  • Набор активностей J, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности t_j > 0, ∀ j∈ J , положительный бюджет B, и для каждой активности j ∈ J задана монотонно невозрастающая ступенчатая функция с lj ступенями:

\begin{displaymath}

c_j(t)=\left\{\begin{array}{ll} ∈ fty&\mbox{if $0≤t< a_{j,1}$},\\ c_j(a_{j,i})&\mbox{if $a_{j,i}≤t, где ∈ fty>c_j(a_{j,1})>\cdots>c_j(a_{j,l_j}).

  • Найти однопроцессорное расписание для J которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет \sum_{j∈ J} c_j(t_j)≤B.

StasFomin 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно.

  • Минимизировать общее время всех активностей \sum_{j∈ J} t_j

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, для каждой задачи есть
    • время релиза r(t)∈ Z^+ (раньше запускать задачу нельзя)
    • длина l(t)∈ Z^+
    • вес w(t)∈ Z^+
  • Найти однопроцессорное расписание для T, которое соблюдает времена релиза, т.е. функция f: T → N, которая
    • ∀u ≥ 0, если S(u) это набор задач t, для которых f(t)≤u , то \vert S(u)\vert = 1 (в процессе только одна задача)
    • ∀t \ \ f(t)≥ r(t) (раньше релиза не запускаем)
  • Минимизировать взвешенную сумму времен завершения
\sum_{t∈  T} w(t)(f(t)+l(t)) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, положительное целое D, для каждой задачи есть целочисленная задержка $0≤d(t)≤D$,
    • направленный ациклический граф G=\left(T,E\right), определяющий отношения предшествования для этих задач.
  • Найти одно-процессорное расписание для T, соблюдающее отношения предшествования и задержки, т.е. инъективная функция S: T→ Z^+, такая, что для каждого ребра \left∈ E, выполняется S(t_j)-S(t_i)>d(t_i)
  • Минимизировать время выполнение всего расписания.
\max\limits_{t∈  T} S(t) → \min

Задача в лаб22 (рид-онли просмотр)


  • Набор задач T, для каждой задачи есть длина l(t)∈ Z^+,
    • направленный ациклический граф G=\left(T,E\right), определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес w(t_1,t_2), измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
  • Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка \pi: [1..\vert T\vert ]→ [1..\vert T\vert ], такая что для каждого ребра \left∈ E выполняется \pi^{-1}(i)<\pi^{-1}(j).
  • Минимизировать произведение затрат на хранение и времени, т.е.

\begin{displaymath} \displaystyle\sum\limits_{ \left∈ E} w(t_{\pi(i)},t_{\pi(j)}) \displaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}). \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Набор T задач, для каждой задачи t ∈ T есть длина l(t)∈ Z^+, вес w(t)∈ Z^+ и дедлайн d(t)∈ Z^+, подмножество S ⊆ T и положительное целое K.
  • Найти однопроцессорное расписание σ для T, такая что сумма w(t) по всем t ∈ T для которых σ(t)+l(t)>d(t) не превосходит K.
  • Максимизировать число работ в S, выполненных в срок.

Задача в лаб22 (рид-онли просмотр)


  • Дерево T=(V,E),
    • нормализованный вес на вершинах w: V → Q^{+}, \sum_{v ∈ V}w(v)=1,
    • некоторая страничная емкость p.
  • Найти компактную упаковку T на страницах емкости p, т.е. функция \tau : V → Z^{+}, такая, что |\tau^{-1}(i)| = p
  • Минимизировать страничные сбои этой упаковки, т.е.

\sum_{v ∈ V}c_{\tau}(v)w(v), где 


\begin{displaymath}
c_{\tau}(v)=\sum_{i=0}^{l(v)-1}\Delta_{\tau}(v_{i}),
\end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Положительный целый d, коллекция S1, …, Sk наборов d-мерных точек.
  • Найти множество точек S' конгруэнтное каждому множеству Si из коллекции.
  • Максимизировать размер этого общего набора точек S'.

Задача в лаб22 (рид-онли просмотр)


  • Произвольный многоугольник P.
  • Найти коллекцию из m прямоугольников, чье объединение точно эквивалентно многоугольнику P.
  • Минимизировать m — число элементов в этой коллекции.

Задача в лаб22 (рид-онли просмотр)


  • Коллекция T1, …, Tn деревьев.
  • Найти дерево T' изоморфное какому-то поддереву, для каждого Ti.
  • Максимизировать число узлов в этом общем поддереве T'.

Задача в лаб22 (рид-онли просмотр)


  • Конечный алфавит Σ, конечный набор R строк из \Sigma^*.
  • Найти строку w∈ \Sigma^*, такую она является подпоследовательностью любой строки x ∈ R, т.е. ее можно получить вычеркивая символы из любого x.
  • Максимизировать длину этой подпоследовательности \vert w| → \max.

Задача в лаб22 (рид-онли просмотр)


  • Конечный алфавит Σ, конечный набор R строк из \Sigma^*.
  • Найти строку w∈ \Sigma^*, такую что каждая строка x ∈ R является ее подстрокой, т.е. w=w_0 x w_1, для каких-то w_0,w_1∈ \Sigma^*.
  • Минимизировать длину этой суперстроки |w|.

Задача в лаб22 (рид-онли просмотр)


  • Конечный алфавит Σ, конечный набор R строк из \Sigma^*.
  • Найти строку w∈ \Sigma^*, такую что каждая строка x ∈ R является ее подпоследовательностью, т.е. можно получить x вычеркиванием символов из w.
  • Минимизировать длину этой суперпоследовательности |w|.

Задача в лаб22 (рид-онли просмотр)


  • Нужно хранить некий набор A каких-то штук, каждая a ∈ A из которых имеет
    • размер s(a)∈ Z^+
    • время прибытия r(a) ∈ Z^{+}
    • время отбытия d(a) ∈ Z^{+}
  • Найти допустимый план резервирования места хранения, т.е. функция σ: A → Z^{+}, такая что для любых a,a'∈ A, если I(a) ∩ I(a') непусто, то либо d(a) ≤ r(a'), либо d(a') ≤ r(a).
  • Минимизировать максимальный требуемый размер, т.е.
\max_{a ∈  A}(σ(a)+s(a)-1) → \min.

Задача в лаб22 (рид-онли просмотр)


  • Набор X векторов из [0,1]^{d}.
  • Найти разбиение X на m подмножеств S_{1},…,S_{m}
  • Максимизировать покрывающих подмножеств среди \{S_{1},…,S_{m}\}, где «покрывающим» подмножество S векторов из [0,1]^{d}, считается, если для всех i ≤ d сумма i-х компонент элементов из S будет не меньше 1.

Задача в лаб22 (рид-онли просмотр)


  • Набор прямоугольников B=\{(x_i,y_i)\} с положительными размерами (ширина x_i ≤ 1, высота yi).
  • Найти упаковку P из прямоугольников B в плоский контейнер единичной ширины и бесконечной высоты. Прямоугольники должны быть упакованы без пересечений и вращать их нельзя.
  • Минимизировать высоту упаковку P.

Задача в лаб22 (рид-онли просмотр)


  • Конечное множество элементов U, с заданными размерами s(u)∈ Z^+, ∀ u∈ U, и емкость контейнера — положительное целое B.
  • Найти разбиение U на непересекающиеся множества U1, U2, …, Um, такие что сумма размеров элементов в каждом Ui не превышает B.
  • Минимизировать число используемых контейнеров, т.е. число непересекающихся множеств, m.

Задача в лаб22 (рид-онли просмотр)


  • Массив n×n неотрицательных целых A, положительное число p.
  • Найти разбиение A на p непересекающихся квадратных подмассивов.
  • Минимизировать максимальный «вес» (сумма элементов) подмассива из разбиения.

Задача в лаб22 (рид-онли просмотр)


  • Массив n×n неотрицательных целых A, положительное число p.
  • Найти
    • p-1 горизонтальных делителей 0=h_0
    • p-1 вертикальных делителей 0=v_0
    • разбивающих A на p^2 блоков.
  • Минимизировать максимальный «вес» блока

\begin{displaymath}

\max_{1≤i≤p\atop 1≤j≤p} \sum_{v_{i-1}

Задача в лаб22 (рид-онли просмотр)


  • Конечное множество A, задан размер s(a)∈ Z^+ для каждого a ∈ A, и целое K ≥ 2 .
  • Найти разбиение A на множество из K непересекающихся множеств A1, A2, …, AK.
  • Минимизировать сумму квадратов их размеров 

\begin{displaymath}

\sum_{i=1}^{K}\left(\sum_{a∈ A_i} s(a)\right)^2 → \min. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Непересекающиеся множества S1, …, Sm, и для любых i \neq j, x ∈ S_i, y

∈ S_j, чтобы была задана неотрицательная емкость c(x,y).

  • Найти систему представителей T, т.е. набор T, такой, что для любого i, |T ∩ S_i|=1.
  • Максимизировать «емкость» системы представителей, т.е.

$\sum_{x,y ∈ T}c(x,y).

Задача в лаб22 (рид-онли просмотр)


  • Три множества X, Y, W и функция стоимости c: X×Y×W → N
  • Найти назначение A, т.е. подмножество A ⊆ X×Y×W, такой что каждый элемент из X ∪ Y ∪ W принадлежит только одной тройке из A.
  • Минимизировать стоимость назначения, т.е.

\sum_{(x,y,w) ∈ A}c(x,y,w) → \min

Задача в лаб22 (рид-онли просмотр)


  • Конечное множество A и размер s(a)∈ Z^+ для каждого его элемента a ∈ A, выделенный элемент a_0∈ A, и подмножество S⊆A.
  • Найти разбиение A, т.е. подмножество A' ⊆ A, такой, что

\sum_{a∈ A'} s(a)=\sum_{a∈ A-A'} s(a)

  • число элементов из S на той стороне разбиения, где a0.

Задача в лаб22 (рид-онли просмотр)


  • Множество точек на целочисленной плоскости P ⊆ Z×Z.
  • Найти набор центров C ⊆ Q×Q на Евклидовой плоскости, такой, что каждая точка в P будет покрыта диском с радиусом r и центром в одной из точек в C.
  • Минимизировать размер этого дискового покрытия, т.е. |C|

Задача в лаб22 (рид-онли просмотр)


  • Коллекция C подмножеств конечного множества S.
  • Найти множество представителей (hitting set) для C, т.е. подмножество S' ⊆ S, такое, что S' содержит по крайней мере один элемент из каждого подмножества из C.
  • Минимизировать размер множества представителей, \vert S'| → \min.

Задача в лаб22 (рид-онли просмотр)


  • Коллекция C подмножеств конечного множества S.
  • Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) x_1, x_2 ∈ S, есть некоторое подмножество c∈C', которое содержит точно один элемент из этой пары.
  • Минимизировать мощность этой подколлекции |C'|.

Для понимания названия задачи, представим, что S — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней.

Задача в лаб22 (рид-онли просмотр)

Minimum-exact-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать суммарных объем покрывающих подмножеств, т.е. \sum\limits_{c\in C'} |c| → \min

Задача в лаб22 (рид-онли просмотр)

Minimum-set-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать число покрывающих подмножеств, т.е. |C'|→min.

Задача в лаб22 (рид-онли просмотр)

Maximum-set-splitting.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти разбиение S, на непересекающиеся множества S1 и S2.
  • Максимизировать число подмножеств C, которые «разделены» между S1 и S2, т.е. не лежат полностью в S1 или S2.

Задача в лаб22 (рид-онли просмотр)

Maximum-set-packing.svg
  • Коллекция конечных множеств C.
  • Найти упаковку множеств, т.е. коллекцию непересекающихся множество C'⊆ C.
  • Максимизировать размер этой упаковки, т.е. |C'|

Задача в лаб22 (рид-онли просмотр)

Maximum-3-dimensional-matching.svg
  • Множество T ⊆ X×Y×Z, с непересекающимися X, Y, и Z.
  • Найти трехмерное сопоставление для T, т.е. подмножество M⊆T, такое, что его элементы не пересекаются ни по одной координате.
  • Максимизировать размер сопоставления, т.е. |M| → max.

Задача в лаб22 (рид-онли просмотр)


  • Семейство непересекающихся полигонов P1, …, Pk.
  • Найти разделяющее подразделение, т.е. семейство из k-полигонов R1, …, Rk, с попарно непересекающимися границами, такими, что для каждого i, Pi ⊆ Ri.
  • Минимизировать размер подразделения, т.е. полное число ребер в полигонах R1, …, Rk.

Задача в лаб22 (рид-онли просмотр)


  • Коллекция C=\{(a_i,b_i) : 1 ≤ i ≤ n\} пар целых, задающих координаты на плоскости.
  • Найти триангуляцию набора точек из C, т.е. коллекция E непересекающихся отрезков соединающих некоторые точки из C, так, что внутренность этой выпуклой оболочки подразделена на треугольники.
  • Минимизировать округленно-евклидову длину триангуляции, т.е.

\begin{displaymath}

\left\lceil\sum_{((a_i,b_i),(a_j,b_j)) ∈ E}\sqrt{(a_i-a_j)^2+(b_i-b_j)^2}\right\rceil → \min. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Направленный планарный граф G=(V,E)
  • Найти планарный ортогональный чертеж графа G, т.е. отрисовка вершин G как точек плоскости, а ребер как последовательностей горизонтальных и вертикальных отрезков, так, что нет пересечений.
  • Минимизировать число сгибов на чертеже.

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), расстояния d(v_i,v_j)∈ N удовлетворяющие неравенство треугольника.
  • Разбиение F=\{A_1,A_2,…, A_{k},B_1,B_2,…, B_{k}\} вершин V.
  • Минимизировать максимальное расстояние между вершинами разных множеств с одним индексом, т.е.

\begin{displaymath}

\max\limits_{i∈ [1..k]} \max\limits_{v_1∈ A_{i}\atop v_2∈ B_{i}} d(v_1,v_2) → \min \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), доходы p(v_i,v_j)∈ N.
  • Найти места для строительства мест обслуживания, F⊆ V,\ \vert F\vert=k.
  • Максимизировать максимальный полный доход

\sum\limits_{v∈ V}\max\limits_{f∈ F} p(v,f) → \max .

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), стоимости перемещения с(v_i,v_j)∈ N, с неравенством треугольника, F⊆V — места, где можно построить место обслуживания (туалеты, магазины, заправки), ∀v∈ F, f(v)>0 — стоимость этого строительства, ∀v∈ V, d(v)>0 — потребности в разных местах.
  • Найти места для строительства мест обслуживания, F' ⊆ F.
  • Минимизировать

\sum_{v∈ F'} f(v)+\sum_{u∈ F'}\sum_{v∈ V} d(v)\cdot c(u,v) → \min

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), расстояния d(v_i,v_j)∈ N, с неравенством треугольника.
  • Найти набор для размещения k мест обслуживания (туалеты, магазины, заправки), подмножество \vert F\vert=k.
  • Минимизировать минимальное расстояние между двумя такими местами:

\min\limits_{f_1,f_2∈ F} d(f_1,f_2) → \min

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Декомпозиция графа на два фактора F1 и F2 с одинаковыми диаметрами.
  • Минимизация диаметра F1.

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E) и расстояния d(e)∈ N.
  • Найти k-медианное множество, т.е. подмножество V' ⊆ V, \vert V'\vert=k.
  • Минимизировать расстояния от каждой вершины до ближайшей медианы, т.е. 

\begin{displaymath}

\sum_{v ∈ V}\min_{w ∈ V'} d(v,w) → \min \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), расстояния d(v_i,v_j)∈ N, удовлетворяющие неравенству треугольника, для вершин v ∈ V заданы стоимость строительство центра c(v)∈ N, некий «вес» использования w(v), ограничение на бюджет L ∈ N.
  • Места размещения поставок в рамках бюджета, т.е. подмножество вершин S⊆V, для которых \sum_{v∈ S} c(v)≤L.
  • Минимизировать максимальную взвешенную дистанцию от вершины до ближайшего поставщика, т.е.

\begin{displaymath} \max\limits_{v∈ V} \min\limits_{s∈ S} w(v)d(v,s). \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Конечное множество X, расстояние d(x,y)∈ N, для каждой пары, удовлетворяет неравенству треугольника.
  • Найти подразделение X на непересекающиеся подмножества C1, C2, …, Ck.
  • Минимизировать сумму всех расстояний между элементами одного подмножества, т.е.

\begin{displaymath}\displaystyle\sum\limits_{i=1}^{k} \displaystyle\sum\limits_{v_1,v_2∈ C_i} d(v_1,v_2) → \min. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Конечное множество X, расстояние d(x,y)∈ N, для каждой пары, удовлетворяет неравенству треугольника.
  • Найти подразделение X на непересекающиеся подмножества C1, C2, …, Ck.
  • Минимизировать максимальное расстояние между элементами одного подмножества, т.е.

\max\limits_{i∈ [1..k]\atop x,y∈ C_i} d(x,y) → min

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E) и расстояния d(v_i,v_j)∈ N, удовлетворяющие неравенству треугольника.
  • Найти к-центр, т.е. подмножество C ⊆ V, \vert C\vert=k, с минимальным расстоянием от всех вершин до какого-то узла из этого множества.
  • Минимизировать максимальное расстояние от каждой вершины до ближайшего к ней «центра»:

\max\limits_{v∈ V} \min\limits_{c∈ C} d(v,c) → \min

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), вершина-источник v_0∈ V.
  • Найти схему вещания. В момент «0» только v0 содержит сообщение, которое надо передать в кажду вершину. В каждый момент любая вершина, котора получила сообщение, может передать это сообщение максимум одному из своих соседей.
  • Минимизировать время передачи, т.е. момент времени, когда все вершины получат сообщение.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), емкости на ребрах c: E→ Z^{+}, вершина-источник s, коллекция вершин-стоков t1, …, tk, с привязанными неотрицательными целочисленными запросами \rho_1,…,\rho_k, такое, что \rho_i≤c(e), ∀ e∈ E, ∀ i∈ [1..k].
  • Найти для каждого типа i единый путь s → t_i, такой что все запросы удовлетворены, и полный поток проходящий через любое ребро e ограничено c(e).
  • Минимизировать \max_{e∈ E} f(e)/c(e), где f(e) это полный поток проходящий через e.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), пути на ребрах l: E → N, набор вершин-источников S⊆V, сток t ∈ V, функция запросов d:S→ Z^+, конечный набор типов кабелей, характеризующихся емкостью и стоимостью единицы длины.
  • Найти сеть из этих кабелей, т.е. количество кабелей каждого типа для каждого ребра, причем такое, чтобы выполнить все запросы из источников к стоку. Запрос каждого источника должен идти по одному пути от источника к стоку.
  • Минимизировать полную стоимость этой сети.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), пути на ребрах l: E → N, и некоторая пара вершин s,t в V. Найти два непересекающихся по вершинам пути в G, соединающих s и t, т.е. две последовательности вершин u1, u2, …, um и v1, v2, …, vn, такие что
    • \vert\{u_1,u_2,…,u_m,v_1,v_2,…,v_n\}\vert=m+n
    • (s,u_1) ∈ E
    • (s,v_1) ∈ E
    • (u_m,t) ∈ E
    • (v_n,t) ∈ E
    • ∀i (u_i ,u_{i+1}) ∈ E
    • ∀i (v_i ,v_{i+1}) ∈ E
  • Минимизировать максимальную длину этих путей, т.е.

\max(l(s,u_1)+\sum_{i=1}^{m-1} l(u_i,u_{i+1})+l(u_m,t), l(s,v_1)+\sum_{i=1}^{n-1} l(v_i,v_{i+1})+l(v_n,t))

Задача в лаб22 (рид-онли просмотр)


  • Мультиграф G=(V,E), коллекция пар вершин T=\{(s_1,t_1),(s_2,t_2),…,(s_k,t_k)\}.
  • Найти коллекцию непересекающихся по ребрам путей в G соединающих некоторые из пар (si, ti), т.е. путь это последовательность вершин u1, u2, …, um, такая что для некоторого i, u_1=s_i, u_m=t_i, и для всех j, (u_j ,u_{j+1})∈ E.
  • Максимизация числа пар вершин (si, ti), которые будут соединены этими путями.

Задача в лаб22 (рид-онли просмотр)


  • Дерево T=(V,E), пропускная способность на ребрах c: E → N, k пар вершин (si, ti).
  • Найти поток f_i ∈ N, для каждой пары (si, ti), такой что ∀ e∈ E,\ \sum_{i=1}^k f_iq_i(e) ≤ c(e), где q_i(e)=1, если e лежит на (единственном, тут дерево) пути из si в ti, и 0 в противном случае.
  • Максимизировать сумму потоков \sum_{i=1}^k f_i

Задача в лаб22 (рид-онли просмотр)


  • Направленный граф G=(V,E), вершины-источники s_1, …, s_k ∈ V, вершины-стоки t_1, …, t_k ∈ V, емкость ребер c: E → R, ограничения на вершинах b: V → R, и для любой вершины v, есть некий порядок исходящих ребер.
  • Найти приоритетный поток f, т.е. функция f: E→R, такая что
    • для любого ребра e, f(e) ≤ c(e)
    • для любой вершины v ∈ V-\{s_1, …,

s_k, t_1, …, t_k\}, поток сохраняется в v

    • для любой вершины v
      • поток покидающий v не превышает b(v)
      • для исходящей любой пары ребер e_1, e_2, если f(e_1) < c(e_1) и e_1 < e_2, то f(e_2)=0.
  • Максимизировать поток, приходящей в первый сток t1, т.е. \sum_{(x,t_1) ∈ E}f(x,t_1).

Задача в лаб22 (рид-онли просмотр)


  • Неотрицательные симметричные n×n матрицы A и B.
  • Найти перестановку \pi: [1..n]→ [1..n].
  • Максимизировать \sum_{i\ne j} a_{\pi(i),\pi(j)} b_{i,j}.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), стартовая вершина r ∈ V, длины на ребрах ∀e∈ E, l(e)∈ N, удовлетворяющие неравенству треугольника.
  • Найти обход, стартующий в r, обходящий все вершины в G, т.е. перестановка \pi: [1..\vert V\vert→ V, такая что \pi(1)=r.
  • Минимизировать \sum_{v∈ V} d_{\pi}(r,v), где d_{\pi}(r,v) — полное расстояние пройденное в этом пути от стартовой вершины, до вершины v.

Задача в лаб22 (рид-онли просмотр)


  • m× n-массив шлюзов, коллекция сетей C, т.е. наборов по три шлюза.
  • Найти прямые отрезки-связи соединяющие шлюзи в каждой сети.
  • Минимизировать самое большое число связей, соединающих два шлюза в данном массиве.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), длина l: E → N, и вес w: E → N ребер,

выделенные вершины s,t ∈ V и целое W.

  • Найти простой путь в G весом не больше W, т.е. последовательность различных вершин s=v_1,v_2,…,v_m=t, таких, что ∀ i, 1 ≤ i ≤ m-1, (v_i ,v_{i+1}) ∈ E и \sum_{i=1}^{m-1}w(v_i,v_{i+1}) ≤ W.
  • Минимизировать длину этого пути, т.е. \sum_{i=1}^{m-1}l(v_i,v_{i+1}).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти простой путь в G, т.е. набор различных вершин v1, v2, …, vm, такой что ∀ i, \ 1 ≤ i ≤ m-1, (v_i ,v_{i+1}) ∈ E.
  • Минимизировать длину пути, т.е. число ребер в этом пути.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), длина l(e)∈ N на ребрах e ∈ E, подмножества E' ⊆ E, V'⊆V.
  • Цикл в G, который заходит ровно раз в каждую вершину из V' и пересекает каждое ребро из E'.
  • Минимизировать общую длину этого цикла.

Задача в лаб22 (рид-онли просмотр)


  • Смешанный (ориентированные дуги и неориентированные ребра) граф G=\left(V,A,E\right), длины на ребрах l(e)∈ N для каждого ребра и дуги e∈ A∪ E.
  • Найти коллекцию из k циклов, каждый содержит начальную вершину s, такая, что их совокупность включает каждое дугу графа.
  • Минимизировать максимальную длину среди этих k циклов.

Задача в лаб22 (рид-онли просмотр)


  • Смешанный (ориентированные дуги и неориентированные ребра) граф G=\left(V,A,E\right), длины на ребрах l(e)∈ N для каждого ребра и дуги e∈ A∪ E, такой, что для каждой дуги, есть параллельное ребро где длина не больше.
  • Найти цикл в G (возможно с повтором вершин), такой что включает каждое направленную дугу в A по крайней мере один раз, проходя по ним в правильном направлении.
  • Минимизировать тотальную длину цикла.

Задача в лаб22 (рид-онли просмотр)


  • Мультиграф, начальная вершина s∈V, длина l(e)∈N для каждого ребра e ∈ E.
  • Найти коллекцию из k циклов, каждый содержит начальную вершину s, такая, что их совокупность включает каждое ребро графа.
  • Минимизировать максимальную длину среди этих k циклов.

Задача в лаб22 (рид-онли просмотр)


  • Набор C из m городов, стартовый город s ∈ C, финишный город f ∈ C, расстояния d(c_i,c_j)∈ N удовлетворяющие неравенству треугольника.
  • Найти простой путь из начального города s в финишный город f проходящий через все города из C, т.е. перестановка \pi: [1..m]→ [1..m], такая что v_{\pi(1)}=s и v_{\pi(m)}=f.
  • Минимизировать максимальную длину ребра в пути.

\begin{displaymath} \max\limits_{i∈ [1..m-1]}d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right). \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Набор C из m городов, стартовый город s ∈ C, расстояния d(c_i,c_j)∈ N удовлетворяющие неравенству треугольника.
  • Найти коллекцию из k подтуров, каждый из которых соедержит начальный город, и каждый город есть хотя бы в одном подтуре.
  • Минимизировать максимальную длину среди этих k подтуров.

Задача в лаб22 (рид-онли просмотр)


  • Набор C ⊆ Z×Z из m точек на плоскости.
  • Тур C, т.е. перестановка \pi: [1..m]→ [1..m].
  • Минимизировать длину тура где расстояние между точками (x1, y1) и (x2, y2) это округленная Евклидова длина 
\begin{displaymath}

\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Набор C из m городов с заданными расстояниями между ними d(c_i,c_j)∈ N для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
  • Найти тур C, т.е. перестановка \pi: [1..m]→ [1..m].
  • Минимизировать длину этого тура

d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

Задача в лаб22 (рид-онли просмотр)


  • Набор C из m городов с заданными расстояниями между ними d(c_i,c_j)∈ N для каждой пары городов.
  • Найти тур C, т.е. перестановка \pi: [1..m]→ [1..m].
  • Минимизировать длину этого тура

d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), положительное целое D<\vert V\vert.
  • Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что G'=(V, E ∪ E') имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
  • Минимизировать размер дополняющего множества |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Направленный граф G=(V,A), и весовая функция w: V×V → N.
  • Найти набор дуг A' дополнения G до связности, т.е. A' — упорядоченные пары вершин из V, такие что G'=\left(V, A ∪ A'\right) сильно связан.
  • Минимизировать вес дополняющего набора \sum_{(u,v) ∈ A'}w(u,v).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), и симметричная весовая функция w: V×V → N.
  • Найти набор ребер E' дополнения G до связности, т.е. E' — неупорядоченные пары вершин из V, такие что G'=(V, E ∪ E') двусвязен.
  • Минимизировать вес дополняющего набора \sum_{(u,v) ∈ E'}w(u,v).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), константа k ≥ 2 .
  • Найти k-реберно-связный остовный подграф G'=(V,E'), т.е. остовный подграф, который нельзя сделать несвязным, удалив меньше чем k ребер.
  • Минимизировать размер остова , т.е. |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), константа k ≥ 2 .
  • Найти k-вершинно-связный остовный подграф G'=(V,E'), т.е. остовный подграф, который нельзя сделать несвязным, удалив меньше чем k вершин.
  • Минимизировать размер остова , т.е. |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), веса на вершинах w: V → N, стоимости на ребрах c: E → N.
  • Найти разрез C⊆V.
  • Минимизировать коэффициент разреза, т.е.

\begin{displaymath}\frac{c(C)}{\min\{w(C),w(V-C)\}} \end{displaymath}, где c(C) означает сумму стоимостей ребер (u,v), таких, что либо u ∈ C и v ∉ C или u ∉ C и v ∈ C и для любого подмножества V'⊆V, w(V') означает сумму весов вершин из V'.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), рациональное b, 0.
  • Найти разбиение V на непересекающиеся множества A, B, и C, такие что \max\{\vert A\vert ,\vert B\vert\}≤b\cdot \vert V\vert, и ни одно ребро не лежит разными концами в A и B одновременно.
  • Минимизировать размер разделителя, т.е. |C|.

Задача в лаб22 (рид-онли просмотр)

Minimum-b-balanced-cut.png
  • Граф G=(V,E), веса на вершинах w: V → N, стоимости на ребрах c: E → N, рациональное число b, 0 < b ≤1/2.
  • Найти разрез C, т.е. подмножество вершин C⊆V, такой, что

\begin{displaymath} \min\{w(C),w(V-C)\}≥ b\cdot w(V), \end{displaymath} , где where w(V') означает сумму весов вершин в V'.

  • Минимизировать вес разреза, т.е. 
\begin{displaymath}\displaystyle\sum_{e∈ \delta(C)} c(e) → \min \end{displaymath},

где \delta(C)=\{e=\{v_1,v_2\}: e∈ E, v_1∈ C, v_2∈ V-C\}

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., 📺 видео 📺


  • Граф G=(V,E), пропускная способность на ребрах c: E → N, k

товаров, т.е., k пар (s_i,t_i) ∈ V^2, и запросы di для каждой пары.

  • Найти разрез, т.е. разбиение V на два непересекающихся набора V1 и V2.
  • Минимизировать емкость разреза деленную на объем запросов через этот разрез:

\begin{displaymath}\sum_{v_1∈ V_1, v_2∈ V_2 \atop (v_1,v_2) ∈ E}c(v_1,v_2)/ \sum_{i:\vert\{s_i,t_i\} ∩ V_1\vert=1}d_i. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), набор S ⊆ V×V пар «источник-терминал», веса на ребрах w: E → N.
  • Найти мультиразрез, т.е. набор ребер E' ⊆ E, удаление которых отсоединит каждый терминал от своего источника.
  • Минимизировать вес разреза, т.е. \sum_{e ∈ E'} w(e).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), набор S⊆V терминалов, веса на ребрах w: E → N.
  • Многопутевой разрез, т.е. набор ребер E' ⊆ E, удаление которых отсоединит каждый терминал от других.
  • Минимизировать вес разреза, т.е. \sum_{e ∈ E'} w(e).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), набор S=\{s_1,t_1,…,s_k,t_k\}, выделенных специальных вершин, веса для остальных вершин w: V-S → N, целое k.
  • Найти вершинный k-разрез, т.е. подмножество вершин C⊆ V-S, такое, что их удаление из графа отключает каждую специальную вершину si от ti для всех 1 ≤ i ≤ k.
  • Минимизировать сумму весов вершин в этом разрезе \displaystyle\sum_{v∈ C} w(v).

Задача в лаб22 (рид-онли просмотр)

Minimum-k-cut.png
  • Граф G=(V,E), веса на ребрах w: E → N, целое k∈ [2..\vert V\vert].
  • Найти разбиение V на k непересекающихся множеств F=\{C_1,C_2,…,C_k\}.
  • Минимизировать сумму весов между ребрами, которые между этими множествами \begin{displaymath}

\displaystyle\sum_{i=1}^{k-1}\displaystyle\sum_{j=i+1}^k \displaystyle\sum_{v_1∈ C_i\atop v_2∈ C_j} w(\{v_1,v_2\}). \end{displaymath}

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺


  • Граф G=(V,E), пропускная способность ребер c: E → N, стоимость разрушения ребра d: E → N, и бюджет B.
  • Найти стратегию атаки на эту сеть, т.е. функцию \alpha: E → [0,1], такую, что \sum_{e ∈ E}\alpha(e)d(e) ≤ B.
  • Минимизировать пропускную способность поврежденной сети, т.е. минимальный разрез в G с емкостью c'(e)=\alpha(e)c(e).

Задача в лаб22 (рид-онли просмотр)

Maximum-k-cut.png
  • Граф G=(V,E), веса на ребрах w: E → N, целое k∈ [2..\vert V\vert].
  • Найти разбиение V на k непересекающихся множеств F=\{C_1,C_2,…,C_k\}.
  • Максимизировать сумму весов между ребрами, которые между этими множествами\begin{displaymath}\displaystyle\sum_{i=1}^{k-1}\displaystyle\sum_{j=i+1}^k

\displaystyle\sum_{v_1∈ C_i\atop v_2∈ C_j} w(\{v_1,v_2\}).\end{displaymath}

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺

Maximum-directed-cut.png
  • Направленный граф G=(V,A).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число дуг, которые стартуют в V1, и заканчиваются в V2.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺


  • Направленный граф G=(V,A).
  • Найти размещение графа на плоскости.
  • Минимизируя число пересекающихся пар ребер.

Задача в лаб22 (рид-онли просмотр)

Maximum-cut.png
  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺


  • Граф G=(V,E), три функции весов на ребрах d_2(e) ≤ d_1(e) ≤ d_0(e) (для всех e ∈ E), где d_i(e) означает вес ребра e, если i его концов «обновлены», причем известна стоимость обновления c(v) для каждой вершины v ∈ V, и некое ограничивающее значение D для веса минимального остовного дерева.
  • Найти набор обновляемых вершин W⊆V, так чтобы вес минимального остовного дерева с весами dW, была ограничена D.
    • dW означает вес ребра в результате обновления вершин в W, т.е. d_W(u,v)=d_i(u,v), где \vert W∩ \{u,v\}\vert=i.
  • Минимизировать стоимость обновления вершин, т.е. c(W)=\sum_{v∈ W} c(v).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), веса w: E → N на ребрах.
  • Найти подграф E' ⊆ E из k ребер, и минимальное остовное дерево T в графе (V,E-E').
  • Минимизировать вес T.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), веса w: E → N на ребрах.
  • Найти маршрутное дерево T для G, т.е. дерево T, для которого все внутренние вершины имеют степень 3, а листья соответствуют вершинам G.
  • Минимизировать перегруженность дерева маршрутизации, т.е. минимум по максимуму для каждого ребра e по \begin{displaymath}\sum_{(u,v) ∈ E, u ∈ S, v ∉ S}w(u,v)\end{displaymath}, и где

S — это один из двух связных компонентов, полученных удалением e из T.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), веса w: E → N и пропускная способность c: E → N на ребрах, функция требований r: V×V → N.
  • Найти сеть Штейнера над G которая удовлетворит требованиям, не превысив пропускные способности, т.е. функция f: E → N, такая, что для каждого ребра e, f(e) ≤ c(e) и для любой пары вершин i и j, число непересекающихся по ребрам путей между i и j будет как минимум r(i,j), при этом, для кадого ребра e можно использовать f(e) копий ребра e.
  • Минимизировать \sum_{e ∈ E}w(e)f(e).

Задача в лаб22 (рид-онли просмотр)


  • Набор точек на плоскости P ⊆ Z×Z.
  • Найти конечный набор точек Штейнера, Q ⊆ Z×Z.
  • Минимизировать полный вес минимального остовного дерева для набора вершин P∪ Q, где вес ребра \left<(x_1,y_1),(x_2,y_2)\right> это округленная евклидова длина \begin{displaymath}\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil.\end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), метрика — веса на ребрах s: E → N, некоторое подмножество S⊆V требуемых вершин.
  • Найти дерево Штейнера, т.е. поддерево G которое включает все вершины из S.
  • Минимизировать сумму весов ребер этого поддерево.

Задача в лаб22 (рид-онли просмотр)


  • Полный граф G=(V,E), веса на ребрах w(e)∈N, e∈E, некоторое требование для каждой пары вершин r({u,v})∈N.
  • Найти основное дерево для G.
  • Минимизировать взвешенную сумму по всем парам вершин стоимостей путей по парам вершин в T, т.е., \sum_{u,v∈V} W(u,v)\cdot r(\{u,v\}), где W(u,v) означает сумму весов ребере на пути, соединающем u и v в T.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), на ребрах e ∈ E заданы вес w(e)∈ Z^+ и длина l(e)∈ N, положительное число B.
  • Найти остовный подграф E' ⊆ E для G, такой, что сумма весов ребер в E' не превосходит B.
  • Минимизировать диаметр остовного подграфа.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), длина ребер l(e) ∈ N ∀e∈E удовлетворяют неравенству треугольника.
  • Найти подмножество V'⊆V, такое, что |V'|=k
  • Максимизировать стоимость минимального остовного дерева подграфа, порожденного V'.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти остовное дерево G.
  • Минимизировать число листьев в этом остовном дереве.

Задача в лаб22 (рид-онли просмотр)


  • Множество P ⊆ Z×Z точек на плоскости.
  • Найти остовное дерево T для P, в котором нет вершин степени большей 3.
  • Минимизировать полный вес этого дерева, \sum_{(u,v) ∈ T}d(u,v), где d(u,v) — евклидово расстояние между u и v.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти остовное дерево T для G.
  • Минимизировать максимальную степень этого дерева.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), целое k ≤ n, веса на ребрах w: E → N.
  • Найти k-остовное дерево, т.е. дерево T, подграф G с по крайней мере k вершинами.
  • Минимизировать вес этогго дерева \sum_{e ∈ T}w(e).

Задача в лаб22 (рид-онли просмотр)


  • Класс C ненаправленных графов с раскраской ребер из строки цветов x.
  • Найти граф G∈ \vert C\vert и простой путь в нем, такой, что строка-последовательность ребер на этом пути как раз будет равна x.
  • Минимизировать размер множества ребер в G.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Декомпозиция на деревья, т.е. пара \left(\{X_i:i∈ I\},T\right), где T=\left(I,F\right) — некое дерево, и \{X_i\} коллекция подмножеств вершин V, такая, что
    • \bigcup_{i∈ I} X_i=V
    • для любого (v,w)∈ E существует i∈ I: u,v∈ X_i
    • для любого v ∈ V множество \{i∈ I: v∈ X_i\} образует связное поддерево T.
  • Минимизировать ширину дерева в декомпозиции на деревья, т.е. \max_{i ∈ I} \vert X_i\vert-1.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти метрический базис для G, т.е. подмножество V'⊆V, такое, что для каждой пары u,v ∈ V есть w∈ V', что длина кратчайшего пути из u в w отличается от длины кратчайшего пути из v в w.
  • Минимизировать размер этого метрического базиса, |V'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), веса на ребрах w: E → N и множество стартовых S=\{s_1, …, s_p\} и финишных D=\{d_1,…,d_p\} точек.
  • Найти связь точка-точка, т.е. подмножество ребер E' ⊆ E, таких, что для каждой пары старт-финиш, можно проложить путь в E'.
  • Минимизировать вес этой связи, \sum_{e ∈ E'}w(e)$.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) и коллекция C=\{\left(a_1,b_1\right),…,\left(a_m,b_m\right)\} пар вершин из V, начальная вершина s ∈ V, и конечная вершина f ∈ V.
  • Найти простой путь из s в f, который содержит хотя бы одну вершину из каждой пары в C.
  • Минимизировать длину пути, то есть количество ребер в пути.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) и коллекция C=\{\left(a_1,b_1\right),…,\left(a_m,b_m\right)\} пар вершин из V.
  • Найти простой путь в G, который содержит хотя бы одну вершину из каждой пары в C.
  • Минимизировать длину пути, то есть количество ребер в пути.

Задача в лаб22 (рид-онли просмотр)


  • Графы G1=(V1,E1) G2=(V2,E2).
  • Найти набор ребер E'⊆ E1, которых надо удалить из E1 и добавить в E2.
  • Минимизировать размер этого множества ребер, |E'|

Задача в лаб22 (рид-онли просмотр)


  • Деревья T1 и T2 с метками на вершинах.
  • Найти общее встроенное поддерево, т.е. помеченное дерево T', которое можно встроить в оба исходных дерева. Встраивание из T' в T, это инъективная функция от вершин T' в вершины T, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
  • Максимизировать размер общего поддерева, |T'|.

Задача в лаб22 (рид-онли просмотр)


  • Графы G1=(V1,E1) и G2=(V2,E2).
  • Найти общий порожденный подграф, т.е. подмножества V1' ⊆ V1 и V2' ⊆ V2, такие, что два подграфа G1', порожденный {V_1}' и G2', порожденный {V_1}' изоморфны.
  • Максимизировать размер общего подграфа, т.е. \vert {V_1}'\vert.

Задача в лаб22 (рид-онли просмотр)


  • Графы G1=(V1,E1) и G2=(V2,E2).
  • Найти общий подграф, т.е. подмножества E1' ⊆ E1 и E2' ⊆ E2, такие, что два подграфа G_1'=\left(V_1,{E_1}'\right) и G_2'=\left(V_2,{E_2}'\right) изоморфны.
  • Максимизировать размер общего подграфа, т.е. |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию f:V →

\{1,2,…,\vert V\vert\}.

  • Минимизировать максимальное число ребер разреза в любой целой точке, т.е.

\begin{displaymath} \max_{i∈ [1..\vert V\vert]}\vert\{\{u,v\}∈ E: f(u)≤i < f(v)\}\vert → \min \end{displaymath} .

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию f:V →

\{1,2,…,\vert V\vert\}.

  • Минимизировать сумму длин ребер в этом упорядочивании, т.е. \sum_{\{u,v\}∈ E}\vert f(u)-f(v)\vert.

Задача в лаб22 (рид-онли просмотр)


  • Направленный ациклический граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию f: V→ {1,2,…,|V|}, такую что (u,v)∈ E, f(u)<f(v).
  • Минимизировать «пропускную способность» этого упорядочивания, т.е. \max_{(u,v) ∈ E}\vert f(u)-f(v)\vert.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию f:V →

\{1,2,…,\vert V\vert\}.

  • Минимизировать «пропускную способность» этого упорядочивания, т.е. \max_{(u,v) ∈ E}\vert f(u)-f(v)\vert.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти «хордальный граф», который содержит G, как подграф, т.е. E ⊆ E'.
  • Минимизировать размер хордального графа, |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти интервальный граф, который содержит G, как подграф, т.е. E ⊆ E'.
  • Минимизировать размер интервального графа, |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Направленный граф G=(V,E).
  • Найти подмножество E' ⊆ E, такое что для каждой пары вершин u,v ∈ V, граф G'=(V,E') содержит направленный путь из u в v, тогда и только тогда, когда этот путь есть в оригинальном графе G.
  • Минимизировать размер E', т.е. |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти подмножество V'⊆V, такое, что порожденный подграф G'=\left(V',E'\right) k-раскрашиваем, т.е. есть раскраска G', размерности не больше чем k.
  • Минимизировать размер этого подмножества, |V'|.

Задача в лаб22 (рид-онли просмотр)


  • Связный граф G=(V,E) с весами на ребрах w: E → N, положительное целое k.
  • Найти k-остов G, т.е. G' — остовной подграф G такой, что для любой пары вершин u и v, длина кратчайшего пути между u и v в G' будет не больше чем в k раз больше, чем кратчайший путь между u и v в исходном графе G.
  • Минимизировать число ребер в G' (вариант — минимизировать сумму весов ребер G').

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) с весами на ребрах w: E → N, положительное целое k.
  • Найти подмножество V'⊆V, заданного размера |V'|=k
  • Максимизировать общий вес ребер подграфа порожденного V', \begin{displaymath}

\sum_{(u,v)∈ E∩ (V'× V')} w(u,v) → \max. \end{displaymath}

Задача в лаб22 (рид-онли просмотр)


  • Дерево G=(V,E) и набор деревьев H.
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G'=(V,E') не содержит ни одного поддерева изоморфного какому-нибудь дереву из H.
  • Максимизировать мощность этого подграфа |E'|

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G'=(V,E') может быть раскрашен в k-цветов, т.е. есть раскраска G' размерности не больше k.
  • Максимизировать мощность этого подграфа |E'|

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), с весом на ребрах w: E → N.
  • Найти «k»-разбиение вершин («раскраску») c: V → [1..k]
  • Минимизировать вес одноцветных ребер, т.е. \sum\limits_{(v_1,v_2) ∈ E: c(v_1)=c(v_2)}w(v_1,v_2).

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти подмножество ребер E' ⊆ E, такое что подграф G'=(V,E') — планарный.

Максимизировать размер этого планарного подграфа, |E'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E), вес на ребрах w : E → N и целое d ≥ 2
  • Найти подмножество ребер E' ⊆ E, такое что подграф G'=(V,E') связный и нет вершин степени большей d.

Максимизировать полный вес этого подграфа, \sum_{e ∈ E'}w(E)

Задача в лаб22 (рид-онли просмотр)


Направленный или ненаправленныый граф G=(V,E) и некое свойство (предикат) P над подграфами.

Найти подмножество вершин V'⊆V, такое, что подграф порожденный вершинами V-V' — связный и

имеет свойство P.

Минимизировать размер этого множества |V'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) и некое свойство (предикат) P над подграфами.
  • Найти подмножество вершин V'⊆V, такое, что подграф порожденный вершинами V' — связный и имеет свойство P.
  • Максимизировать размер этого множества |V'| → max.

Задача в лаб22 (рид-онли просмотр)


  • Направленный или ненаправленный граф G=(V,E) и некое свойство (предикат) P над подграфами.
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G=(V, E-E') имеет свойство P.
  • Минимизировать размер этого удаляемого множества ребер |E'|.

Задача в лаб22 (рид-онли просмотр)


Направленный или ненаправленный граф G=(V,E) и некое свойство (предикат) P над подграфами.


Найти подмножество вершин V'⊆V, такое, что подграф порожденный V-V' имеет свойство P.


Минимизировать размер этого удаляемого множества вершин |V'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) и некое свойство (предикат) P над подграфами.
    • Свойство наследуемое, т.е. каждый подграф G' будет удовлетворять P, если сам G' ему удовлетворял.
    • Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.
  • Найти подмножество вершин V'⊆V, такое, что подграф порожденный V' имеет свойство P.
  • Максимизировать размер этого подграфа |V'|.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти независимую последовательность в G, т.е. последовательность независимых вершин, v1, …, vm, таких, что для любого i < m, если вершина \bar v_i ∈ V соседствует с v_{i+1}, но то оно не будет соседствовать ни с одним vj для любого j ≤ i.
  • Максимизировать «m» — длину этой последовательности.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти независимое множество вершин, т.е. подмножество V'⊆V, такое что нет пары вершин в V', соединенных ребром из E.
  • Максимизировать размер этого независимого множества |V'| → max

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти клику в G, т.е. подмножество вершин V'⊆V, такое что любая пара вершин в V' соединены ребром из E.
  • Максимизировать размер клики, т.е. |V'|.

Задача в лаб22 (рид-онли просмотр)

Minimum-cut-cover.png

Граф G=(V,E).

Найти коллекцию разрезов V1, …, Vm,

т.е. коллекция подмножеств вершин V_i ⊆ V, такая что каждое ребро графа (u,v)∈ E свои концы держит в разных подмножествах, т.е.

  • либо u ∈ V_i и v ∉ V_i
  • либо u ∉ V_i и v ∈ V_i$

Минимизировать размер «m» этой коллекции.

Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺


Граф G=(V,E).

Найти семейство F непересекающихся по вершинам циклов, покрывающих V.

Минимизировать число этих циклов в F.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти полное покрытие двудольными подграфами G, т.е. коллекцию

подмножеств вершин V → $V_1,V_2,…,V_k, такую, что

  • каждое такое подмножество вершин Vi порождает полный двудольный граф.
  • каждое ребро (u,v) ∈ E содержит оба конца в каком-нибудь Vi

Минимизировать «k» — размер этого покрытия.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти покрытие кликами для G, т.е. коллекция подмножеств вершин V1, V2, …, Vk, таких, что каждая порождает полный подграф, и каждое ребро (u,v) ∈ E содержит оба своих конца в одном из Vi.
  • Минимизировать размер «k» этого покрытия кликами.

Задача в лаб22 (рид-онли просмотр)


Связный граф G=(V,E) с неотрицательными весами на вершинах w: V → N.

Найти разбиение вершин V на непустые непересекающиеся множества (V1, V2), такие,

что подграфы порожденные V1 и V2 являются связными.

Минимизировать дисбаланс разбиения, т.е.

\min\{w(V_1), w(V_2)\}, где w(V')=\sum_{v∈ V'} w(v)

Максимизировать размер этого разбиения.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E) с весами w: E → N.
  • Найти k-мощное разбиение G на деревья, т.е. непересекающаяся коллекция подмножеств E1, …, Em ребер из E, так, что подграф порожденный каждым Ei будет давать дерево, минимум из k вершин.
  • Минимизировать вес этого разбиения: \sum_i\sum_{e∈ E_i} w(e) → \min.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти разбиение на клики G, т.е. разбиение вершин V на непересекающиеся подмножества V1, V2, …, Vk, такие что для всех 1≤i≤k, подграф, порожденный вершинами из Vi будет полным графом.
  • Максимизировать размер этого разбиения.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E) с четным числом вершин, и весами на ребрах: w: E → N.

Найти непересекающиеся по пути совершенные сочетания для G, т.е. коллекция

P_1,P_2,…,P_{\vert V\vert/2} непересекающихся простых путей в G с различными финишными вершинами.

Минимизировать вес самого «тяжелого» пути в этих сочетаниях, т.е.

\max\limits_{1≤i≤\vert V\vert/2}\sum\limits_{e∈ P_i} w(e)

Задача в лаб22 (рид-онли просмотр)

  • Граф G=\left(V_G, E_G\right) и фиксированный граф H=\left(V_H,E_H\right), с по крайней мере тремя вершинами в каком-нибудь связном компоненте.
  • Найти H-сочетание для G, т.е. коллекцию G1, G2, …, Gk, непересекающихся подграфов G, каждый из которых изоморфен H.
  • Максимизировать размерность H-сочетаний, т.е. число непересекающихся подграфов Gi.

Задача в лаб22 (рид-онли просмотр)

  • Граф G=(V,E).
  • Найти «упаковку треугольников» для G, т.е. набор V1, V2, …, Vk непересекающихся подмножеств V,
    • каждое из которых содержит ровно три вершины — V_i=\{u_i,v_i,w_i\}, 1 ≤ i ≤ k
    • и все три ребра \left, \left, \left есть в E.
  • Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств Vi.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти максимальное паросочетание E', т.е. подмножество E' ⊆ E, такое, что

никакие два ребра не содержат одну вершину, но каждое ребро из E-E' с кем-то содержит общую вершину с каким-либо ребром из E' (т.е. добавить «еще одну пару» нельзя).

Минимизировать размерность паросочетания |E'|.

Задача в лаб22 (рид-онли просмотр)


Направленный граф G=(V,A).

Найти множество ребер разрезающее циклы,

т.е. подмножество $A' ⊆ A, такое, что A' содержит по крайней мере одну дугу из каждого направленного цикла в G.

Минимизировать размерность этого подмножества, \vert A'\vert.

Задача в лаб22 (рид-онли просмотр)


Направленный граф G=(V,A).

Найти множество вершин разрезающее циклы,

т.е. подмножество $V' ⊆ V, такое, что V' содержит по крайней мере одну вершину из каждого направленного цикла в G.

Минимизировать размерность этого подмножества, |V'|.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти полную раскраску ребер E, т.е. разбиение E на непересекающиеся наборы

E1, E2, …, Ek, такие, что

  • никакие два ребра из Ei не имеют общей вершины из G.

Минимизировать размерность раскраски, т.е. число этих независимых наборов Ei.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти полную раскраску G, т.е. разбиение V на непересекающиеся наборы V1, V2, …, Vk, такие, что каждый Vi

  • независимое множество в G,
  • для каждой пары этих непересекающихся множеств Vi, Vj, Vi ∪ Vj не является независимым множеством.

Максимизировать размерность раскраски, т.е. число этих независимых наборов Vi.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти раскраску G, т.е. разбиение V на непересекающиеся наборы V1, V2, …, Vk, такие, что каждый Vi независимое множество в G.
  • Минимизировать «сумму раскрасок», т.е. \sum_{1≤i≤k}\sum_{v∈ V_i} i.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти раскраску G, т.е. разбиение V на непересекающиеся наборы

V1, V2, …, Vk, такие, что каждый Vi независимое множество в G.

Минимизировать размерность раскраски, т.е. число этих независимых наборов Vi.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти независимый доминирующий набор вершин G, т.е. подмножество V'⊆V, такое, что для всех u ∈ V-V' есть
  • v ∈ V'
  • ребро (u,v)∈ E,
  • и при этом нет двух вершин в V' соединенных ребром из E.

Минимизировать мощность доминирующего набора вершин, |V'|.

Задача в лаб22 (рид-онли просмотр)


Граф G=(V,E).

Найти доминирующий набор ребер G, т.е. подмножество E' ⊆ E, такое, что для всех

e_1 ∈ E-E', где $e_2∈ E', такой что e1 и e2 совместны.

Минимизировать мощность доминирующего набора ребер |E'|

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся наборы V1, V2, …, Vk такие, что каждый Vi доминирующее множество над G.
  • Максимизировать размерность разделения, т.е. число этих непересекающихся множеств вершин Vi.

Задача в лаб22 (рид-онли просмотр)


  • Граф G=(V,E).
  • Найти «доминирующий набор» для G, то есть подмножество V'⊆V такое что для всех u ∈ V-V' cуществует v ∈ V' для которого (u,v) ∈ E.
  • Оптимизировать «кардинальность доминирующего набора», то есть, |V'| → min.

Задача в лаб22 (рид-онли просмотр)


Граф G=\left(V,E\right).

Найти, «вершинное покрытие» для «G», т.е.подмножество V'⊆V, такое, что

для каждого ребра (u,v)∈ E, по меньшей мере одна вершина — «u» или «v» принадлежит V'.

Оптимизируем размерность вершинного покрытия, т.е. |V'|

Задача в лаб22 (рид-онли просмотр)


Направленный граф G=(V,A).

Найти множество ребер разрезающее циклы,

т.е. подмножество $A' ⊆ A, такое, что A' содержит по крайней мере одну дугу из каждого направленного цикла в G.

Минимизировать размерность этого подмножества, \vert A'\vert.

Задача в лаб22 (рид-онли просмотр)

Источник — «https://discopal.ispras.ru/index.php?title=Open_Classic_Hard_Problems&oldid=23107»