classe abstraite et héritage - pathfinding avec A*

Version imprimable

bonjour à tous,

j'aimerais pouvoir faire quelque chose comme ça:
(j'ai une erreur de compilation sur cet exemple)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Node{ public: int f; }; class Graph{ public: virtual vector<Node*> getNeighbors(Node* from) = 0; virtual int getCost(Node* from, Node* to) = 0; }; class myNode : public Node{ public: int x, y, cost; }; class myGraph : public Graph{ public: vector<myNode*> getNeighbors(myNode* from); int getCost(myNode* from, myNode* to); private: vector<myNode*> map; };
Si je faisais avec template<typename T> sur graphe, je pourrais remplacer les Node par n'importe quoi. Et je veux qu'on ne puisse le faire qu'avec un Node ou un fils de Node uniquement.

Comment puis je faire ça?

merci pour votre réponse :).

25/08/2007, 19h53
poukill

Citation:

Envoyé par cyril_sy

Si je faisais avec template<typename T> sur graphe, je pourrais remplacer les Node par n'importe quoi. Et je veux qu'on ne puisse le faire qu'avec un Node ou un fils de Node uniquement.

Comment puis je faire ça?

merci pour votre réponse :).

Moi je verrai une classe de trait, ou tu ne définirais l'implémentation que pour les types qui ont un sens. Après, ceux qui utiliseraient ta classe avec un autre T n'auraient rien...

Il doit surement y avoir une meilleure méthode... Je cherche... :koi:

PS. : Ou sont les erreurs de compilation ?
25/08/2007, 20h12
cyril_sy

Les erreurs apparaissent au moment ou j'instancie myGraph:

error: cannot declare variable 'graph' to be of type 'myGraph'
error: because the following virtual functions are abstract:

Il me sort toutes les fonction virtuelles.
Ca parait normal, car pour lui

int getCost(myNode* from, myNode* to);

n'implémente pas

virtual int getCost(Node* from, Node* to) = 0;
25/08/2007, 20h13
MatRem
En fait je ne vois pas vraiment ton problème, si tu fais une bonne interface virtuelle pour Node, tu devrais pouvoir gérer ça il me semble...

Avec quelquechose comme ça (à améliorer bien sur) :
Code:

1 2 3 4 5 6 7 class Node { public: virtual std::vector<Node *> getChilds() = 0; virtual Node * getParent() = 0; };
Il te suffit ensuite juste d'utiliser l'héritage, pour définir des classes concrètes, et tu peux ainsi naviguer dans ton graphe de ta classe à partir d'un Node & (ou *). D'ailleurs dans ce cas un Node est déjà un graphe.

C'est effectivement aussi possible avec les templates, tu ne pourras pas obliger d'avoir des classes dérivant de Node, mais les classes devront quand même respecter une interface.
25/08/2007, 20h15
MatRem

Il te suffit d'implémenter le getCost dans MyGraph avec des Node * et non des MyNode *.
25/08/2007, 20h17
cyril_sy

oui, mais pour connaitre cost par exemple, j'ai besoin d'un myNode. Je ne peux pas le connaitre à partir de Node...
25/08/2007, 20h18
MatRem

A mon avis il faudrait que ce soit Node qui soit une classe virtuelle.
25/08/2007, 21h32
cyril_sy

Bein s'en est presque une aussi, sauf qu'elle ne contient pas de fonctions.

En fait je suis en train de faire un "path finder". Il prend en argument un Graph et effectue certaines opérations sur des Node.

Ce que j'aimerais c'est laisser à l'utilisateur un moyen de definir son graphe comme il l'entend.

Je lui propose de deriver une classe Node et une classe Graphe. Les 2 ont une interface qui sert au path finder.

Si vous avez une autre solution je prend aussi :D, et merci pour vos réponses

Voilà un exemple d'autre solution ;) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
#ifndef GRAPH_NODE_HPP
#define GRAPH_NODE_HPP
 
