Кухонний робот#2268

Кухонний робот (Розбір)

Нехай $A$ і $B$ — дві пляшки, які робот буде збирати послідовно. Після того як робот підніме пляшку $A$ , він повинен віднести її до однієї з чотирьох граней столу і викинути. Лише тоді робот може рушити за пляшкою $B$ . Знайдемо найкоротший шлях робота від точки $A (x_{i}, y_{i})$ A(x_i, y_i) до точки $B (x_{j}, y_{j})$ B(x_j, y_j) з обов'язковим заходом на край столу.

Відстань $A K + K B = A K + K P = A P$ AK + KB = AK + KP = AP. Знаючи координати точок $A (x_{i}, y_{i})$ A(x_i, y_i) і $P (x_{j}, - y_{j})$ P(x_j, -y_j), можна обчислити відстань

A P = (x_{j} - x_{i})^{2} + (- y_{j} - y_{i})^{2} = (x_{j} - x_{i})^{2} + (y_{j} + y_{i})^{2}

AP = \sqrt{(x_j - x_i)^2 + (-y_j - y_i)^2} = \sqrt{(x_j - x_i)^2 + (y_j + y_i)^2}

Відстань $A L + L B = A L + L Q = A Q$ AL + LB = AL + LQ = AQ. Абсциса точки $Q$ дорівнює $w + (w - x_{j}) = 2 w - x_{j}$ w + (w - x_j) = 2w - x_j. Знаючи координати точок $A (x_{i}, y_{i})$ A(x_i, y_i) і $Q (2 w - x_{j}, y_{j})$ Q(2w - x_j, y_j), можна обчислити відстань

A Q = (2 w - x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2}

AQ = \sqrt{(2w - x_j - x_i)^2 + (y_j - y_i)^2}

Відстань $A E + E B = A E + E T = A T$ AE + EB = AE + ET = AT. Знаючи координати точок $A (x_{i}, y_{i})$ A(x_i, y_i) і $T (- x_{j}, y_{j})$ T(-x_j, y_j), можна обчислити відстань

A T = (- x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2} = (x_{j} + x_{i})^{2} + (y_{j} - y_{i})^{2}

AT = \sqrt{(-x_j - x_i)^2 + (y_j - y_i)^2} = \sqrt{(x_j + x_i)^2 + (y_j - y_i)^2}

Відстань $A D + D B = A D + D S = A S$ AD + DB = AD + DS = AS. Ордината точки $S$ дорівнює $l + (l - y_{j}) = 2 l - y_{j}$ l + (l - y_j) = 2l - y_j. Знаючи координати точок $A (x_{i}, y_{i})$ A(x_i, y_i) і $S (x_{j}, 2 l - y_{j})$ S(x_j, 2l - y_j), можна обчислити відстань

A S = (x_{j} - x_{i})^{2} + (2 l - y_{j} - y_{i})^{2}

AS = \sqrt{(x_j - x_i)^2 + (2l - y_j - y_i)^2}

Знайдемо найменшу відстань, яку потрібно пройти роботу, щоб викинути пляшку, розташовану в точці $(x_{i}, y_{i})$ (x_i, y_i), за край столу. Ця відстань дорівнює мінімуму з чотирьох значень:

min (x_{i}, y_{i}, w - x_{i}, l - y_{i})

min(x_i, y_i, w - x_i, l - y_i)

Саме такий шлях робот повинен буде пройти, щоб викинути останню пляшку.

Початкове положення робота і координати всіх пляшок задані. Розглянемо граф, у якому нульова вершина відповідає початковому положенню робота, а решта вершин — пляшкам. Відстань між нульовою вершиною і кожною з решти визначається як евклідова відстань між відповідними точками. Відстань між пляшками $i$ і $j$ задається як мінімальний шлях, який робот повинен пройти від пляшки $i$ до пляшки $j$ , обов'язково побувавши на межі столу. Оскільки на столі розташовано $n$ пляшок, граф міститиме $n + 1$ n + 1 вершину.

Далі потрібно знайти в цьому графі Гамільтонів шлях мінімальної довжини. Після того як робот дійде до останньої пляшки, до загальної довжини шляху потрібно додати відстань, необхідну для викидання цієї пляшки за край столу. Пошук Гамільтонового шляху виконується за допомогою динамічного програмування з використанням масок, з асимптотичною складністю $O (n^{2} \cdot 2^{n})$ O(n^2 \cdot 2^n).

Приклад

Нижче наведено початкове положення робота і координати пляшок.

Довжина найкоротшого шляху робота дорівнює

1 + 3^{2} + 2^{2} + 1 = 2 + 13 \approx 5.605

1 + \sqrt{3^2 + 2^2} + 1 = 2 + \sqrt{13} ≈ 5.605

Реалізація алгоритму

Оголосимо константу $I N F$ , що позначає безкінечність, і константу $M A X$ — максимальну кількість точок у Гамільтоновому шляху.

#define INF 1e18
#define MAX 20

Оголосимо масив $d p$ , у якому зберігатимуться значення $d p (S, i)$ dp(S, i), що перераховуються динамічно. Координати пляшок зберігаємо в точках $(x_{i}, y_{i}) (1 \leq i \leq n)$ (x_i, y_i)~(1 \le i \le n). Початкове положення робота зберігаємо в точці $(x_{0}, y_{0})$ (x_0, y_0).

