#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #include <math.h> #include <list> using namespace std; const int MaxEdge = 1000; int map [MaxEdge] [MaxEdge]; int width = 40, height = 40; class Point { public : int x, y; void set (int x1, int y1) { x = x1; y = y1; } void random () { x = (rand () / (RAND_MAX + 1.0)) * width; y = (rand () / (RAND_MAX + 1.0)) * height; } void print (FILE *fp) { fprintf (fp, "(%d,%d)\n", x, y); } bool operator == (Point p) { return ((x == p.x) && (y == p.y)); } bool operator != (Point p) { return ((x != p.x) || (y != p.y)); } }; void fillMap (int nbPoints) { for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) map [i] [j] = 0; int x, y; for (int i = 0; i < nbPoints; i++) { x = (rand () / (RAND_MAX + 1.0)) * width; y = (rand () / (RAND_MAX + 1.0)) * height; while (map [x] [y] == 1) { x = (rand () / (RAND_MAX + 1.0)) * width; y = (rand () / (RAND_MAX + 1.0)) * height; } map [x] [y] = 1; } } void printMap (FILE *fp) { for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (map [i] [j] == 0) fprintf (fp, "."); else fprintf (fp, "+"); } fprintf (fp, "\n"); } } void printMap (FILE *fp, Point start, Point goal, Point p) { for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (start.x == i && start.y == j) fprintf (fp, "s"); else if (goal.x == i && goal.y == j) fprintf (fp, "g"); else if (p.x == i && p.y == j) fprintf (fp, "p"); else if (map [i] [j] == 0) fprintf (fp, "."); else fprintf (fp, "+"); } fprintf (fp, "\n"); } } int g [MaxEdge] [MaxEdge]; list<Point> stackAt [MaxEdge * MaxEdge]; int nodes = 0, sumNodesDijkstra = 0, sumNodesAstar = 0, sumNodesTriangular = 0, sumNodesPerfect = 0; clock_t clockStart; int dijkstra (Point start, Point goal) { for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) g [i] [j] = -1; for (int i = 0; i < height * width; i++) stackAt [i].clear (); nodes = 1; int currentg = 0; Point current = start; g [start.x] [start.y] = 0; while (current != goal) { nodes++; Point p [4]; p [0].set (current.x + 1, current.y); p [1].set (current.x - 1, current.y); p [2].set (current.x, current.y + 1); p [3].set (current.x, current.y - 1); for (int i = 0; i < 4; i++) if ((p [i].x >= 0) && (p [i].x < width) && (p [i].y >= 0) && (p [i].y < height)) if (map [p [i].x] [p [i].y] == 0) { if (g [p [i].x] [p [i].y] == -1) { g [p [i].x] [p [i].y] = currentg + 1; stackAt [currentg + 1].push_back (p [i]); } else if (g [p [i].x] [p [i].y] > currentg + 1) { g [p [i].x] [p [i].y] = currentg + 1; stackAt [currentg + 1].push_back (p [i]); fprintf (stderr, "+"); } } while (stackAt [currentg].size () == 0) { currentg++; if (currentg >= height * width) return currentg; } current = stackAt [currentg].back (); stackAt [currentg].pop_back (); } return currentg; } void generateAndSolveDijkstra (int f, int &nd, int &ld) { fillMap (f); Point start, goal; start.random (); while (map [start.x] [start.y] != 0) start.random (); goal.random (); while (map [goal.x] [goal.y] != 0) goal.random (); ld = dijkstra (start, goal); sumNodesDijkstra += nodes; nd = nodes; if (nd > width * height) { printMap (stderr); fprintf (stderr, "Dijkstra : nodes = %d, length = %d\n", nd, ld); start.print (stderr); goal.print (stderr); } } const int nbTailles = 11; int sumNodesD [nbTailles] [100], sumNodesA [nbTailles] [100], sumNodesT [nbTailles] [100], sumNodesP [nbTailles] [100], sumLengthD [nbTailles] [100], sumLengthA [nbTailles] [100], sumLengthT [nbTailles] [100], sumLengthP [nbTailles] [100]; int main (int argc, char *argv []) { clockStart = clock (); for (int s = 1; s < nbTailles; s++) { height = s * 20; width = s * 20; for (int p = 20; p < 50; p++) { int f = (400 * s * s * p) / 100; sumNodesD [s] [p] = 0; sumNodesA [s] [p] = 0; sumNodesT [s] [p] = 0; sumNodesP [s] [p] = 0; sumLengthD [s] [p] = 0; sumLengthA [s] [p] = 0; sumLengthT [s] [p] = 0; sumLengthP [s] [p] = 0; int nd, ld, na, la, nt, lt, np, lp; for (int i = 0; i < 100; i++) { generateAndSolveDijkstra (f, nd, ld); sumNodesD [s] [p] += nd; sumLengthD [s] [p] += ld; } fprintf (stderr, "Dijkstra (%d,%d) : nodes = %d, length = %d\n", s, p, sumNodesD [s] [p], sumLengthD [s] [p]); } } clock_t t = clock () - clockStart; fprintf (stderr, "time = %2.6f, sumNodesDijkstra = %d, sumNodesAstar = %d, sumNodesTriangular = %d, sumNodesPerfect = %d\n", (((float)t) / CLOCKS_PER_SEC), sumNodesDijkstra, sumNodesAstar, sumNodesTriangular, sumNodesPerfect); }