Mətbəx robotu#2268

Mətbəx robotu (Həll təhlili)

$A$ və $B$ ardıcıl olaraq robot tərəfindən yığılacaq iki butulkadır. Robot butulka $A$ -nı götürdükdən sonra onu masanın dörd kənarından birinə aparmalı və atmalıdır. Yalnız bundan sonra robot butulka $B$ -nin arxasınca gedə bilər. Robotun $A (x_{i}, y_{i})$ A(x_i, y_i) nöqtəsindən $B (x_{j}, y_{j})$ B(x_j, y_j) nöqtəsinə ən qısa yolunu tapmalıyıq ki, masanın kənarından keçməsi məcburidir.

$A K + K B$ AK+KB məsafəsi $A K + K P = A P$ AK+KP=AP. $A (x_{i}, y_{i})$ A(x_i, y_i) və $P (x_{j}, - y_{j})$ P(x_j,-y_j) nöqtələrinin koordinatlarını bilsək, məsafəni hesablaya bilərik

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$ AL+LB məsafəsi $A L + L Q = A Q$ AL+LQ=AQ. $Q$ nöqtəsinin $x$ koordinatı $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) və $Q (2 w - x_{j}, y_{j})$ Q(2w-x_j,y_j) nöqtələrinin koordinatlarını bilsək, məsafəni hesablaya bilərik

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$ AE+EB məsafəsi $A E + E T = A T$ AE+ET=AT. $A (x_{i}, y_{i})$ A(x_i, y_i) və $T (- x_{j}, y_{j})$ T(-x_j, y_j) nöqtələrinin koordinatlarını bilsək, məsafəni hesablaya bilərik

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$ AD+DB məsafəsi $A D + D S = A S$ AD+DS=AS. $S$ nöqtəsinin $y$ koordinatı $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) və $S (x_{j}, 2 l - y_{j})$ S(x_j,2l-y_j) nöqtələrinin koordinatlarını bilsək, məsafəni hesablaya bilərik

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}

Robotun masanın kənarından atmaq üçün $(x_{i}, y_{i})$ (x_i, y_i) nöqtəsində yerləşən butulkaya gedərkən keçməli olduğu ən qısa məsafəni tapmalıyıq. Bu məsafə dörd qiymətdən ən kiçiyinə bərabərdir:

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

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

Məhz bu yolu robot axırıncı butulkanı atmaq üçün gedəcək.

Robotun ilkin mövqeyi və bütün butulkaların koordinatları məlumdur. Qrafda düşünək ki, sıfırıncı zirvə robotun ilkin mövqeyinə, yerdə qalan zirvələr isə butulkalara uyğun gəlir. Sıfırıncı zirvə ilə hər biri arasında məsafə müvafiq nöqtələr arasında Evklid məsafəsi ilə müəyyənləşdirilir. İki butulka $i$ və $j$ arasındakı məsafə robotun butulka $i$ -dən butulka $j$ -ə masanın kənarında mütləq olaraq keçməli olduğu minimum yol ilə təyin edilir. Masanın üzərində $n$ butulka olduğunu nəzərə alaraq, bu qraf $n + 1$ n+1 zirvəli olacaqdır.

Daha sonra bu qrafda minimal uzunluqlu Hamiltonian yolu tapmaq lazımdır. Robot sonuncu butulkaya çatdıqdan sonra yolun ümumi uzunluğuna həmin butulkanın masanın kənarından atılması üçün lazım olan məsafə əlavə edilməlidir. Hamiltonian yol axtarışını O( $n^{2} \cdot 2^{n}$ n^2 \cdot 2^n) asimptotik mürəkkəbliklə maskalar ilə dinamik proqramlaşdırma vasitəsilə həyata keçirilir.

Misal

Burada robotun ilkin mövqeyi və butulkaların koordinatları verilmişdir.

Robotun ən qısa yolunun uzunluğu

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

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

Alqoritmin tətbiqi

Konstant $I N F$ göy dəyəri ilə qəy et (sonsuzluq), və konstant $M A X$ — Hamiltonian yolda maksimum nöqtələr sayını təyin edir.

