Genişlik üzrə axtarış 0-1#10056

Genişlik üzrə axtarış 0-1 (Həll təhlili)

$0 - 1$ 0 - 1 eninə axtarış (və ya $0 - 1$ 0 - 1 BFS) — qraflarda ən qısa yolları tapmaq üçün istifadə olunan klassik enliyinə axtarış (BFS) alqoritminin modifikasiyasıdır. Bu alqoritmin fərqi ondan ibarətdir ki, qrafdakı tillərin çəkiləri yalnız $0$ və ya $1$ qiymətlərini ala bilər, bu da axtarışı əhəmiyyətli dərəcədə optimallaşdırmağa imkan verir.

Məsələnin qoyuluşu. Təsəvvür edək ki, bizdə tillərinin çəkiləri ya $0$ , ya da $1$ olan çəkili qraf var. Məsələn, belə bir qrafa şəhərlə işlədiyimiz zaman rast gəlmək olar — bəzi yollar pulsuzdur (çəki $0$ ), digərləri üçün isə pul ödəmək lazımdır (çəki $1$ ). Biz bu çəkiləri nəzərə alaraq qrafın bir təpəsindən digərinə qədər olan ən qısa yolu tapmaq istəyirik.

Standart eninə axtarış alqoritminin problemi. Klassik enliyinə axtarış (BFS) alqoritminin mürəkkəblik qiymətləndirməsi $O (V + E)$ O(V + E)-dir və qrafda ən qısa yolların tapılması üçün istifadə olunur, lakin o, yalnız bütün tillərin eyni çəkiyə malik olduğu qraflar üçün uyğundur. Əgər tillərin çəkiləri müxtəlifdirsə, bu yanaşma artıq səmərəsizdir — bu məqsədlər üçün adətən mürəkkəblik qiymətləndirməsi $O (V^{2} + E)$ O(V^2 + E) və ya $O (E \cdot l o g_{2} V)$ O(E \cdot log_2V) olan Deykstra alqoritmi tətbiq olunur. Lakin yalnız $0$ və $1$ çəkilərinə malik qraflar üçün daha sürətli yanaşma mövcuddur — $0 - 1$ 0 - 1 BFS.

0-1 BFS Alqoritmi

$0 - 1$ 0 - 1 BFS-də biz ikitərəfli növbədən (deque) istifadə edirik. Fikir aşağıdakından ibarətdir:

Biz başlanğıc $s t a r t$ təpəsindən başlayırıq və onu $0$ -a bərabər başlanğıc məsafə ilə növbəyə əlavə edirik.
Hər bir $u$ təpəsinin (növbənin başından çıxarılan) emalı zamanı onun $v$ qonşularına baxırıq:
- Əgər $(u, v)$ tilinin çəkisi $0$ -dırsa, onda qonşu $v$ təpəsi cari məsafə ilə $(d i s t [v] = d i s t [u])$ (dist[v] = dist[u]) növbənin əvvəlinə yerləşdirilir.
- Əgər $(u, v)$ tilinin çəkisi $1$ -dirsə, onda qonşu $v$ təpəsi məsafəni bir vahid artıraraq $(d i s t [v] = d i s t [u] + 1)$ (dist[v] = dist[u] + 1) növbənin sonuna yerləşdirilir.
Bu, təpələrin emalının düzgün qaydasını səmərəli şəkildə saxlamağa imkan verir: daha kiçik çəkili tillər vasitəsilə əldə edilə bilən təpələr daha əvvəl emal olunur.

Beləliklə, ikitərəfli növbədən istifadə bizim həmişə növbənin əvvəlində minimal məsafəli təpəyə çıxışımızın olmasını təmin edir, alqoritmin işinin mürəkkəbliyi isə $O (V + E)$ O(V + E) olaraq qalır.

$0 - 1$ 0 - 1 eninə axtarışda tillərin relaksasiyası Deykstra alqoritmindəki klassik relaksasiyaya bənzəyir, lakin tillərin çəkisi əsasında təpələrin sıralanması üçün prioritet növbə (priority queue) əvəzinə ikitərəfli növbədən (deque) istifadə edilməsi ilə fərqlənir.