#include <map>
#include <vector>
#include <iostream>
 
 
namespace graph
{
 
template<typename Value, typename Cost = long >
class Node
{
public:
	typedef typename std::map<Node *, Cost>    container;
	typedef typename container::iterator       iterator;
	typedef typename container::const_iterator const_iterator;
 
	Node(Value const & val)
	:value(val)
	{}
 
	virtual ~Node()
	{
		iterator it = _childs.begin();
		while(it != _childs.end()) delete (it++)->first;
	}
 
	Node * createChild (Value const value, Cost const & cost)
	{
		Node * node = new Node(value);
		_childs.insert(std::make_pair(node, cost));
		return node;
	}
 
	container const & getChilds() const
	{
		return _childs;
	}
 
	Value value;
 
private:
	container _childs;
};
 
template<typename Value, typename Cost>
void print_node(std::ostream & stream, Node<Value, Cost> const * const node, long tabs)
{
	stream << node->value << std::endl;
 
	typename Node<Value, Cost>::const_iterator it = node->getChilds().begin();
	while(it!=node->getChilds().end())
	{
		stream << std::string(tabs+1,  '\t') << "(" << it->second << ") => ";
		print_node(stream, it->first, tabs+1);
		it++;
	}
}
 
}
 
 
template<typename Value, typename Cost>
std::ostream & operator << (std::ostream & stream, graph::Node<Value, Cost> const & node)
{
 
	stream << "Graph : " << std::endl;	
	graph::print_node(stream, &node, 0);
 
	return stream;
}
 
#endif

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <Node.hpp>
#include <string>
 
using namespace std;
using namespace graph;
 
 
int main()
{
	typedef Node<string> Node;
	Node graph("root");
	Node * node1 = graph.createChild("Child1", 10);
	graph.createChild("Child2", 5);
 
	node1->createChild("Child11", 23);
 
	cout << graph << endl;
}

Ça peut être amélioré en donnant la possiblité de gérer le type de conteneur, et en donnant l'accès au cout en ecriture, mais ça fait déjà une base pour implémenter un algo a* sur un Node.

26/08/2007, 12h55
cyril_sy

Merci, ton exemple est très interessant :D.

Mais ton Node prend beaucoup de place en mémoire non?

Dans mon cas par exemple, le graphe est une image, disons 500*500px, ça fait 250 000 nodes quand même. Surtout que dans ce cas, les child sont liés de manière logique.

C'est pour cette raison que j'aimerais laisser à l'utilisateur, le soin de définir complètement sont système de graphe.
26/08/2007, 13h18
MatRem

Citation:

Mais ton Node prend beaucoup de place en mémoire non?

A priori pas beaucoup plus que prendraient des données brutes...
Il y a juste l'utilisation d'une map pour les _childs qui prend un peu plus de mémoire.
D'ailleurs on pourrait améliorer Node en utilisant une multi_map avec cost comme clef. Ainsi, les childs serait déjà trié.

Citation:

C'est pour cette raison que j'aimerais laisser à l'utilisateur, le soin de définir complètement sont système de graphe.

En quoi voudrait tu laisser l'utilisateur plus libre? Si c'est juste pour une question de place en mémoire, je ne crois pas que ça soit vraiment intéréssant.

Pour laisser l'utilisateur plus libre, par contre, on peut paramétriser le conteneur, son allocateur, et sa fonction de tri (par template).

Citation:

Envoyé par cyril_sy

Bein s'en est presque une aussi, sauf qu'elle ne contient pas de fonctions.

En fait je suis en train de faire un "path finder". Il prend en argument un Graph et effectue certaines opérations sur des Node.

Ce que j'aimerais c'est laisser à l'utilisateur un moyen de definir son graphe comme il l'entend.

Je lui propose de deriver une classe Node et une classe Graphe. Les 2 ont une interface qui sert au path finder.

Si vous avez une autre solution je prend aussi :D, et merci pour vos réponses

