MiniProj:C:2010:Rendu

De wiki-prog
Révision de 10 avril 2010 à 13:37 par Slashvar (discuter | contributions)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher

MiniProj:C:2010 Rendu

Cette page décrit la procédure de rendu.

L'interface de rendu se trouve à l'adresse: http://teach.kh405.net/EPITA2013/

Pour accéder à cette page, vous avez besoin de votre login et du pass fourni par les AOC en début d'année. Si vous n'avez pas ce pass (ou si vous rencontrez des problèmes de login) vous devez m'envoyez un mail (marwan [dot] burelle [at] lse [dot] epita [dot] fr) avec les balises (attention important !) suivantes: [SPE][PROG][MPC2010][PASS]. Je lirais ces mails en priorité.

L'interface de rendu vous permet de rendre autant de fois que vous le voulez jusqu'à la date limite (lundi 12/4 à 12h42), mais attention, je ne garde aucune archive, seul le dernier rendu sera corrigé.

Lorsque vous uploadez votre archive, l'interface vous affiche un rapport d'upload. Attention, seules les archives dont le nom respecte le sujet sont acceptées par l'interface. Le rapport de rendu vous renseigne sur: le nom de votre fichier, sa date d'upload, sa taille (en octets), le type de fichier (sortie de la commande file(1)), la somme MD5 du fichier et enfin un listing de l'archive obtenue avec la commande: 

> tar tjf login-miniprojc.tar.bz2 login-miniprojc

Ce listing n'affiche donc que les fichiers dans le répertoire attendu (à noter que la moulinette utilisera le même principe pour décompresser votre archive, par conséquent seuls les fichiers dans le bon répertoire seront décompressés.)

Si le rendu échoue, vérifier que votre archive à la bon nom ou ne dépasse pas la taille maximale (2 Mo) avant de vous plaindre.

Si votre archive n'est pas au bon format, vous aurez un message d'erreur (celui de tar) à la place du listing de l'archive, vous n'avez donc aucune excuse pour rendre au mauvais format.

L'interface de rendu se souvient de votre dernier rendu et vous réaffiche donc le rapport lorsque vous vous connectez.

Cas particulier

Algo de sup

Si vous passez l'algo de sup, vous avez le droit d'être en binôme (avec quelqu'un passant l'algo de sup) dans ce cas, vous devez m'envoyer un mail avec le nom (et login) des deux personnes et le login de celui qui rendra le projet. Dans ce cas, vous devrez également avoir deux lignes dans votre fichier AUTHORS avec en première ligne le login de celui ayant rendu.

Si vous êtes (encore) coincé sur les graphes, voici une pseudo-implantation de l'algorithme A* en C (attention, plusieurs opérations sont sans définition.) Cette implantation n'a pas été testée: 

/* the graph structure is kept abstract, a state is a vertex of the
   graph plus distance and direct ancestor information. */
 
/* open and close set are abstract structures working as set. Open is
   also supposed to be ordered */
 
/* h(t_state s) is the heuristic function: it returns a float (or
   double.) Normally your heuristic should be aware of the full graph
   and of the destination of your path finding. */
 
void astar(t_graph g, int src, int dst)
{
  t_state		cur;
  t_adj			adj;
  t_state_list		successors;
  t_open_set		opened; // state to be treated
  t_closed_set		closed; // state already treated
  // We get the source state
  cur = get_state(g, src);
  // By default, state have an infinite distance, we fix it to 0 for
  // the source.
  set_dist(0, cur);
  // Source state is its own ancestor.
  set_ancestor(cur, cur);
  opened = empty_oset();
  closed = empty_cset();
  do
    {
      // closed the current state
      add_cset(cur, closed);
      // get successors of the current state
      successors = get_succ(cur, g);
      // iterate on successors
      while ((adj = next(successors)))
	{
	  // If adj->state is not closed and current path is sheeper
	  // we update the state.
	  if (!isin_cset(adj->state, closed)
	      && get_dist(adj->state) > get_dist(cur) + get_cost(adj))
	    {
	      // update distance
	      set_dist(get_dist(cur) + get_cost(adj), adj->state);
	      // update weight of the state (distance + heuristic)
	      set_weight(get_dist(adj->state) + h(adj->state), adj->state);
	      // current state is the new ancestor of adj->state
	      set_ancestor(cur, adj->state);
	      // open set is ordered using weight and not distance,
	      // this is the difference with Dijkstra's algorithm.
	      update_oset(adj->state, opened);
	    }
	}
 
      // done with current, go to next.
      // get_min returned the minimal element of an ordered open set,
      // or NULL if the set is empty.
      cur = get_min(opened);
    }
  while (cur && !is_state(dst,cur));
 
  // Now, if cur != NULL, it is the destination state and we can
  // extract the full path using get_ancestor recursively until we
  // reach the source state.
}

Le code précédant décrit une version abstraite de l'algorithme: la méthode d'accès aux sommets et aux successeurs (et la nature de la liste de successeurs), la gestion des éléments ouverts et fermés et la gestion des états (sommets en cours de traitement) sont cachés au travers des opérations utilisées dans la fonction (leur nom se veut parlant et le commentaire les accompagnants devrait suffire pour comprendre le code.)

