Cum rezolv algoritmul asta de grafuri in timp polinomial?

[drealecs]

Salutare.

Acum cateva luni m-am chinuit cu un algoritm pentru un bot de foursquare.

4sq-ul e mai putin interesant aici pentru ca am scris problema mai dragut asa:

http://www.evernote.com/shard/s119/sh/79f47a65-c1e6-44da-bbc0-7d10e36c7f71/374eda2f355c9a18d41ea19a20866fbc

Pana la urma eu am rezolvat problema mea cu optimizari de rahat si limitand numarul de puncte la cele mai probabile/importante.

Bot-ul il scriu in java dar algoritmul (daca e posibil) ma intereseaza mai mult ca idee.

[cmiN]

Solutia naiva ar fi sa faci un backtracking pe parcurgeri in adancime si la depasirea timpului sa actualizezi maximul, oricum iese cu mult din timp.

O solutie mai buna ar fi o dinamica in T*N unde D[j] pastreaza cele mai bune rezultate ale vecinilor lui j plecand de la momentul de timp i. Toate bune si frumoase pana a aparut problema in care trebuie sa-ti dai seama daca ai mai vizitat sau nu vecinul k al lui j in lantul i (corespunzator momentului de timp) si ca sa faci asta trebuie sa mai faci inca i-1 verificari ceea ce ducea la un timp T!*N si memorie T*N. Asa ca m-am gandit sa memorez fiecare configuratie/drum/lant in functie de fiecare moment de timp dependent de nodul cu pricina si ajungeam la un timp mai bun T*N^2 dar memoria ajungea si ea la fel, iar la datele din problema in cel mai rau caz la 600 de noduri se ocupau cam 5 gb in ram asa ca am limitat nodurile la 100 si avem memoria maxima de 200mb (cam mare) dar timpul maxim de 5 sutimi .

Multumesc lui bylosul93 pentru inspiratie si acum codul:

Ideone.com | Online C++ Compiler & Debugging Tool

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;




const int T = 5001, N = 101;
int maxMoney, startNode, nodes, edges, time, win[N], mat[T][N][N];
vector<vector<pair<int, int> > > adjacent;




void parse_input()
{
    cin >> nodes >> edges >> startNode >> time;
    for (int i = 1; i <= nodes; ++i) cin >> win[i]; // money gain for node i
    adjacent.resize(nodes + 1);
    for (int i = 0; i < edges; ++i) {
        int t, x, y;
        cin >> t >> x >> y; // t time between x and y
        adjacent[x].push_back(make_pair(y, t));
        adjacent[y].push_back(make_pair(x, t));
    }
}




void solve()
{
    /** O(TN^2) */
    maxMoney = win[startNode]; // atribuim maximului castigul de start
    mat[0][startNode][0] = maxMoney; // la momentul de timp t=0 initializam nodul de start
    mat[0][startNode][startNode] = 1; // marcam ca este vizitat in lantul curent
    for (int i = 0; i < time; ++i) { // pentru fiecare moment de timp
        for (int j = 1; j <= nodes; ++j) { // luam fiecare nod
            if (mat[i][j][0]) { // si daca s-a putut ajunge in el (avand suma strict pozitiva)
                for (int k = 0; k < adjacent[j].size(); ++k) { // luam fiecare vecin al lui
                    int tmpTime = i + adjacent[j][k].second; // aflam noul timp pentru vizita vecinului
                    int tmpMoney = mat[i][j][0]; // clonam suma de la care pornim vizita
                    if (!mat[i][j][adjacent[j][k].first]) { // daca nu a mai fost vizitat acel vecin
                        tmpMoney += win[adjacent[j][k].first]; // actualizam suma
                    } // apoi daca vizita intra in timp si obtinem o suma mai buna de bani
                    if (tmpTime <= time && tmpMoney > mat[tmpTime][adjacent[j][k].first][0]) {
                        if (tmpMoney > maxMoney) maxMoney = tmpMoney; // actualizam maximul
                        mat[tmpTime][adjacent[j][k].first][0] = tmpMoney; // evenimentul in matrice
                        for (int l = 1; l <= nodes; ++l) { // dar si lantul de noduri vizitate
                            mat[tmpTime][adjacent[j][k].first][l] = mat[i][j][l];
                            mat[tmpTime][adjacent[j][k].first][adjacent[j][k].first] = 1;
                        }
                    }
                }
            }
        }
    }
}