$0 - 1$ 0-1 BFS alqoritmi (klassik BFS-dən fərqli olaraq) hər bir təpənin ilk dəfədən minimal məsafə ilə ziyarət ediləcəyinə zəmanət vermir, xüsusən əgər eyni təpəyə bir neçə yolla çatmaq mümkündürsə. Buna görə də tillərin relaksasiyası mütləqdir.

Aşağıdakı nümunəyə baxaq. Ən qısa məsafələr $d i s t$ massivini və $q$ növbəsini işə salaq:

$1$ təpəsindən çıxan tillərə baxaq. $(1, 2)$ və $(1, 3)$ tillərini relaksasiya edək. $3$ təpəsi növbənin əvvəlinə, $2$ təpəsi isə növbənin sonuna yerləşdiriləcək.

Ancaq $d i s t [2] = 1$ dist[2] = 1 qiyməti yekun deyil. $3 - 4$ 3 - 4 tili boyunca keçək və $d i s t [4] = 0$ dist[4] = 0, $q u e u e = (4, 2)$ queue = (4, 2) təyin edək. Sonra $4 - 2$ 4 - 2 tilinə baxaq və $d i s t [2]$ qiyməti $0$ -a bərabər olacaq. Beləliklə, $d i s t [2]$ relaksasiya nəticəsində iki müxtəlif qiymət aldı (əvvəlcə $1$ , sonra $0$ ).

Nümunə

Nümunədə verilmiş qraf aşağıdakı formaya malikdir:

$1$ təpəsindən $3$ təpəsinə qədər olan ən qısa yolun uzunluğu $1$ -ə bərabərdir, ən qısa yolun özü isə aşağıdakı formadadır: $1 - 2 - 3$ 1 - 2 - 3.

Alqoritmin realizasiyası

Sonsuzluq sabitini elan edək.

#define INF 0x3F3F3F3F

Ən qısa məsafələr $d i s t$ massivini və qrafın qonşuluq siyahısı $g$ -ni elan edək.

vector\u003cint\u003e dist;
vector\u003cvector\u003cpair\u003cint, int\u003e\u003e\u003e g;

bfs funksiyası $s t a r t$ təpəsindən enliyinə axtarışı reallaşdırır.

void bfs(int start)
{

Ən qısa məsafələr $d i s t$ massivini işə salaq.

  dist = vector\u003cint\u003e(n + 1, INF);
  dist[start] = 0;

Növbəni elan edək və ona başlanğıc $s t a r t$ təpəsini daxil edək.

  deque\u003cint\u003e q;
  q.push_back(start);

Növbə boş olmayana qədər enliyinə axtarış alqoritminə davam edirik.

  while (!q.empty())
  {

Növbənin başından $v$ təpəsini çıxarırıq.

    int v = q.front(); q.pop_front();

$v$ təpəsindən çıxan tilləri gəzirik.

    for (auto edge : g[v])
    {
      int to = edge.first;
      int w = edge.second;

Cari $(v, t o)$ (v, to) tilinin çəkisi $w$ -dir. Onun relaksasiyasını aparırıq.

      if (dist[to] \u003e dist[v] + w)
      {

Əgər til relaksasiya olunursa, onda $d i s t [t o]$ dist[to] ən qısa məsafəsini yenidən hesablayırıq.

        dist[to] = dist[v] + w;

$w$ tilinin çəkisindən asılı olaraq $t o$ təpəsini növbənin sonuna və ya əvvəlinə əlavə edirik.

        if (w == 1)
          q.push_back(to);
        else
          q.push_front(to);
      }
    }
  }
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d %d %d", \u0026n, \u0026m, \u0026s, \u0026d);
g.resize(n + 1);

Qrafı oxuyuruq.

for (i = 0; i \u003c m; i++)
{
  scanf("%d %d %d", \u0026a, \u0026b, \u0026w);
  g[a].push_back({ b, w });
  g[b].push_back({ a, w });
}

$s$ başlanğıc təpəsindən enliyinə axtarışı işə salırıq.

bfs(s);

$d$ təpəsinə qədər olan ən qısa məsafəni çap edirik.

printf("%d\n", dist[d]);