Moi j'ai fait ça il y a justement quelques jours, pour l'algorithme A*.

J'ai défini une fonction template qui prend en argument :

- un graphe
- une fonction ou foncteur qui permet d'obtenir la liste des successeurs d'un noeud, qui prend en argument, un graphe, un sommet, et un insert_iterator afin de donner les successeurs, car je voulais pas imposer un conteneur quelconque
- un noeud de départ et d'arrivée
- une fonction qui compare les couts de 2 noeuds
- l'élément neutre de l'unité des coûts (au cas où quelqu'un utiliserait autre chose que des int/float/double pour les couts, un peu comme std::accumulate fait)
- un insert_iterator pour avoir la réponse

En sachant que cette fonction a ses types paramétrés comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 template < typename Graph, typename SuccessorInserter, typename Node, typename BinaryOperator, typename CostType, typename InsertIterator > void a_star(Graph const& graph, SuccessorInserter get_successors, Node const& begin, Node const& end, BinaryOperator distance, CostType nil_element, InsertIterator result);
Ah oui, j'ai supposé que CostType et Node sont des types ordonnés, pour des raisons de performances (l'implémentation utilise std::set).
Pour Node, je sais pas si c'est une bonne idée, je pourrais peut-être faire une deuxième version où on doit fournir la relation d'ordre.

Citation:

Envoyé par MatRem

En quoi voudrait tu laisser l'utilisateur plus libre? Si c'est juste pour une question de place en mémoire, je ne crois pas que ça soit vraiment intéréssant.

Oui, c'était surtout pour ça. C'est vrai que je n'ai pas trop réflechis au gain que pourrais m'apporter une telle liberté. Mais bon, je débute en POO et pour m'entrainer j'aimerais faire quelque chose de vraiment flexible. J'espère que je ne vais pas tomber dans la surqualité :mouarf:. En tous cas merci pour ton aide, car j'utiliserais ton exemple de Node (si possible en spécialisant le miens :roll:).

Citation:

Envoyé par HanLee

Moi j'ai fait ça il y a justement quelques jours, pour l'algorithme A*.

C'est ce que je suis en train de faire en fait. Je vais essayer de faire quelque chose comme ta fonction, mais avec ma classe.
Si ça t'interesses je poste ma version:

le .h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <limits>
 
#define OK std::cerr << "ok" << std::endl;
 
class Node;
class NodeContainer;
class Graph;
class PathFinder;
 
class Node{
 
	public:
 
		friend class NodeContainer;
 
		//J'aimerais que ces paramètres fassent partie de la spécialisation de ce node:
		unsigned int x, y;
		int cost;
 
 
		//Ceux là servent à l'algo:
		int f, g, h;
 
		void init(){
			f=g=h=0;
			container=0;
			parent=0;
		};
 
		void setParent(Node* node){ parent = node; };
		Node* getParent() const { return parent; };
 
		bool operator> (const Node &node) const { return f < node.f; };
		bool operator< (const Node &node) const { return f > node.f; };
 
	private:
 
		Node* parent;
 
		NodeContainer* container;
 
};
 
class BestNode {
  public:
 
    bool operator()(const Node* n1, const Node* n2) const{ return *n1 < *n2; }
};
 
 
class Graph{
 
	public:
 
		virtual std::vector<Node*> getPossibilities(Node* from) = 0;
 
		virtual int heuristic(Node* node) = 0;
 
		virtual Node* getStartNode() = 0;
 
		virtual bool isTheGoal(Node* node) = 0;
 
		virtual int getCost(Node* from, Node* to) = 0;
};
 
 
//******************************************************************************
//
//	NodeContainer
//
//------------------------------------------------------------------------------
//
//	Ce que le container doit faire, par ordre de fréquence d'appel
//
//	1. contain
//
//		Renvoie si le node passé en argument est dans le container.
//
//	2. insert
//
//		Insert un node dans le container.
//
//	3. removeBest
//
//		Supprimme le meilleur node du container, le renvoie.
//
//	4. remove
//
//		Supprimme le node passé en argument
//
//	5. reInsert
//
//		Insert un node déja présent dans le container.
//
//	Les nodes ne sont contenus que dans un container à la fois.
//
//	Si un node est supprimé, puis réinséré, c'est qu'il est mieux placé
//	qu'il ne l'était avant.
//
//******************************************************************************
 
