Problem mit A* Wegsuchsalgorithmus

Wenn es effizient sein soll, musst du dir wohl eine eigene Heap Klasse implementieren. Du kannst die std::push_heap() , std::pop_heap() Funktionen verwenden und musst noch eine Funktion schreiben, mit der du den Wert eines Eintrags im Heap ändern kannst. Das lässt sich noch ein wenig effizienter schreiben, als einer Entfernen gefolgt von ein Einfügen-Operation.

Falls du es ganz effizient haben willst, kannst du auch einen Fibbonacci-Heap implementieren.

*Q* 1

Heap selbst implementieren ist mir (zumindest erstmal) zuviel aufwand, ich versuchs erstmal mit nem set, bring es zum laufen und guck obs schnell genug läuft und wenn nicht such ich erstmal nach dem bottleneck und nur falls es dann wirklich die OpenList ist guck ich nochmal in Richtung Heaps

Edit: Hab mir gerade doch nochmal die heap-algorithmen angeguckt, ist dann wohl doch nicht soviel aufwand, vll benutz ich doch den heap.

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Welche DecreaseKey-Operation? Ruf einfach makeHeap auf, wenn du
Elemente in der PQ geändert hast.

knivil

make_heap: At most, (3*(last-first)) comparisons.

Ich sage mal O(n). Eine set mit Einfuegen/Loeschen ist aber O(log n).

*Q* 1

Dann bleib ich wohl doch beim set, außer wenn wer nen guten Vorschlag hat.

DecreaseKey soll heißen, dass ein element so verändert wird, dass er in der priority_queue früher drankommt als vorher.

Jedes element bei mir hat eine rating.
Je niedriger, desto früher wirds abgearbeitet.
Hin und wieder muss ich die Rating eines Elements verringern.

knivil schrieb:

make_heap: At most, (3*(last-first)) comparisons.
Ich sage mal O(n). Eine set mit Einfuegen/Loeschen ist aber O(log n).

Ein Heap lässt sich auch so implementieren, dass beliebige Elemente in O(log n) entfernt werden können. Ein Heap ist nur im Allgemeinen schneller als ein set (um einen konstanten Faktor). Das geht natürlich nur, wenn man weis, wo sich das entsprechende Element im Moment im Heap befindet.

Q schrieb:

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Wenn du die irgendwo gefunden hast, dann wird die schon in Ordnung sein. Es ging mir nur darum, zu erwähnen, dass es besser geht, als entfernen und einfügen. Eben mit einer decreaseKey -Funktion. Man kann auch relativ einfach eine changeKey -Funktion bauen.

Heaps sind btw. hier recht gut erklärt:
Introduction to Algorithms | ISBN: 9780262033848

*Q* 1

ProgChild schrieb:

Q schrieb:

Wie kriegt man denn dabei die decreaseKey-Operation gut hin?

Wenn du die irgendwo gefunden hast, dann wird die schon in Ordnung sein. Es ging mir nur darum, zu erwähnen, dass es besser geht, als entfernen und einfügen. Eben mit einer decreaseKey -Funktion. Man kann auch relativ einfach eine changeKey -Funktion bauen.

Ich habe ja keine gefunden, sondern will eine basteln

*Q* 1

Jetzt hab ich folgendes Problem:

struct NodeComparator
	{
		bool operator()(const Node* lhs, const Node* rhs) const
		{
			if(lhs->GetRating() < rhs->GetRating())
				return true;
			if(lhs->pos.x < rhs->pos.x)
				return true;
			return lhs->pos.y < rhs->pos.y;
		}
	};

	typedef std::set<Node*, NodeComparator> OpenList;

Debug Assertion Failed!
Expression: invalid operator<

Was ist denn falsch an meinem Comparator?

Th69

Hallo Q,

du willst ja nur die Positionen vergleichen, wenn dein Rating gleich ist (und daselbe dann für dein pos.x und pos.y):

struct NodeComparator
    {
        bool operator()(const Node* lhs, const Node* rhs) const
        {
            if(lhs->GetRating() < rhs->GetRating())
                return true;
            else if(lhs->GetRating() > rhs->GetRating())
                return false;

            if(lhs->pos.x < rhs->pos.x)
                return true;
            else if(lhs->pos.x > rhs->pos.x)
                return false;

            return lhs->pos.y < rhs->pos.y;
        }
    };

*Q* 1

Danke! Jetzt funktionierts!
Hab std::set statt priority_queue verwendet.

Edit: Irgendwo ist nocjh nen fehler, gerade wurde ein ungültiger Pfad mit sprüngen drin gefunden.
Edit2: Ups ich glaube, die Sprünge hab ich nur gesehen, weil die Konsole Zeilenumbrüche reingemacht hat Bin mir aber nicht ganz sicher.

Q schrieb:

Ich habe ja keine gefunden, sondern will eine basteln

Ach so. Dann habe ich dich falsch verstanden.

Angenommen bei deinem Heap ist immer das Minimum die Wurzel. Wenn du jetzt den Schlüssel von einem Element verminderst, dann muss dieses Element im Binärbaum so weit nach oben geschoben werden, bis der Schlüssel seiner Söhne größer sind, als es selbst. Dazu immer mit dem Vater-Knoten vergleichen und falls die Eigenschaft noch nicht erfüllt ist, die Knoten vertauschen. Das gleiche dann mit der neuen Position wiederholen, usw.

Mehr Details müsstest du in entsprechender Literatur nachlesen.