Discussion :

[tazimovski773]

Bonsoir tout le monde, je crée cette discussion dans l'espoir de recevoir une généreuse aide (ou au moins des petits coups de pouces ) concernant un projet universitaire dans mon école qui concerne les explorations de graphes/taquins, dans le cadre du module d'intelligence artificielle.

Je joins à mon énoncé une image qui détaille ce que mon programme C doit faire, un ensemble de headers et fichiers sources de manipulations de graphes/piles/listes/arbres qu'on a réalisé l'année dernière, ainsi qu'un lien Mediafire vers un zip qui contient 2 PDFs détaillant les algorithmes d'exploration informée/non informée (coût uniforme; A*, IDA*...).

Je précise que la réalisation de ce projet est malheureusement urgente (doit être rendu avant le jeudi) et des contributions rapides seront infiniment appréciées.

En l'attente d'éventuelles sages réponses, veuillez agréez à mes salutations les plus sincères.

Cordialement.



Codes C.zip

http://www.mediafire.com/download/qa...plorations.zip

[Invité]

C'est chouette.

Mais à part cela, que peut-on faire pour toi ? Qu'as-tu fait ? As-tu au moins essayez ?

Je précise que la réalisation de ce projet est malheureusement urgente (doit être rendu avant le jeudi) et des contributions rapides seront infiniment appréciées.

C'est vraiment triste, pour toi, de ne pas t'y être mis plus tôt, vu l'ampleur du bidule...

Nous ne sommes pas un forum de self-service, ou il suffit d'exposer un "exercice universitaire" pour que d'un coup de baguette magique, tout le monde se rue pour le faire à ta place. T'aiguiller si tu as un soucis sur un point précis, oui. Faire pour toi, non.

" Aide-toi et le forum t'aidera ", comme on dit.

[tazimovski773]

J'ai oublié de préciser que seulement les explorations non informées sont concernés ici donc le PDF d'explorations informées n'a pas de sens ici.

Aussi, dans le fichier 'Codes C.zip' il y a déjà le fichier "graphe.txt". Pour le taquin je crois qu'il sera implémenté sous forme d"un tableau de 2 dimensions dans un autre fichier "taquin.txt".

[tazimovski773]

