Design-Ideen gesucht

pli

otze schrieb:

Was sind ungefärbte/gefärbte Knoten? den begriff hör ich jetzt zum ersten mal.

Faerbbarkeit eines Graphen, ist ein NP-schweres (glaub ich) Problem der Algorithmik. 2 benachbarte Knoten duerfen nicht die gleiche Farbe haben.
Anwendung: politische Landkarten, benachbarte Laender duerfen nicht die gleiche Farbe haben und die Anzahl der Farben soll minimal sein.

pli

Als Datentyp fuer deine Knoten, nimm doch einfach eine Priority Queue (ist sogar in der STL meines Wissens) mit deiner Bewertung als Referenzwert, so steht der beste Wert immer am Kopf der Queue.

Denke hier kannst du sehr viele Infos zu deinem Problem finden:
http://www.algo.informatik.tu-darmstadt.de/ Unter Lehre->WS04/05->Effiziente Graphenalgorithmen, stehen auch die Laufzeiten fuer die verschiedenen Operationen drin

HumeSikkins

pli schrieb:

Als Datentyp fuer deine Knoten, nimm doch einfach eine Priority Queue (ist sogar in der STL meines Wissens) mit deiner Bewertung als Referenzwert, so steht der beste Wert immer am Kopf der Queue.

Eine Priority-Queue kann ich nur für Fall 1 benutzen. Für die anderen Fälle funktioniert ein Priority-Queue nicht. Für Fall 1 hat eine Priority-Queue allerdings genau die gleichen Nachteile wie eine set. Sprich: Ich muss die Knoten doppelt speichern. Allein schon, weil man durch eine PQ weder iterieren kann noch an beliebigen Stellen löschen. Beides sind aber Operationen die ich brauche.

Denke hier kannst du sehr viele Infos zu deinem Problem finden:
http://www.algo.informatik.tu-darmstadt.de/ Unter Lehre->WS04/05->Effiziente Graphenalgorithmen, stehen auch die Laufzeiten fuer die verschiedenen Operationen drin

Wie helfen mir Graphenalgorithmen in dieser Situation? Ich bin auch stolzer Besitzer von Sedgewicks "Algorithms in C++ - Part 5 Graph Algorithms". Aber keiner der dort beschriebenen Algorithmen löst meine derzeitige Situation, da diese eigentlich wenig mit klassischen Graphen zu tun hat.

Trotzdem schonmal danke für die Anregungen.

Was sind ungefärbte/gefärbte Knoten? den begriff hör ich jetzt zum ersten mal.

Ist in diesem Kontext nicht wichtig. Wichtig ist nur, dass ich eine Menge von Knoten habe, die ein bestimmtes Attribut besitzen. Der Wert des Attribut verändert sich laufend.

Wen's interessiert: Das Anwendungsgebiet ist die Berechnung von Antwortmengen (auch stable models gennat). Die Knoten sind Teil eines Body-Head-Graphens, der die Abhängigkeiten der Regeln eines Logischen Programms beschreibt. Ungefärbte Knoten sind Choice-Point-Kandidaten sowie Kandidaten für Lookahead-Operatoren.
Aber das ist für mein konkretes Problem eigentlich alles nicht relevant.

otze

Gut. hab mir jetzt was überlegt:

ich hab hier was für den ersten Fall, ich setz hierbei voraus, dass UncoloredNodesBase ein public typedef auf Iterator hat:

template <class Impl>
class StaticHeuristic {
public:
    typedef typename Impl::Compare_Type CompareType;
    typedef typename Impl::Evaluate_Type EvaluateType;
    typedef UncoloredNodesBase::Iterator Iter;

    void stable(Iter begin, Iter end) {
        for_each(Node* n in [begin, end]){
            evaluator_(n);  // bewerten
        }
        bestNode=max_element(begin, end, CompareType());
        this->begin=begin;
        this->end=end;
    }
    template <class Iter>
    Node* getBestNode(Iter, Iter) const {return bestNode}

    void addNode(Node* n) {
        evaluator_(n);
        if(n->getVal()>bestNode->getVal()){
            bestNode=n;
        }
    }
    void removeNode(Node* n) {
        if(n==bestNode){
             bestNode=max_element(begin, end, CompareType());
        }
    }
private:
    Iter begin;
    Iter end;
    Node* bestNode;
    EvaluateType evaluator_;
};

HumeSikkins

Sehr schön!

Hat aber noch ein kleines Problem: Der Iterator begin kann ungültig werden. Kann man aber recht einfach lösen, in dem man removeNode neben dem Knoten auch noch die beiden Iteratoren die die Sequenz markieren mitgibt. end bleibt zwar stabil und man könnte deshalb auf die Übergabe verzichten. Aber von der Logik wäre es imo einfacher.

Hat sich ja schon gelohnt, dass ich hier gefragt habe. Danke!

HumeSikkins

Zu früh gefreut

Da die Auswahl des Besten Knotens immer auch dazu führt, dass dieser aus der Menge entfernt wird, hat deine Lösung für die Auswahl des Besten Knotens ein Laufzeitverhalten von O(n). Was ich ja gerade verhindern wollte

otze

das bedeuted, dass irgendwo in deinem programm ein

Node& n=SR_Heu.getBestNode();
SR_Heu.removeNode(&n);

steht?

das ist natürlich bitter...

vielleicht hilft ja ein zwischending aus deiner und meiner lösung?

das man zb nur die besten 5/10/15 nodes in einem set speichert.
müsstest dann halt nichtmehr alles doppelt speichern, hast aber immer einen puffer.

HumeSikkins

otze schrieb:

das bedeuted, dass irgendwo in deinem programm ein
Node& n=SR_Heu.getBestNode();
SR_Heu.removeNode(&n);
steht?

Zumindest vom Effekt her, ja. Der Tatsächliche Code ist natürlich komplizierter

das man zb nur die besten 5/10/15 nodes in einem set speichert

Daran habe ich auch schon gedacht.

Das blöde ist: Das Problem ließe sich trivial lösen, wenn es sowas wie virtuelle Template-Funktionen gäbe. Kluge Leute haben mir aber erklärt, dass ein Design, das virtuelle Template-Funktionen braucht einen Design-Fehler enthält. Dumm nur, dass ich diesen nicht finde

otze

Das blöde ist: Das Problem ließe sich trivial lösen, wenn es sowas wie virtuelle Template-Funktionen gäbe

sorry, ich komm nicht drauf, wie soll das hier helfen? haben die nodes eine bestimmte Eigenschaft, auf die du dann zurückgreifen kannst?

HumeSikkins

sorry, ich komm nicht drauf, wie soll das hier helfen?

Was ich brauche ist eine Möglichkeit wie ich
begin- und end so implementieren kann, dass der Iterator-Typ variable ist ohne das er dazu polymorph sein muss.
Dann könnte ich das Problem effizient lösen. Fall 1 würde die Knoten in einer set speichern und begin und end würde set::iteratoren liefern. Fall 2 und Fall 3 würden die Knoten in einer hash_set speichern und hash_set::iteratoren liefern.
Verwendet man nun internal- statt external-Iteratoren könnte man das Ganze mit virtuellen Templates so lösen:

class UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) = 0;
};

class Static : public UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) {
		for_each(s_.begin(), s_.end(), p);
	}
private:
	set<Node*> s_;
};

class Dynamic : public UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) {
		for_each(s_.begin(), s_.end(), p);
	}
private:
	hash_set<Node*> s_;
};

Ohne virtuelle Templates muss P ein polymorpher Typ sein. Das wäre dann aber Geschwindigkeitstechnisch das selbe wie ein polymorpher Iterator.