API

Vous n'avez pas encore de login, mais, ceux-ci devraient arrivés rapidement (d'ici vendredi soir) dans votre boite mail EPITA.

Examples suplémentaires

Voici un donjon simple avec beaucoup d'arc et possibilité de circuit: 

ROOMS: 11
MONSTER: 10 420000
BREWERY: 5 5
ARCS
ARC: 1 1 2
ARC: 1 1 3
ARC: 1 1 4
ARC: 1 1 5
ARC: 1 1 6
ARC: 1 1 7
ARC: 1 1 8
ARC: 1 1 9
ARC: 1 1 10
ARC: 2 1 1
ARC: 2 1 3
ARC: 2 1 4
ARC: 2 1 5
ARC: 2 1 6
ARC: 2 1 7
ARC: 2 1 8
ARC: 2 1 9
ARC: 2 1 10
ARC: 3 1 1
ARC: 3 1 2
ARC: 3 1 4
ARC: 3 1 5
ARC: 3 1 6
ARC: 3 1 7
ARC: 3 1 8
ARC: 3 1 9
ARC: 3 1 10
ARC: 4 1 1
ARC: 4 1 2
ARC: 4 1 3
ARC: 4 1 5
ARC: 4 1 6
ARC: 4 1 7
ARC: 4 1 8
ARC: 4 1 9
ARC: 4 1 10
ARC: 5 1 1
ARC: 5 1 2
ARC: 5 1 3
ARC: 5 1 4
ARC: 5 1 6
ARC: 5 1 7
ARC: 5 1 8
ARC: 5 1 9
ARC: 5 1 10
ARC: 6 1 1
ARC: 6 1 2
ARC: 6 1 3
ARC: 6 1 4
ARC: 6 1 5
ARC: 6 1 7
ARC: 6 1 8
ARC: 6 1 9
ARC: 6 1 10
ARC: 7 1 1
ARC: 7 1 2
ARC: 7 1 3
ARC: 7 1 4
ARC: 7 1 5
ARC: 7 1 6
ARC: 7 1 8
ARC: 7 1 9
ARC: 7 1 10
ARC: 8 1 1
ARC: 8 1 2
ARC: 8 1 3
ARC: 8 1 4
ARC: 8 1 5
ARC: 8 1 6
ARC: 8 1 7
ARC: 8 1 9
ARC: 8 1 10
ARC: 9 1 1
ARC: 9 1 2
ARC: 9 1 3
ARC: 9 1 4
ARC: 9 1 5
ARC: 9 1 6
ARC: 9 1 7
ARC: 9 1 8
ARC: 9 1 10
ARC: 10 1 1
ARC: 10 1 2
ARC: 10 1 3
ARC: 10 1 4
ARC: 10 1 5
ARC: 10 1 6
ARC: 10 1 7
ARC: 10 1 8
ARC: 10 1 9
ARC: 10 1 11

Vous pouvez tester ce donjon avec la commande: 

PATH 5 1 11

Le chemin le plus court fait 280000 sommets. La ref met entre 1.07s et 1.13s (avec l'entrée standard redirigée sur /dev/null, sans la redirection elle met aux alentours de 1.24s) pour trouver le chemin sur ma machine.

Un autre plus simple: 

# Salles
ROOMS: 10
MONSTER: 4 4
MONSTER: 9 20
BREWERY: 7 5
DEAD: 3

# couloirs
ARCS
ARC: 1 1 2
ARC: 1 1 3
ARC: 2 1 4
ARC: 2 1 5
ARC: 3 30 6
ARC: 4 1 5
ARC: 5 6 2
ARC: 5 1 6
ARC: 6 1 7
ARC: 7 1 8
ARC: 8 1 6
ARC: 8 1 9
ARC: 9 1 10

Encore un simple: 

ROOMS: 13
MONSTER: 6 5
BREWERY: 4 10
DEAD: 3
DEAD: 5

ARCS
ARC: 1 1 2

ARC: 2 1 3
ARC: 2 1 7
ARC: 2 1 8

ARC: 3 1 4

ARC: 4 1 5
ARC: 4 1 9
ARC: 4 1 10

ARC: 5 1 6

ARC: 7 1 3
ARC: 7 5 4
ARC: 7 1 8
ARC: 7 1 9

ARC: 8 1 3
ARC: 8 5 4
ARC: 8 1 7
ARC: 8 1 10

ARC: 9 1 5
ARC: 9 2 11

ARC: 10 1 5
ARC: 10 1 12

ARC: 11 1 5
ARC: 11 1 6
ARC: 11 1 7
ARC: 11 1 13

ARC: 12 1 5
ARC: 12 1 6
ARC: 12 1 8

Avec par exemple la commande: 

PATH 5 1 13
Récupérée de « http://wiki-prog.infoprepa.epita.fr/index.php?title=MiniProj:C:2010:Rendu&oldid=1116 »