class NodeContainer{
 
	public:
 
		bool contain(Node* node){ return node->container == this; };
 
		void insert(Node* node){
			c.push_back(node);
			push_heap(c.begin(), c.end(), comp);
			node->container = this;
		};
 
		Node* removeBest(){
			Node* node;
			while(!c.empty()){
				node = c.front();
				pop_heap(c.begin(), c.end(), comp);
				c.pop_back();
				if(node->container == this){
					node->container = 0;
					return node;
				}
			}
			return 0;
		};
 
		void reInsert(Node* node){
			remove(node);
			insert(node);
		};
 
		void remove(Node* node){ node->container = 0; };
 
		size_t size() const { return c.size(); };
 
		bool empty() const { return c.empty(); };
 
	private:
 
		BestNode comp;
 
		std::vector<Node*> c;
};
 
 
class PathFinder{
 
	public:
 
		PathFinder(Graph *graph);
 
		std::vector<Node*> find();
 
	private:
 
		Graph* graph;
 
		NodeContainer closedList;
 
		NodeContainer openList;
};

et le .cpp:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "Astar.h"
 
PathFinder::PathFinder(Graph *graph){
 
	this->graph = graph;
}
 
std::vector<Node*> PathFinder::find(){
 
	int loops = 0;
 
	Node* curNode;
 
	openList.insert(graph->getStartNode());
 
	std::vector<Node*> neighbors;
	std::vector<Node*>::iterator neighbor;
 
	while(!openList.empty()){
 
		// Prendre le meilleur node de la liste ouverte
		// Elle devient la case en cours
		curNode = openList.removeBest();
 
		// Mettre ce node dans la liste fermée
		closedList.insert(curNode);
 
		// Si c'est le node recherché, on s'arrête
		if(graph->isTheGoal(curNode)) break;
 
		// Pour les nodes adjacents au node en cours
		neighbors = graph->getPossibilities(curNode);
		for(neighbor = neighbors.begin(); neighbor != neighbors.end(); ++neighbor){
 
			loops++;
 
			// Si elle n'est pas traversable, on l'ignore.
			if(	graph->getCost(curNode, (*neighbor)) == std::numeric_limits<int>::max() )
 
				continue;
 
			int newG = curNode->g + graph->getCost(curNode, *neighbor);
 
			if(openList.contain(*neighbor) && newG < (*neighbor)->g)
 
				openList.remove(*neighbor);
 
			if(openList.contain(*neighbor) && newG < (*neighbor)->g)
 
				closedList.remove(*neighbor);
 
			if(!openList.contain(*neighbor) && !closedList.contain(*neighbor)){
 
				(*neighbor)->g = newG;
				(*neighbor)->h = graph->heuristic(*neighbor);
				(*neighbor)->f = (*neighbor)->h + (*neighbor)->g;
 
				(*neighbor)->setParent(curNode);
 
				openList.insert(*neighbor);
			}
		}
	}
 
	std::vector<Node*> path;
 
	if(!openList.empty()){
 
		// ici curNode == end
		for(; curNode; curNode = curNode->getParent())
 
			path.push_back(curNode);
	}
 
	std::cerr << "loops: " << loops << std::endl;
 
	return path;
}

Pour mon NodeContainer, je me suis inspiré de la priority_queue de la STL.

Pour l'instant c'est le Graph qui gère les nodes de début et fin, et c'était pas une bonne idée, je vais changer ça.
J'ai surtout fais ça car dans mon cas, je ne veut pas atteindre un node en particulier, mais une ligne de node (je suis dans une carte 2D).