#define INF 1e18
#define MAX 20

Dinamik şəkildə hesablanacaq $d p$ dəyərinə təyin olunan $d p$ massivini eləcə də butulkanın koordinatları $x_{i}, y_{i} (1 \leq i \leq n)$ x_i, y_i~(1 \le i \le n) saxlanan nöqtələrdə elan edək. Robotun ilkin mövqeyini $x_{0}, y_{0}$ x_0, y_0 nöqtəsində saxlayırıq.

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

solve funksiyası $d p (S, l a s t)$ dp(S, last) dəyərini hesablayır — $S$ çoxluğunda olan bütün nöqtələri keçərək, $l a s t$ zirvəsində bitirmək üçün lazım olan minimum məsafədir. $S$ çoxluğu tam sayı $ma s k$ ilə kodlaşdırılır. Onda:

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]),

burada

$m [i] [l a s t]$ m[i][last] — $i$ və $l a s t$ nöqtələri arasındaki məsafə,
$S ∖ l a s t = ma s k ˆ (1 << l a s t)$ S\setminus {last} = mask~\^{}~(1<< last) — $l a s t$ isdəkləri olmayan $S$ çoxluğu.

$d p [ma s k] [l a s t]$ dp[mask][last] hüceyrəsinə uyğun olan dəyişən $r es$ , dəyişəndə $d p [ma s k] [l a s t]$ dp[mask][last] dəyişimləri avtomatik olaraq yenilənir.

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 funksiyası $(x [i], y [i])$ (x[i], y[i]) nöqtəsindən masanın kənarına qədər ən qısa məsafəni qaytarır.

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

dist funksiyası $(x [i], y [i])$ (x[i], y[i]) və $(x [j], y [j])$ (x[j], y[j]) nöqtələri arasındakı məsafəni qaytarır.

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

Proqramın əsas hissəsi. Masa ölçülərini $w$ və $l$ oxuyuruq.

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

Butulkaların sayı $n$ və onların koordinatlarını $(x [i], y [i])$ (x[i], y[i]) oxuyuruq.

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

Robotun ilkin koordinatlarını $(x [0], y [0])$ (x[0], y[0]) nöqtəsində saxlayırıq.

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

$n$ -ə əlavə olaraq robotun ilkin mövqeyinə uyğun sıfırıncı zirvəni əlavə edib, artıq $n$ bir artırılır və ümumi qrafda zirvə sayı olur. Qrafiyada zirvələr $0, 1, ..., n - 1$ 0, 1, ..., n - 1 olaraq nömrələnir.

n++;

Butulkalar arasında cüt-cüt məsafələri hesablayırıq. İki butulka $i$ və $j$ arasındakı məsafə robotun butulka $i$ -dən butulka $j$ -ə masanın kənarına mütləq olaraq keçərək gedəcək minimum yolla təyin edilir.

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++

İlkin olaraq $d p (S, i)$ dp(S, i) dəyərləri məlum olmadığından, onlara sonsuzluq dəyəri atanır.

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

${0}$ çoxluğuna $1$ maskası uyğundur. $d p ({0}, 0) = 0$ dp(\{0\}, 0) = 0 edək, çünki başlanğıc zirvə öz üzərinə qayıtmağı tələb etməyən ən qısa yol sıfıra bərabərdir. $t o t a l$ dəyişənində tələb olunan minimal Hamiltonian yolun uzunluğunu saxlayacağıq.

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

Minimal uzunluqlu Hamiltonian yolu tapırıq. $2 n - 1$ 2n-1 dəyəri ${0, 1, 2, ..., n - 1}$ \{0, 1, 2, ..., n-1\} çoxluğuna uyğundur. Bütün dəyərlərin ən kiçiyini hesablayırıq:

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

Minimal Hamiltonian yolun uzunluğunu tapdıqdan sonra nəticəyə sonuncu $i$ -ci butulkanın masanın kənarına atılması üçün robotun keçəcəyi məsafə əlavə olunur ki, bu da $f (i)$ -yə bərabərdir.

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

Nəticə olaraq minimum yolun uzunluğunu çıxarırıq.

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