Je vous remercie pour votre réponse Mr. archMqx. Oui, malheureusement vous avez raison, je dois d'abord vous présenter l'état d'avancement de mon programme d'abord... Le problème c'est que, à part les algorithmes d'exploration (j'ai les pseudo-codes donc je peux les implémenter), je n'ai pas assez de points de repères pour faire fonctionner tout l'ensemble correctement.

En ce qui concerne le temps... Ce projet ne nous à été communiqué que depuis jeudi dernier donc il n'y a pas assez de temps pour l'entamer tôt vu qu'on a des projets dans toutes les matières !!

Enfin, bref, pas d'excuses !! Je vais essayer d'avancer moi-même et recourir à vos aides dès que je plante !! Encore merci pour votre temps !!

[ternel]

Et bien, je vais te faire la même réponse qu'à chaque exercice posté:

Programmer en C, c'est deux choses: programmer, et parler en C.

le C, c'est le langage que comprend ton compilateur pour qu'il puisse écrire du binaire (que comprendra l'ordinateur).
programmer, c'est ce que tu dois vraiment apprendre: savoir créer une solution à un problème dont les données sont suffisantes.

On t'a donné deux choses: une description informelle du jeu, et une description informelle de la solution que doit atteindre ton programme.
On t'a même fait cadeau d'idées de méthodes de résolution.

A toi de trouver un vocabulaire que l'ordinateur saura comprendre.
Pour cela, il te faut définir ton vocabulaire à partir de mots plus simples.

Par exemple, pour commencer, le taquin est un jeu constitué d'une grille de N cases de coté.
L'une des cases est vide, les autres contenant (des cubes indiquant) les nombres de 1 à N²-1.
La grille est initialement mélangée, et le programme souhaite la ranger.
Il dispose pour cela de toutes les informations (la grille complete), et d'une seule action possible: déplacer une nombre d'une case voisine de la case vide dans celle-ci.

En gras, des donnés du problème, en italique, du vocabulaire encore à définir.
Chaque nom correspondra à un typedef (par exemple typedef int case_t;). Un adjectif correspond souvent à une valeur (ici, vide correspondra à une valeur interdite de nombre: par exemple, 0)
Un adverbe de temps désigne doit apparaître dans le code (sous forme d'un commentaire bien choisi)
Enfin, tout verbe est une fonction.


Le C dispose d'un vocabulaire minimal:

• des adjectifs comme vrai, faux,
• des noms comme entier, nombre, adresse (ou pointeur),
• des verbes comme ajouter, affecter, appeler une fonction, lire, afficher, concaténer,

Par contre, il te donne trois outils intéressants:

• les variables qui permettent de nommer des choses.
• les types de donnée dit utilisateurs: structures, énumérations et unions
• la possibilité de définir des fonctions.

Comme certaines choses sont quasiment toujours nécessaires, la bibliothèque standard fourni un vocabulaire complémentaire.

Programmer, c'est donc de descendre jusqu'à un vocabulaire trivial, puis de construire en C les mots qui lui manque.
Tu découvriras que certaines choses ont plusieurs définitions, c'est-à-dire plusieurs solutions techniques.

[tazimovski773]

Bonjour. Merci Mr. "leternel" pour vos sages paroles sur mon problème et sur la programmation en C en général. Je crois que ce sera un grand plus pour moi dans mes futures aventures de programmeur.

En ce qui concerne mon programme; ce que je n'ai pas bien compris est la bifurcation taquin/graphe. Mon programme doit faire 2 choses qui ne sont pas vraiment liées entre elles : parcourir des graphes suivant plusieurs algo d'exploration et déterminer les coûts etc... Et en ce qui concerne le taquin il doit le ranger d'une manière à atteindre un état but à partir d'un état initial.

Ma question est : ne serait-ce t-il plus "convenable" d'écrire DEUX programmes qui fassent les deux choses séparément ? Je suis en train de me demander pourquoi je n'avais pas posé cette question au prof...

[ternel]

A priori, il te faut quatre fonctions (une par méthode d'exploration), et appeler chacune dans ton programme.

Tu peux même imaginer que les quatres fonctions ont la même signature, et utiliser un tableau de pointeur vers ces fonctions pour faire une boucle mesurant les temps d'exécution de chacune. (ou une liste chainée)
L'avantage de procéder ainsi, c'est que ton code pourra évoluer très souplement en ajoutant au fur et à mesure des versions des fonctions.

Voici un exemple de structure de code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef int (*explo_f)();
 
int explo_1();
int explo_2();
 
int main() {
    explo_f fonction[2] = {explo_1, explo2};
    for (int i = 0; i<2; ++i) {
        int début = /*mesurer l'instant de début*/;
        int res = fonctions[i]();
        int sortie = /*mesurer l'instant de sortie*/;
        printf ("fonction %d : %d (en %d ms)", i, res, (sortie-debut));
    }
    return 0;
}

Quant au graphe, je crois que c'est un arbre de décision à explorer, mais je n'ai pas lu tes documents.

[tazimovski773]

Merci beaucoup Mr. "leternel" pour vos efforts et votre réponse.

Oui c'est exactement l'idée que j'ai eu; il faut créer 4 fonctions de parcours de graphes selon l'algorithme de parcours (vu les contraintes de temps je vais seulement me contenter de 2 vu qu'aucun de mes camarades n'a réussi tous les implémenter ).

Aussi, je dois choisir soit le taquin soit le graphe, et pas les deux comme je croyais auparavant !! Je vais donc essayer de finir l'implémentation des algo. A* et IDA* et vous communiquer mes résultats. Le grand problème... Ce sont ces foutus pointeurs qui me causent toujours des ennuis !!

Cordialement.

[ternel]

Un pointeur, ce n'est jamais qu'une variable dont la valeur est une adresse en mémoire.
Il n'y a rien de magique.

Il y a trois moyens d'obtenir une telle valeur:

• prendre l'adresse d'une variable
• faire allouer un bloc mémoire via malloc() (ou variantes)
• faire jouer l'arithmétique de pointeur: par exemple "trois entiers plus loin que telle adresse".

La mémoire est en quelque sorte un immense tableau, et les adresses mémoires sont les indices dans ce tableau.

Concrêtement, le problème n'est pas le pointeur, mais le fait qu'il serve à deux choses très différentes:

1. accéder à une variable qu'on ne possède pas: c'est par exemple le passage dit "par référence"
2. gérer les allocations dynamiques

Les premiers sont des pointeurs qu'on peut qualifier d'observateur. On crée ces pointeurs en prenant l'adresse de quelque chose, et on ne libère pas ce pointeur.
Les seconds s'obtiennent uniquement via des malloc() (ou des fonctions l'appellant), et il faut absoluement les libérer une et une seule fois.

[sambia39]

Bonjour

.......
Aussi, je dois choisir soit le taquin soit le graphe, et pas les deux comme je croyais auparavant !! Je vais donc essayer de finir l'implémentation des algo. A* et IDA* et vous communiquer mes résultats. Le grand problème... Ce sont ces foutus pointeurs qui me causent toujours des ennuis !!
.

Si je peux me permettre, je pense qu'il est préférable de comprendre ce qui est demander.
Il vous est demandé de résoudre le problème en implémentant un algorithme (quant au coût ce référée au graphe).
Plus clairement la solution réside dans l'application d'un algorithme de recherche heuristique afin d'atteindre un but (si je peux dire) grâce aux différentes implémentations (FILE, PILE etc.) connue & appliquer à une recherche heuristique qui vous permettra de répondre.
->(A*)


Quant au coût je pense qu'il s'agit de démontrer à travers un graphe de coût /la résolution du problème d'ailleurs c'est à ça que le graphe sert.
En clair démontrer l'association des états Xn et la valeur fournie par la fonction de recherche heuristique Z(Xn) afin d'estimer le coût du chemin optimum entre Xn et un but.

à bientôt