Si tu veux me faire part de tes commentaires, n'hésite pas :)

Et encore merci pour votre aide :king:

27/08/2007, 05h08
HanLee
> Matrem : ben, il faudrait laisser l'utilisateur plus libre de choisir son implémentation de graphe, parce que pour un graphe, une représentation sous forme de matrice d'adjacence, de listes de successeurs, ou tout simplement une matrice pour du pathfinding sur des terrain, sera la plus efficace selon le problème considéré.

> cyril_sy : en fait ton sujet tombe bien ça m'a permis de revoir et puis d'optimiser un peu mon code.

Alors, plusieurs remarques :
- Pour le conteneur : je pense que c'est pas une bonne idée d'utiliser un tas binaire. Ok, on peut obtenir le noeud avec le coût minimal F en O(1). Le problème c'est qu'implémenté sous forme de std::vector, les copies générées par l'insertion dans un tas sont en O(log n), mais avec une grosse constante devant, à cause de toutes les copies qui vont devoir être effectuées.
  
  Un std::set va avoir une insertion en O(log n) mais ça concerne uniquement les déréférencements de pointeurs, ce qui est bien plus rapide.
  
  Mais après, faut voir, vu que ton implémentation de graphe est plus spécialisée que la mienne. Chez moi, prendre un tas est quasiment 2 fois plus lent.
- Pour la closedList, vu que chez toi tu peux savoir si un noeud est contenu dedans (grâce à ton pointeur) en temps constant, je crois que ça n'a pas d'intérêt de l'implémenter sous forme de tas binaire.
- Le design de tes noeuds est intrusif, parce que pour que l'algorithme fonctionne, il faut que tu rajoutes les champs f, g, h.
  Moi dans ma fonction j'ai créé une classe locale qui contient un champ du type Node, qui représente un Node annoté de ses coûts.
- Sinon, tu dis que tu veux atteindre une ligne de noeuds au lieu d'un seul, mais ça revient au même : il te suffit de créer un type de noeuds fictifs, qui peuvent désigner un ou plusieurs noeuds réels, et d'adapter l'heuristique.

Oui c'est vrai qu'on peut vouloir utiliser d'autre représentation de graphe... En tout cas je me suis aperçu que ma version de permettait pas de faire des graphes, juste des arbres.

J'ai corrigé ça et j'ai ajouté une version de A* : find (si mes souvenirs sont bons :) ). :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#ifndef GRAPH_NODE_HPP
#define GRAPH_NODE_HPP
 
#include <map>
#include <set>
#include <vector>
#include <iostream>
 
 
namespace graph
{
 
template<typename Value, typename Cost=long>
class Node
{
public:
	typedef          Value                                           value_t;
	typedef          Cost                                            cost_t;
	typedef          std::multimap<cost_t, std::pair<Node *, bool> > container_t;
	typedef typename container_t::iterator                           iterator_t;
	typedef typename container_t::const_iterator                     const_iterator_t;
	typedef          std::vector<std::pair<Node const *, cost_t> >   path_t;
	typedef          std::set<Node const *>                          visited_t;
 
	Node(Value const & val)
	:value(val)
	{}
 
	virtual ~Node()
	{
		iterator_t it = _childs.begin();
		while(it != _childs.end())
		{
			if(it->second.second)	delete it->second.first;
			++it;
		}
	}
 
	Node * createChild (value_t const value, cost_t const & cost)
	{
		Node * node = new Node(value);
		_childs.insert(std::make_pair(cost, std::make_pair(node, true)));
		return node;
	}
 
	Node * addChild(Node * node, cost_t const & cost)
	{
		_childs.insert(std::make_pair(cost, std::make_pair(node, false)));
		return node;
	}
 
	container_t const & getChilds() const
	{
		return _childs;
	}
 
