MiniProj:C:2012:Rendu
MiniProj:C:2011 Rendu
- La date du rendu est Lundi 23 avril 2012 à 23h42.
Cette page décrit la procédure de rendu.
L'interface de rendu se trouve à l'adresse: http://rendu.infoprepa.epita.fr/EPITA2015/index.php?TP=20120418
L'interface est toujours la même, il vous faut donc le pass que je vous ai fourni, si vous ne l'avez pas envoyer moi un mail avec dans le sujet les balises [IP][MPC01][PASS] et votre login.
Le suffixe du rendu est "donjon2012", donc le format du dossier (et de la tarball, donc) est le suivant:
- Dossier: login-donjon2012
- Tarball: login-donjon2012.tar.bz2
Bien évidement, votre rendu doit compiler avec la commande make (la moulinette teste GNU et BSD make au cas où ... ) Votre code peut utiliser l'intégralité de la libc (attention tout de même aux extensions non standard) et c'est tout. Normalement, la moulinette tourne sur un FreeBSD, mais si je m'aperçois qu'il y a des (trop) problèmes, je la ferai tourner sur un Linux similaire aux Fedora de vos rack. Dans tous les cas, la machine est en 64bits et supporte les mêmes versions de gcc que vos racks.
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 ê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.)
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. L'une des refs 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 (attention, il s'agit de l'ancienne ref, la nouvelle va plus vite ... )
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