double dp[1 << MAX][MAX + 1];
double x[MAX], y[MAX], m[MAX][MAX];

Функція solve обчислює значення $d p (S, l a s t)$ dp(S, last) — мінімальну відстань, щоб пройти всі точки з множини $S$ , закінчивши на вершині $l a s t$ . Множина $S$ кодується цілим числом $ma s k$ . Тоді:

d p (S, l a s t) = i \in S ∖ l a s t min (d p (S ∖ l a s t, i) + m [i] [l a s t]),

dp(S, last) = \min_{i \in S \setminus {last}}⁡(dp(S \setminus {last},i) + m[i][last]),

де

$m [i] [l a s t]$ m[i][last] — відстань між точками $i$ і $l a s t$ ,
$S ∖ l a s t = ma s k ˆ (1 << l a s t)$ S\setminus {last} = mask~\^{}~(1<< last) — множина $S$ без елемента $l a s t$ .

Змінна $r es$ відповідає комірці $d p [ma s k] [l a s t]$ dp[mask][last], тому при зміні $r es$ автоматично оновлюється і значення $d p [ma s k] [l a s t]$ dp[mask][last].

double solve(int mask, int last)
{
  double &res = dp[mask][last];
  if (res == INF)
  {
    mask ^= (1 << last);
    for (int i = 1; i < n; i++)
      if ((mask & (1 << i)) && (i != last)) 
        res = min(res, solve(mask, i) + m[i][last]);
  }
  return res;
}

C++

Функція f повертає найкоротшу відстань від точки $(x [i], y [i])$ (x[i], y[i]) до границі столу.

double f(int i)
{
  return min(min(x[i], y[i]), min(l - y[i], w - x[i]));
}

Функція dist повертає відстань між точками $(x [i], y [i])$ (x[i], y[i]) і $(x [j], y [j])$ (x[j], y[j]).

double dist(int i, int j)
{
  return sqrt((x[i] - x[j])*(x[i] - x[j]) + 
              (y[i] - y[j])*(y[i] - y[j]));
}

Основна частина програми. Читаємо розмір столу $w$ і $l$ .

scanf("%d %d", &w, &l);

Читаємо кількість пляшок $n$ і їх координати $(x [i], y [i])$ (x[i], y[i]).

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%lf %lf", &x[i], &y[i]);

Початкові координати робота зберігаємо в $(x [0], y [0])$ (x[0], y[0]).

scanf("%lf %lf", &x[0], &y[0]);

До $n$ пляшок додаємо нульову вершину, що відповідає початковому положенню робота. Після цього $n$ збільшується на одиницю і стає рівним загальному числу вершин у графі. Вершини графа нумеруються від $0, 1, ..., n - 1$ 0, 1, ..., n - 1.

n++;

Обчислюємо попарні відстані між пляшками. Відстань між пляшками $i$ і $j$ визначається як мінімальний шлях, який робот повинен пройти від пляшки $i$ до пляшки $j$ з обов'язковим заходом на межу столу.

for (i = 1; i < n - 1; i++)
for (j = i + 1; j < n; j++)
  m[i][j] = m[j][i] =
    min(
 	min(sqrt((x[i] + x[j])*(x[i] + x[j]) + (y[i] - y[j])*(y[i] - y[j])),
     sqrt((2 * w - x[i] - x[j])*(2 * w - x[i] - x[j]) + 
          (y[i] - y[j])*(y[i] - y[j]))),
 min(sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] + y[j])*(y[i] + y[j])),
     sqrt((x[i] - x[j])*(x[i] - x[j]) + 
          (2 * l - y[i] - y[j])*(2 * l - y[i] - y[j])))
       );

C++

Спочатку значення $d p (S, i)$ dp(S, i) невідомі, тому присвоюємо їм значення плюс нескінченність.

for (i = 0; i < 1 << n; i++)
for (j = 0; j < n; j++)
  dp[i][j] = INF;

Множині ${0}$ відповідає маска $1$ . Встановимо $d p ({0}, 0) = 0$ dp(\{0\}, 0) = 0, оскільки мінімальний шлях із нульової вершини в саму себе без відвідування інших вершин дорівнює нулю. У змінній $t o t a l$ будемо зберігати бажану мінімальну довжину Гамільтонова шляху.

dp[1][0] = 0; total = INF;
for (i = 1; i < n; i++) dp[1 | (1 << i)][i] = dist(0, i);

Знаходимо Гамільтонів шлях мінімальної довжини. Значення $2 n - 1$ 2n - 1 відповідає множині всіх вершин ${0, 1, 2, ..., n - 1}$ \{0, 1, 2, ..., n - 1\}. Обчислюємо мінімум серед усіх значень:

d p ({0, 1, 2, ..., n - 1}, i) + f (i), 1 \leq i < n

dp(\{0, 1, 2, ..., n - 1\}, i) + f(i), 1 \le i < n

Після знаходження мінімальної довжини Гамільтонова шляху до результату потрібно додати відстань, яку робот проходить, щоб викинути останню $i$ -ту пляшку за межу столу — вона дорівнює $f (i)$ .

for (i = 1; i < n; i++)
  total = min(total, solve((1 << n) - 1, i) + f(i));

Виводимо бажану мінімальну довжину шляху.

printf("%.6lf\n", total);