	value_t value;
 
private:
	container_t _childs;
};
 
template<typename Value, typename Cost>
void print(std::ostream & stream, Node<Value, Cost> const & node, long tabs, typename Node<Value, Cost>::visited_t & visited)
{
	if(visited.find(&node)!=visited.end())
	{
		stream << node.value << " >>> " << std::endl;
	}
	else
	{
		stream << node.value << std::endl;
 
		typename Node<Value, Cost>::const_iterator_t it = node.getChilds().begin();
		while(it!=node.getChilds().end())
		{
			stream << std::string(tabs+1,  '\t') << "(" << it->first << ") : ";
 
			visited.insert(&node);
 
			print(stream, *it->second.first, tabs+1, visited);
			it++;
		}
	}
}
template<typename Value, typename Cost>
void print(std::ostream & stream, Node<Value, Cost> const & node)
{
	typename Node<Value, Cost>::visited_t visited;
	print(stream, node, 0, visited);
}
 
template<typename Node>
bool find(Node const & begin, Node const & end, typename Node::path_t & path, typename Node::visited_t & visited)
{
	bool found = false;
 
	if(&begin == &end)
	{
		found = true;
	}
	else
	{
		if(visited.find(&begin)==visited.end())
		{
			visited.insert(&begin);
 
			typename Node::const_iterator_t it = begin.getChilds().begin();
			while(it!=begin.getChilds().end() && !found)
			{
				path.push_back(std::make_pair(it->second.first, it->first));
 
				found = find(*it->second.first, end, path, visited);
				if(!found) path.pop_back();
 
				it++;
			}
		}
	}
 
	return found;
}
 
template<typename Node>
bool find(Node const & begin, Node const & end, typename Node::path_t & path)
{
	typename Node::visited_t visited;
	path.clear();
	path.push_back(std::make_pair(&begin, 0));
	return find(begin, end, path, visited);
}
 
template<typename Path>
void print(std::ostream & stream, Path const & path)
{
	typename Path::const_iterator it = path.begin();
	while(it!=path.end())
	{
		stream << "(" << it->second << ") : " << it->first->value << std::endl;
		++it;
	}
}
 
template<typename Path, typename Cost>
Cost & cost(Path const & path, Cost & cost)
{
	cost = Cost();
	typename Path::const_iterator it = path.begin();
	while(it!=path.end())
	{
		cost += it->second;
		++it;
	}
 
	return cost;
}
 
}
 
#endif

Voilà comment je m'en sers :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <Node.hpp>
#include <string>
 
using namespace std;
 
 
int main()
{
	typedef graph::Node<string> Node;
	Node graph("root");
 
	Node * node1 = graph.createChild("Child1", 10); //Creation a partir de la racine.
	Node * node2 = graph.createChild("Child2", 5);  //Creation a partir de la racine.
 
	node1->createChild("Child11", 23); //Creation a partir de node1 (Child1).
	node1->addChild(&graph, 17);       //Ajout de la racine a node1 (Child1).
 
	cout << "-----------" << endl;
	cout << "- Graphe :" << endl;
	cout << "-----------" << endl;
	graph::print(cout, graph);
 
	Node::path_t path;
	if(graph::find(*node1, *node2, path))
	{
		cout << "----------------------------------" << endl;
		cout << "- Chemin entre " << node1->value << " et " << node2->value <<" :" << endl;
		cout << "----------------------------------" << endl;
		graph::print(cout, path);
		Node::cost_t c;
		cout << "cout total : "<< graph::cost(path, c) << endl;
	}
 
	if(!graph::find(*node2, *node1, path))
	{
		cout << "----------------------------------" << endl;
		cout << "- Chemin entre " << node2->value << " et " << node2->value <<" :" << endl;
		cout << "----------------------------------" << endl;
		cout << "pas de chemin" << endl;
	}
}

Et le résultat :

Citation:

-----------
- Graphe :
-----------
root
------ (5) : Child2
------ (10) : Child1
------------ (17) : root >>>
------------ (23) : Child11
----------------------------------
- Chemin entre Child1 et Child2 :
----------------------------------
(0) : Child1
(17) : root
(5) : Child2
cout total : 22
----------------------------------
- Chemin entre Child2 et Child2 :
----------------------------------
pas de chemin