int main()
{
    freopen("dp_graf.in", "rt", stdin); // switch input source
    parse_input();
    solve();
    cout << maxMoney;
    return 0;
}

Mai merge scazut si din T, oricum in implementarea ta nu cred ca folosesti dimensiuni asa mari.

Edited December 14, 2011 by cmiN

[drealecs]

Nu ma asteptam, si inca nu ma astept, ca-s putin pesimist.

Ma uit si-ti zic daca rezultatul este cum ar trebui. Si daca suna bine o scriu si-n java imediat si-o testez cu date reale.

Sa ma trezesc mai intai cu cafea ca sunt adormit de-n 5 minute alunecam in pat.

Morning edit:

N-am reusit sa ma trezesc bine

Din pacate nu cred ca e buna rezolvarea.

1. Imi trebuie path-ul, nu maximul. E un algoritm de pathfinding pana la urma.

2. Graful este complet. Din orice punct se poate ajunge in alt punct si timpul dintre ele este optim (adica nu se micsoreaza daca trece printr-n punct intermediar.) - ca mai ai un if in plus acolo.

3. Implementarea cu fiecare moment de timp este interesanta. O sa ma gandesc daca ma ajuta in alte parti. Timpul il folosesc la microsecunde aici dar as putea-l tai chiar si la zeci de secunda. Ideea este ca aici erau doar niste cuantificari direct proportionale. Daca ar fi sa vorbim de date reale, fie ele chiar si trunchiate la secunda, Txy este intre 1500 si 3500 iar T este undeva pe la 50000 - 60000. Ca si complexitate ar trebui sa depinda de T/avg(Txy) care in realitate o sa fie intre 25 si 30... modific si enuntul problemei acum.

N-ul nu l-as limita mai jos de 256 dar ma descurc eu cu memoria

Inca sunt de parere ca n-ar functiona...

Pentru a genera datele care sa fie compatibile cu problema, genereaza niste puncte pe o harta (patrata sa zicem): (x,y) unde x si y sunt float random intre 0 si 200 si functia de timp intre puncte o consideram simpla:

float time(p1, p2){
    float distance = sqrt((p1.x-p2.x)^2 + (p1.y-p2.y)^2);
    return 80 + min ( (40 + distance / 4), (distance / 2) );
}

Txy intre 80 si 200

T considera-l fix : 4000

N ramane... 200

[cmiN]

Pai poate fi adaptat usor de la int la float, iar generarea drumului si mai simplu. Acolo in if-ul in care se seteaza maximul se adauga 2 paranteze acolada si pe langa setarea maximului se mai pune intr-un vector lantul respectiv, cu conditia ca lantul sa-si modifice semnificatia, adica mat[j][l] sa nu mai fie 1 (adica nod vizitat) ci un indice, tot un numar pozitiv care sa se incrementeze odata cu adaugarea de noi noduri.

Algoritmul functioneaza foarte bine si da optimul pe diferite cazuri destul de suspecte, tinand cont de datele problemei, iar de la enuntul ei la necesitatea ta nu e deloc cale lunga .. ci cateva modificari la tipul de date si adaugarea unei linii de cod. Cu memoria scapi de probleme ... o aloci dinamic in java daca e, oricum totul depinde de o constanta.

Cat despre if-ul ala de care ziceai tu cu referire la enuntul problemei ca fiecare muchie este optima e mai mult o pseudoeuristica pentru alte tipuri de abordari ale problemei. Eu am nevoie neaparat de if-ul ala (banuiesc ca te referi acolo cand verific timpul si suma de bani) ca sa decid daca actualizez cu noua valoare in matrice sau nu. Timpul se refera la depasirea limitei maxime, nu daca gasesc vreun timp mai bun, practic nici nu ma intereseaza ce timp am, ma intereseaza sa stiu daca incape in limita ca sa trec noul rezultat al noii sume de bani daca merita. Si cum nu pot alege intre o pereche timp_bun-suma_mica si timp_prost-suma_mare a iesit dinamica asta.