Cześć,
Próbuję rozwiązać to zadanie z algorytmiki:
https://szkopul.edu.pl/problemset/problem/5ngwR2pw5IQsTAOKQL3qFgjm/site/?key=statement
Mój algorytm (https://4programmers.net/Pastebin/14665) liczy, do których wierzchołków agenci mogą dotrzeć w kolejnych dniach, a potem szuka części wspólnej. Chcę go jeszcze przyspieszyć, licząc te dane równocześnie dla obu agentów i szukając części wspólnej, żeby móc zakończyć działanie od razu jak się ona pojawi (obecnie program liczy dane dla jednego agenta na całe m dni, a potem dla drugiego - strata czasu). Napotkałem jednak na kłopot - rozwiązanie przekracza limit pamięci (wynosi on 32MB, program przechodzi bezbłędnie test załączony w zadaniu, ale wszystkie inne, które są ukryte, oblewa). Nie rozumiem dlaczego - policzyłem koszt największych zmiennych w programie, czyli vector<vector<int>>. Wielkość zewn. wektora to m elementów, czyli max 250*249 = 62 250 elementów (zakładając, że 1 vector zabiera 20 bajtów, to jest 1,25MB). Wielkość zawartych w wewn. vectorach intów chyba można pominąć (bo jest niezauważalnie mała?). Takich zmiennych jest w czasie działania programu maksymalnie 3 na raz, co daje niecałe 4MB. Dalej pozostaje ponad 28 MB na resztę zmiennych (raczej niewielkich - kolejki i stosy z niedużą ilością elementów, jednowymiarowe vectory) i inne dane. Problem z przekroczeniem pamięci napotkałem 2 raz w życiu, więc pewnie coś źle rozumiem / liczę. W jaki sposób się zabrać za szukanie przyczyny? Proszę o pomoc.
graf jest wystarczająco mały by się zmieścić poniżej <1MB, więc problem jest w ilości wszystkich możliwych dróg których może być bardzo dużo. Zrób równoczesne liczenie o którym wspomniałeś, to nie będziesz miał więcej niż 500 elementów na kolejce i cały algorytm zmieści w poniżej <1M.
i raczej Twoje rozwiązanie nie jest poprawne, pomyśl nad równoległym przechodzeniem wszerz, bez wyznaczania całych dróg, bez wykrywania cykli i bez eliminowania chodzenia wstecz ;)
W jaki sposób równoczesne liczenie zmniejszy ilość elementów w kolejce? Szczerze mówiąc wydawało mi się, że to rozwiązanie podwoi ilość zużywanej pamięci, w końcu będą potrzebne dwie kolejki na raz (po jednej na agenta - startują z różnych miejsc w grafie).
jedna kolejka dla dwóch agentów, na kolejce możesz mieć 250 miast dla 1 agenta i 250 miast dla 2 agenta, żadne dodatkowe kolejki i stosy nie są potrzebne.
Mógłbyś mi zarysować jak by to wyglądało w moim kodzie? Nie chcę nadużywać pomocy, ale nie rozumiem toku rozumowania (w jaki sposób zarezerwować 250 miejsc dla jednego, 250 dla drugiego wewnątrz jednej kolejki?).
Nie tyle rezerwować, co tyle by wynosił przypadek gdyśmy na kolejce trzymali trójki, zaczynamy z kolejki wyglądającej tak
(Agent1, miasto startowe 1, dzien 0)
(Agent2, miasto startowe 2, dzien 0)
zdejmujemy pierwszą trójkę, dodajemy na kolejkę nowe trójki
(Agent2, miasto startowe 2, dzien 0)
(Agent1, miasto osiągalne z miasta startowego 1, dzien 1)
(Agent1, miasto osiągalne z miasta startowego 2, dzien 1)
i znowu
(Agent1, miasto osiągalne z miasta startowego 1, dzien 1)
(Agent1, miasto osiągalne z miasta startowego 2, dzien 1)
(Agent2, miasto osiągalne z miasta startowego 1, dzien 1)
(Agent2, miasto osiągalne z miasta startowego 2, dzien 1)
(Agent2, miasto osiągalne z miasta startowego 3, dzien 1)
itd ...
w sumie widzę kolejne podejście z trzymaniem tylko numerów miast na kolejce (wtedy na kolejce maks będzie 250 miast), plus dodatkowo w miastach ostatniego dnia w którym dany agent odwiedził miasto.
tylko że ten algorytm który mam na myśli będzie miał złożoność O(n^4), a z tego co widzę to tu jednak trzeba będzie O(n^3) napisać.
Dzięki wielkie, sporo mi to wyjaśniło. Napisałem coś takiego (nie wykrywam cykli, nie eliminuję chodzenia wstecz):
https://4programmers.net/Pastebin/14670
Tak jak sugerowałeś, jest jedna kolejka i wrzucam dane w trójkach. Jest lepiej, bo dostałem punkty (19/100). W prawie wszystkich testach przekraczam limit czasu, ale w dwóch testach z max danymi też limit pamięci. Co do limitu czasu, to rozwiązanie jest nieoptymalne - czytałem opis rozwiązania optymalnego, które ma złożoność O(n^3), ale chciałem spróbować po swojemu. W tym opisie jest też napisane, że pomysł taki jak mój (czyli sprawdzanie, do których miast agenci mogą dotrzeć w kolejnych dniach) dla pewnych danych będzie równie wolny co O(n^4). Dziwi mnie jednak aż tak duża liczba testów niezaliczonych przez czas, no i te dwa niezaliczone przez pamięć. Czy dobrze rozumuję, że pamięć jest przekraczana ze względu na obecność w grafie cykli, przez co zapycham na stałe kolejkę pewnymi miastami, które należą do cyklu (cykli musiałoby być bardzo dużo, np. graf, w którym każda droga jest dwukierunkowa, czyli w zasadzie nieskierowany, ale innego wytłumaczenia nie mogę znaleźć)?
no powiedzmy że cykle powodują problem, a właściwie to kliki, czyli pod grafy w których każdy wierzchołek ma krawędzie do pozostałych wierzchołków w klice. I teraz korzystając z tablicy lastTimeVisited trzeba wyeliminować dodawanie na kolejkę trójek które już są na kolejce, czyli jeśli mamy drogę 1->3, 2->3, i nasz agent numer 1 może być dnia pierwszego w mieście 1 i 3, to na kolejkę tylko raz chcemy dodać trójkę (dzien 2, miasto 3, agent 1) a nie dwa razy.
Za rozwiązanie O(n^4) można dostać 72%, tyle dał mi ten kod:
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Miasto
{
int a1;
int a2;
vector<int> drogi;
};
int main()
{
Miasto miasta[256];
int n, m, a1, a2;
scanf("%d%d", &n, &m);
scanf("%d%d", &a1, &a2);
for (int i = 0; i <= n; ++i)
{
miasta[i].a1 = -2;
miasta[i].a2 = -3;
}
for (int i = 0; i < m; ++i)
{
int f, t;
scanf("%d%d", &f, &t);
miasta[f].drogi.push_back(t);
}
miasta[a1].a1 = 0;
miasta[a2].a2 = 0;
queue<int> q;
q.push(a1);
q.push(a2);
q.push(-1);
int dzien = 0;
while (dzien < 1600)
{
int top = q.front();
q.pop();
if (top == -1)
{
dzien++;
q.push(-1);
continue;
}
Miasto miasto = miasta[top];
if (miasto.a1 == miasto.a2)
{
printf("%d", miasto.a1);
return 0;
}
if (miasto.a1 >= dzien)
{
for (int i : miasto.drogi)
{
if (miasta[i].a1 <= dzien)
{
miasta[i].a1 = dzien + 1;
q.push(i);
}
}
}
if (miasto.a2 >= dzien)
{
for (int i : miasto.drogi)
{
if (miasta[i].a2 <= dzien)
{
miasta[i].a2 = dzien + 1;
q.push(i);
}
}
}
}
printf("NIE");
return 0;
}
Być może przyda się taki fakt:
jeśli istnieją dwa cykle, których długości są względnie pierwsze, i takie że do pierwszego się dotrze z obu pozycji startowych, a do drugiego się dotrze z pierwszego, to da się zrobić spotkanie.