Speicherleck bei A* Implementierung, vermutlich im Heap

Salix

Hallo,

ich versuche gerade einen A* Algo zu implemetieren und habe mich weitestgehend an diesen Artikel gehalten: http://www.student.nada.kth.se/~f93-maj/pathfinder/4.html#2.6

Der Autor nutzt als PriorityQueue einen Fibonacci Heap und verwendet folgende Implementierung:
http://web.mit.edu/cocosci/isomap/code/fibheap.h
http://web.mit.edu/cocosci/isomap/code/dijkstra.cpp
Die cpp ist im wesentlichen die fibheap.cpp - nur, dass unten noch ein Dijstra dranhängt, der hier aber uninteressant ist.

Ich habe mal versucht, das Problem auf das Wesentliche zu reduzieren und lasse den Großteil des A* einfach mal weg. Dazu habe ich mel eine Testfunktion gebaut, in der ich den Heap analog zum Verlauf des Suchalgos fülle und leere. Der dabei allozierte Speicher wird leider nicht wieder freigegeben und ich weiß momentan nicht weiter...

void test()
{
	FibHeap PQ;
	HeapNode* p;
	for (int i=0; i<8000;i++)
	{
		for(int j=100;j>0;j--)
		{
		p=new HeapNode;
		p->x=i;
		p->g=i*j;
		p->h=9999999/(j+1);
		PQ.Insert(p);	
		}
	}

	while((p = (HeapNode*)PQ.ExtractMin()) !=NULL)
	{
		//jeweils kleinsten Knoten vom Heap genommen

	}
	delete p;
}

HeapNode ist analog zur dijkstra.cpp eine von FibHeapNode abgeleitete Klasse, nur dass ich int x und float g,h als Member habe und die Operatoren entsprechend angpasst habe.

Ich hoffe, dass das Problem halbwegs deutlich wird und jemand eine Idee hat...

Christoph

Du rufst 800000 Mal new auf, aber nur ein einziges Mal delete. Das delete musst du fuer jeden HeapNode einzeln aufrufen.

Salix

besten Dank!

nachdem ich deinen Hinweis heute Mittag gelesen habe, habe ich mir meinen geposteten Code nochmal genau angeguckt und mit dem eigentlichen Algorithmus verglichen - und siehe da, es war wirklich identisch und ein kleines delete in der Schleife hat es gebracht