27/08/2007, 12h16
cyril_sy

Citation:

Envoyé par HanLee

Pour le conteneur : je pense que c'est pas une bonne idée d'utiliser un tas binaire.

J'ai fais ça pour l'instant, je changerais peut être, c'est ce qui me paraissais le plus pratique. Tu utilises quoi toi?
Pour la liste fermée, ça ne sera surement pas le même container que la liste ouverte.

Citation:

Envoyé par HanLee

Le design de tes noeuds est intrusif, parce que pour que l'algorithme fonctionne, il faut que tu rajoutes les champs f, g, h.
Moi dans ma fonction j'ai créé une classe locale qui contient un champ du type Node, qui représente un Node annoté de ses coûts.

En fait c'est exactement ce que je cherchais a faire, sans y avoir pensé, merci beaucoup :D.
Edit: par contre avec cette solution j'ai un problème pour savoir si un Node est contenu dans un container. En effet le Node renvoyé par le graphe de l'utilisateur ne contient pas de pointeur vers le container. Si je le cherche, ça prend énormément de temps...
Comment fais tu?

Citation:

Envoyé par HanLee

Sinon, tu dis que tu veux atteindre une ligne de noeuds au lieu d'un seul, mais ça revient au même : il te suffit de créer un type de noeuds fictifs, qui peuvent désigner un ou plusieurs noeuds réels, et d'adapter l'heuristique.

>MatRem
Je vais lire plus attentivement ton code un peu plus tard. J'ai regardé vite fait mais je n'ai pas compris tous les passages :roll:. merci encore.
27/08/2007, 17h29
HanLee

Citation:

Envoyé par cyril_sy

J'ai fais ça pour l'instant, je changerais peut être, c'est ce qui me paraissais le plus pratique. Tu utilises quoi toi?
Pour la liste fermée, ça ne sera surement pas le même container que la liste ouverte.

[...]

En fait c'est exactement ce que je cherchais a faire, sans y avoir pensé, merci beaucoup :D.
Edit: par contre avec cette solution j'ai un problème pour savoir si un Node est contenu dans un container. En effet le Node renvoyé par le graphe de l'utilisateur ne contient pas de pointeur vers le container. Si je le cherche, ça prend énormément de temps...
Comment fais tu?

Ben moi comme je t'ai dit pour la openList, j'ai pris un std::set classé selon le coût F (tu peux préciser en paramètre template le comparateur qui sera utilisé).

Pour la closedList, je les classe selon l'opérateur < défini par les noeuds.

Mais oui après on le problème que tu évoques dans la 2e partie.
Pour savoir si le noeud est contenu dans l'openList, oui il faut faire une recherche en temps linéaire.
Mais pour savoir s'il est dans la closedList, non ça ne prend pas énormément de temps, parce qu'on peut le retrouver en O(log n).

Oui, quand on cherche à faire trop générique, il y a des optimisations qui sont parfois impossibles ou délicates à faire. C'est pour ça que je te dis, fais comme tu le sens.
Mais après peut-être que quelqu'un qui passe ici a une meilleure solution.

----
Cependant, je me demande si je vais pas changer le comparateur utilisé dans l'openList, et utiliser le même que celui de la closedList.
Je remarque qu'on cherche le noeud au coût minimal dans l'openList une seule fois par étape ; par contre on vérifie plusieurs fois par étape si un noeud voisin est contenu dans cette openList.

J'ai pas encore testé...
27/08/2007, 18h35
cyril_sy

Et si, au lieu d'utiliser une autre classe qui inclue le node de l'utilisateur, on utilisait un tableau associatif userNode* => astarNode

classé par userNode*. Ca devrais etre assez rapide pour trouver la correspondance?

Je n'ai jamais utilisé un tableau associatif, donc je vais regarder ce que je peux faire avec la STL.