Migliorare il tempo di esecuzione di Larghezza Prima creazione della lista di ricerca e di adiacenza

Question

Migliorare il tempo di esecuzione di Larghezza Prima creazione della lista di ricerca e di adiacenza

#1 da (1 voti)

2

Viene fornita una matrice di numeri interi in cui tutti gli elementi sono compresi tra 0 e 9. Deve iniziare dalla 1a posizione e raggiungere la fine nel minimo numero di mosse tale che possiamo da un indice spostare 1 posizione indietro e avanti i.i i-1 e i + 1 e passare a qualsiasi indice avente lo stesso valore dell'indice i.
Limite di tempo: 1 secondo
Dimensione massima dell'input: 100000

Ho provato a risolvere questo problema utilizzando un approccio a percorso singolo a sorgente più corta usando la ricerca di ampiezza prima e sebbene BFS sia di per sé O (V + E) e funzioni nel tempo, la creazione della lista di adiacenze richiede tempo O (n2) e quindi complessità complessiva diventa O (n2). c'è un modo per diminuire la complessità temporale della creazione della lista di adiacenza? o c'è un modo migliore e più efficace per risolvere il problema?

int main(){

    vector<int> v;
    string str;
    vector<int> sets[10];

    cin>>str;
    int in;
    for(int i=0;i<str.length();i++){
        in=str[i]-'0';
        v.push_back(in);
        sets[in].push_back(i);
    }

    int n=v.size();
    if(n==1){
        cout<<"0\n";
        return 0;
    }
    if(v[0]==v[n-1]){
        cout<<"1\n";
        return 0;
    }


    vector<int> adj[100001];
    for(int i=0;i<10;i++){
        for(int j=0;j<sets[i].size();j++){
            if(sets[i][j]>0)
                adj[sets[i][j]].push_back(sets[i][j]-1);
            if(sets[i][j]<n-1)  
                adj[sets[i][j]].push_back(sets[i][j]+1);
            for(int k=j+1;k<sets[i].size();k++){
                if(abs(sets[i][j]-sets[i][k])!=1){
                    adj[sets[i][j]].push_back(sets[i][k]);
                    adj[sets[i][k]].push_back(sets[i][j]);
                }
            }
        }
    }

    queue<int> q;
    q.push(0);

    int dist[100001];
    bool visited[100001]={false};
    dist[0]=0;
    visited[0]=true;

    int c=0;
    while(!q.empty()){
        int dq=q.front();
        q.pop();
        c++;

        for(int i=0;i<adj[dq].size();i++){
            if(visited[adj[dq][i]]==false){
                dist[adj[dq][i]]=dist[dq]+1;
                visited[adj[dq][i]]=true;
                q.push(adj[dq][i]);
            }
        }

    }

    cout<<dist[n-1]<<"\n";

    return 0;
}

c++ array graph graph-traversal

posta user45957 09.06.2014 - 19:49

fonte

1 risposta

Leggi altre domande sui tag c++ array graph graph-traversal

Utilizzo del software AGPL su server con software closed-source Come faccio a distinguere tra vecchi e nuovi dati nelle raccolte backbone?

score 1 · Accepted Answer

Informazioni chiave: non è necessario costruire in modo avido l'elenco di adiacenze. In realtà, non è necessario costruire mai la lista di adiacenza; hai solo bisogno di un modo per trovare i nodi successivi. Con questa intuizione, possiamo costruire una versione efficiente della ricerca.

Bordi pigri

Per ogni dato nodo, trovare indici i + 1 e i-1 è banale. La ricerca di nodi con lo stesso valore richiede semplicemente una ricerca nella struttura di sets che hai già creato.

Il resto della tua ricerca per ampiezza si applica ugualmente; contrassegni i nodi che hai già visto per assicurarti di non rivederli.

Valori raggruppati

Nota che non c'è davvero alcun motivo per tornare a un valore una volta che lo hai lasciato. Qualsiasi percorso che raggiunge un indice con valore X può raggiungere qualsiasi altro indice con valore X nel passaggio successivo. Ciò significa che il tuo percorso massimo è 19 (ogni valore può verificarsi al massimo due volte per 20 nodi, ovvero 19 spigoli lungo il percorso).

Tuttavia, significa anche che non vuoi che si verifichi quanto segue:

sei nell'indice K con valore X, e itera su tutti gli altri indici con valore X, contrassegnandoli come visitati e aggiungendoli alla coda
alla fine raggiungi ognuno di quegli indici con valore X nella coda, e itera su tutto ciò che può raggiungere, cioè tutte quelle altre X - anche se sono state tutte visitate e sai già che non stai andando per aggiungerli alla coda.

Quindi stai facendo un lavoro quadratico (ogni istanza di un valore itera su ogni istanza dello stesso valore) ed è ovviamente inutile da avviare. Una volta che hai elaborato un indice con valore X e quindi visiti tutte le altre X, conosci non dovrai mai più seguire un margine X- > X. Soluzione facile? Basta svuotare l'elenco di indici di quel valore dopo averne elaborato uno.

Questo nuovo algoritmo è tempo lineare:

la lettura dell'ingresso è lineare
building sets è lineare (ogni indice viene inserito una volta)
ogni indice può essere "elaborato" (aggiunto alla coda) al massimo una volta, quindi è lineare.
ogni indice può essere "visitato" (controllando l'array visitato) al massimo tre volte: una volta da i-1, una volta da 1 + 1, e una volta da qualche altro indice con valore identico.

Se vuoi davvero, puoi eliminare un po 'del fattore costante qui. Dopo tutto, il percorso finale passerà attraverso ogni valore una volta (e quando lo farà, toccando uno o due indici per quel valore). È quindi possibile costruire un grafico molto più piccolo di come i valori possono raggiungere l'altro; risolverlo per i percorsi più brevi è essenzialmente gratuito (al massimo 10 nodi, dopotutto), e un percorso più breve attraverso gli indici deve essere il percorso più breve tra i valori (prova lasciata al lettore, ma nota che qualsiasi scorciatoia tramite i + 1 / i-1 costa almeno un passo, ma non può mai vincere più di un passo). Quindi, quando si risolve il grafico più grande degli indici, non è necessario preoccuparsi di intraprendere azioni in conflitto con ciò che già si conosce della soluzione; Ad esempio, non accodare alcun indice che abbia un valore diverso dal proprio o dal valore "successivo" lungo un percorso più breve nel grafico del valore. (In sostanza, questa ottimizzazione è A *).

Allo stesso modo, puoi segmentare la tua coda in base al valore e alla distanza e saltare l'elaborazione del resto del valore corrente con una distanza maggiore una volta trovata la strada per il prossimo.

Tale inganno è quasi certamente non ne vale la pena, ma hey, è possibile: -).

Stile di codifica: ti suggerisco di denominare le tue variabili dopo quello che rappresentano. Il tuo codice è un po 'difficile da seguire perché contiene cose come sets (di cosa? Perché? - oh è un modo per cercare indici aventi un valore), e una coda q (ancora, cosa significa? Oh è l'insieme raggiungibile in ordine di distanza). Dai concetti significativi (che ripeti nel codice) come adj[dq][i] un nome. È il vicino che visiterai. Questo algoritmo è così semplice, alla fine è chiaro, ma non c'è ragione per cui non dovrebbe essere chiaro subito.

TL; DR

Non precalcolare i bordi, calcola invece la raggiungibilità quando necessario.
Svuota il set di indici che utilizzi per calcolare la raggiungibilità valore-valore dopo averlo usato una sola volta per evitare il comportamento quadratico.
Il risultato è O (N).