#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; } bool usePerfect = false; bool useTriangular = false; const int nbPointsTriangular = 8; Point pointTriangular [nbPointsTriangular]; int distFrom [nbPointsTriangular] [MaxEdge] [MaxEdge]; int manhattan (Point p, Point goal) { if (usePerfect) { int h = distFrom [0] [p.x] [p.y]; return h; } if (useTriangular) { int h = abs (p.x - goal.x) + abs (p.y - goal.y); for (int i = 0; i < nbPointsTriangular; i++) { int ht = abs (distFrom [i] [p.x] [p.y] - distFrom [i] [goal.x] [goal.y]); if (ht > h) h = ht; } return h; } return abs (p.x - goal.x) + abs (p.y - goal.y); } int htn (int nb, Point p, Point goal) { int h = abs (p.x - goal.x) + abs (p.y - goal.y); for (int i = 0; i < nb; i++) { int ht = abs (distFrom [i] [p.x] [p.y] - distFrom [i] [goal.x] [goal.y]); if (ht > h) h = ht; } return h; } int sumDeltaPoints (int nb, Point goal) { int sum = 0; for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) if (map [i] [j] == 0) { Point p; p.set (i, j); sum += htn (nb + 1, p, goal) - htn (nb, p, goal); } return sum; } int sumDeltaGoals (int nb) { int sum = 0; for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) if (map [i] [j] == 0) { Point goal; goal.set (i, j); sum += sumDeltaPoints (nb, goal); } return sum; } void setTriangularPoint (int n, Point p) { pointTriangular [n] = p; Point noPoint; noPoint.set (-1, -1); dijkstra (pointTriangular [n], noPoint); for (int i1 = 0; i1 < height; i1++) for (int j1 = 0; j1 < width; j1++) distFrom [n] [i1] [j1] = g [i1] [j1]; } void greedyChoosePoints (int nb) { for (int n = 0; n < nb; n++) { Point bestPoint; int bestSum = -1; for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) if (map [i] [j] == 0) { Point p; p.set (i, j); setTriangularPoint (n, p); int sum = sumDeltaGoals (n); if (sum > bestSum) { bestSum = sum; bestPoint = pointTriangular [n]; } } fprintf (stderr, "bestPoint %d = (%d,%d), sum = %d\n", n, bestPoint.x, bestPoint.y, bestSum); setTriangularPoint (n, bestPoint); } } class Node { public : Point p; int g; }; list<Node> stackAtf [MaxEdge * MaxEdge]; int astar (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++) stackAtf [i].clear (); nodes = 1; int currentf = 0; Node current, tmp; current.p = start; current.g = 0; g [start.x] [start.y] = 0; while (current.p != goal) { if (current.g <= g [current.p.x] [current.p.y]) { nodes++; Point p [4]; p [0].set (current.p.x + 1, current.p.y); p [1].set (current.p.x - 1, current.p.y); p [2].set (current.p.x, current.p.y + 1); p [3].set (current.p.x, current.p.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) { int f = current.g + 1 + manhattan (p [i], goal); if (f < currentf) fprintf (stderr, "not consistent"); if (g [p [i].x] [p [i].y] == -1) { g [p [i].x] [p [i].y] = current.g + 1; tmp.p = p [i]; tmp.g = current.g + 1; stackAtf [f].push_back (tmp); } else if (g [p [i].x] [p [i].y] > current.g + 1) { g [p [i].x] [p [i].y] = current.g + 1; tmp.p = p [i]; tmp.g = current.g + 1; stackAtf [f].push_back (tmp); } } } while (stackAtf [currentf].size () == 0) { currentf++; if (currentf >= height * width) return currentf; } current = stackAtf [currentf].back (); stackAtf [currentf].pop_back (); } return currentf; } void generateAndSolveDijkstra (int f, int &nd, int &ld, int &na, int &la, int &nt, int &lt, int &np, int &lp) { 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; useTriangular = false; la = astar (start, goal); sumNodesAstar += nodes; na = nodes; if (na > width * height) { printMap (stderr); fprintf (stderr, "Dijkstra : nodes = %d, length = %d\n", nd, ld); fprintf (stderr, "Astar : nodes = %d, length = %d\n", na, la); start.print (stderr); goal.print (stderr); } useTriangular = true; for (int p = 0; p < nbPointsTriangular; p++) { pointTriangular [p].random (); while (map [pointTriangular [p].x] [pointTriangular [p].y] != 0) pointTriangular [p].random (); Point noPoint; noPoint.set (-1, -1); dijkstra (pointTriangular [p], noPoint); for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) distFrom [p] [i] [j] = g [i] [j]; } lt = astar (start, goal); sumNodesTriangular += nodes; nt = nodes; if (nt > width * height) { printMap (stderr); fprintf (stderr, "Dijkstra : nodes = %d, length = %d\n", nd, ld); fprintf (stderr, "Astar : nodes = %d, length = %d\n", na, la); fprintf (stderr, "Triangular : nodes = %d, length = %d\n", nt, lt); start.print (stderr); goal.print (stderr); } usePerfect = true; Point noPoint; noPoint.set (-1, -1); dijkstra (goal, noPoint); for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) distFrom [0] [i] [j] = g [i] [j]; lp = astar (start, goal); sumNodesPerfect += nodes; np = nodes; usePerfect = false; } const int nbPathToFind = 100; Point startPoint [nbPathToFind]; Point goalPoint [nbPathToFind]; void generateAndPlace (int s) { height = s * 20; width = s * 20; int f = (400 * s * s * 39) / 100; fillMap (f); printMap (stderr); for (int i = 0; i < nbPathToFind; i++) { startPoint [i].random (); while (map [startPoint [i].x] [startPoint [i].y] != 0) startPoint [i].random (); goalPoint [i].random (); while (map [goalPoint [i].x] [goalPoint [i].y] != 0) goalPoint [i].random (); } usePerfect = false; useTriangular = false; int scoreAstar = 0; for (int p = 0; p < nbPathToFind; p++) { astar (startPoint [p], goalPoint [p]); scoreAstar += nodes; } fprintf (stderr, "Astar score = %d\n", scoreAstar); usePerfect = true; int perfectScore = 0; for (int p = 0; p < nbPathToFind; p++) { Point noPoint; noPoint.set (-1, -1); dijkstra (goalPoint [p], noPoint); for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) distFrom [0] [i] [j] = g [i] [j]; astar (startPoint [p], goalPoint [p]); perfectScore += nodes; } fprintf (stderr, "Perfect score = %d\n", perfectScore); usePerfect = false; useTriangular = true; if (s < 3) { greedyChoosePoints (nbPointsTriangular); int scoreGreedy = 0; for (int p = 0; p < nbPathToFind; p++) { astar (startPoint [p], goalPoint [p]); scoreGreedy += nodes; } fprintf (stderr, "Greedy score = %d\n", scoreGreedy); } } int main (int argc, char *argv []) { generateAndPlace (1); generateAndPlace (10); exit (0); }