Out of Memory dans l'algorithme A *

Question

Comme vous pouvez le voir, j'utilise la méthode de Dijkstra pour traverser les nœuds et Il fonctionne avec de petites entrées (pas petites mais petites par rapport à celles problématiques).

Mais quand il y a une très grosse entrée (comme un graphe de 5000 sommets avec 5 millions d'arêtes) j'obtiens une erreur std :: bad_alloc à la ligne où je pousse le vertex détecté dans la file d'attente prioritaire.

Comment puis-je surmonter cela?

int distance; 
    priority_queue<detectedVertex, vector<detectedVertex>, Compare> detectedVertices; 
    detectedVertex s(source, graph[source].strLineDist); 
    detectedVertices.push(s); 

    while (!detectedVertices.empty()) { 
     int ID=detectedVertices.top().ID; 
     int cost=detectedVertices.top().estimatedCost-graph[ID].strLineDist; 
     if(ID==destination) { 
      distance=cost; 
      break; 
     } 
     detectedVertices.pop(); 
     graph[ID].visited=true; 

     for(int i=0;i<graph[ID].adjList.size();i++) { 
      int adjID=graph[ID].adjList[i].v2; 
      int edgeWeight=graph[ID].adjList[i].weight; 
      if(!graph[adjID].visited) { 
       detectedVertex temp(adjID, cost+edgeWeight+graph[adjID].strLineDist); 
       detectedVertices.push(temp); //std::bad_alloc 
      } 
     } 
    } 

Mes struct dans le cas où quelqu'un se demande

struct Edge { 
    int v1; 
    int v2; 
    int weight; 

    Edge(int v1, int v2, int weight) { 
     this->v1 = v1; 
     this->v2 = v2; 
     this->weight = weight; 
    } 
}; 

struct Vertex { 
    int ID = 0; 
    vector<Edge> adjList; 
    bool visited = false; 
    int strLineDist = 0; 
}; 

struct detectedVertex { 
    int ID; 
    int estimatedCost; 

    detectedVertex(int ID, int estimatedCost) { 
     this->ID = ID; 
     this->estimatedCost = estimatedCost; 
    } 
}; 

Answer 1

Le problème est ici:

detectedVertex temp(adjID, cost+edgeWeight+graph[adjID].strLineDist);

detectedVertices.push(temp); //std::bad_alloc

vous êtes en train de pousser des sommets dans la file d'attente plusieurs fois, et cela ne devrait pas arriver avec Dijkstra. Si le noeud adjID a déjà été mis à jour (mais n'est pas encore visité), il est déjà dans la file d'attente. Puis vient un autre de ses "prédécesseurs" et le met à nouveau à jour, vous le repoussez dans la file d'attente. La file d'attente est alors surutilisée, en particulier pour un si gros graphique, il devrait exploser.

Ceci est pour le problème de l'explosion de la mémoire. D'un autre côté, je dois dire que cette implémentation de Dijkstra me semble erronée. Vous devez le réviser, à mon humble avis.