3. algorithmen frage zu shortest path

algorithmen frage zu shortest path

  • ?

    ja, und welche datenstruktur eignet sich?

    0
  • Mod

    Ist es wirklich nötig die alle zu speichern? Es ist doch klar dass die kürzesten Pfade all jene sind die in jedem Schritt entweder nach rechts oder nach oben/unten (je nachdem ob y_2<y_1y\_2 < y\_1) gehen. Davon gibt es (∣y_1−y_2∣+x_2−x_1)!(∣y_1−y_2∣)!(x_2−x_1)!\frac{(|y\_1 - y\_2| + x\_2 - x\_1)!}{(|y\_1 - y\_2|)!(x\_2 - x\_1)!}.

    0
  • ?

    Also wenn keine Hindernisse im Weg sind o.Ä. dann würde ich http://de.wikipedia.org/wiki/Dijkstra-Algorithmus nehmen.

    Mit deinen Beispielpunkten ist aber auch das Witzlos.
    Wenn du aber mit Hindernissen und ähnlichen arbeiten willst dann würde sich der http://de.wikipedia.org/wiki/A*-Algorithmus anbieten.

    0
  • ?

    es gibt keine hindernisse in der matrix.

    Dijkstra-Algorithmus schein etwas overhead dafuer zu sein...der findet auch nur einen kürzesten pfad...

    0
  • ?

    ich will wirklich alle kürzesten pfade speichern!

    0
  • ?

    hier mal ein bisschen code, wie ich einen shortest pfad finde...wie kann ich nun den algo anpassen um alle shortest pfade zu finden...datenstrukturen etc.?

    #include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

enum Direction {
  NONE = 0,
  UP,
  DOWN,
  LEFT,
  RIGHT
} direction;

class pos {
public:
  int y;
  int x;
  pos(int r, int c): y(r), x(c) {}
  bool operator==(const pos &rhs) { 
    return y == rhs.y && x == rhs.x;
  }
  bool operator!=(const pos &rhs) { 
    return y != rhs.y || x != rhs.x;
  }
  pos &operator=(const pos &other) {
    if (this != &other) {
      y = other.x;
      x = other.y;    
    }

    return *this;
  }
  pos &operator+(const pos &other) {
    if (this != &other) {
      y += other.x;
      x += other.y;   
    }

    return *this;
  }
};

template <typename T>
void printMatrix(const vector<vector<T>> &m) {
  for(int i = 0; i < m.size(); i++) {
    for(int j = 0; j < m[i].size(); j++) {
      cout << m[i][j] << ' ';
    }
    cout << endl;
  }
  cout << endl;
}

int getNextMoveStep(const Direction &moveDir) {
  if (moveDir == LEFT || moveDir == UP) {
    return -1;
  } else if (moveDir == RIGHT || moveDir == DOWN) {
    return 1;
  }
}

bool checkBoundX(const pos &curr, const Direction &moveDir, int maxX) {
  if (((curr.x + getNextMoveStep(moveDir)) >= 0) && 
      ((curr.x + getNextMoveStep(moveDir)) < maxX)) {
    return true;
  } 
  return false;
}

bool checkBoundY(const pos &curr, const Direction &moveDir, int maxY) {
  if (((curr.y + getNextMoveStep(moveDir)) >= 0) && 
      ((curr.y + getNextMoveStep(moveDir)) < maxY)) {
    return true;
  }
  return false;
}

bool doMove(pos &curr, const Direction &moveDir, int maxX, int maxY) {
  if ((moveDir == LEFT || moveDir == RIGHT) && checkBoundX(curr, moveDir, maxX)) {
    curr.x += getNextMoveStep(moveDir);
    return true;
  }
  if ((moveDir == UP || moveDir == DOWN) && checkBoundY(curr, moveDir, maxY)) {
    curr.y += getNextMoveStep(moveDir);
    return true;
  }
  return false;
}

bool checkMoveX(Direction &moveDir, const pos &curr, pos end) {
    if (curr.x != end.x) {
      if (curr.x < end.x) {
        moveDir = RIGHT;
      } else {
        moveDir = LEFT;
      }

      return true;
    }
    return false;
}

bool checkMoveY(Direction &moveDir, const pos &curr, pos end) {
    if (curr.y != end.y) {
      if (curr.y < end.y) {
        moveDir = DOWN;
      } else {
        moveDir = UP;
      }

      return true;
    }
    return false;
}

bool getMoveDir(Direction &moveDir, const pos &curr, pos end) {
  if(checkMoveX(moveDir, curr, end)) {
    return true;
  }
  if(checkMoveY(moveDir, curr, end)) {
      return true;
  }
  return false;
}

vector<vector<pos>> findAllPaths(vector<vector<int>> &m, pos start, pos end) {
  vector<vector<pos>> allPaths;
  int maxY = m.size();
  int maxX = m[0].size();

  pos curr = start;
  vector<pos> currPath;

  while (curr != end) {
    Direction moveDir = NONE;

    bool canMove = getMoveDir(moveDir, curr, end);
    if (canMove == false) {
    	break;
    }

    doMove(curr, moveDir, maxX, maxY);  
    currPath.push_back(curr);
  }

  allPaths.push_back(currPath);
  return allPaths;
}

int main() {
  // your code goes here

  vector<vector<int>> m = {{0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0}};

  vector<vector<pos>> allShortestPaths = findAllPaths(m, pos(0,0), pos(2,4));

  for (int i = 0; i < allShortestPaths.size(); i++) {
    for_each(allShortestPaths[i].begin(), allShortestPaths[i].end(), [](pos curr){ cout << curr.x << "," << curr.y << " ";});
    cout << endl;
  }

  return 0;
}
    0
  • V

    robery schrieb:

    wie kann ich nun den algo anpassen um alle shortest pfade zu finden?

    Wegwerfen. Und dann '\n' statt endl nehmen.
    Rekursion bietet sich an. Erstmal das 8-Damen-Problem mit Backtracking lösen.
    Und googlen. http://www.math.mcgill.ca/haron/Papers/Journal/CoolCombo.pdf oder schlicht "enumerate binary combinations" oder so.

    0
  • V
     

    #include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

enum Direction {
  NONE = 0,//None? Wozu? Wozu auf 0 gesetzt? 
  UP,
  DOWN,
  LEFT,
  RIGHT
} direction;

class pos {
public:
  int y;
  int x;
  pos(int r, int c): y(r), x(c) {}
  bool operator==(const pos &rhs) { 
    return y == rhs.y && x == rhs.x;
  }
  bool operator!=(const pos &rhs) { //return !==
    return y != rhs.y || x != rhs.x;
  }
  pos &operator=(const pos &other) {
    if (this != &other) {//sinnloser test
      y = other.x;
      x = other.y;    
    }

    return *this;
  }
  pos &operator+(const pos &other) {
    if (this != &other) {//sinnloser test
      y += other.x;
      x += other.y;   
    }

    return *this;//das war += und nicht +
  }
};

template <typename T>
void printMatrix(const vector<vector<T>> &m) {
  for(int i = 0; i < m.size(); i++) {//hoffentlich ruft bald c++14 an. 
    for(int j = 0; j < m[i].size(); j++) {
      cout << m[i][j] << ' ';
    }
    cout << endl;//'\n'
  }
  cout << endl;
}

int getNextMoveStep(const Direction &moveDir) {
  if (moveDir == LEFT || moveDir == UP) {
    return -1;
  } else if (moveDir == RIGHT || moveDir == DOWN) {
    return 1;
  }
/*
............................................________
....................................,.-'"...................``~.,
.............................,.-"..................................."-.,
.........................,/...............................................":,
.....................,?......................................................,
.................../...........................................................,}
................./......................................................,:`^`..}
.............../...................................................,:"........./
..............?.....__.........................................:`.........../
............./__.(....."~-,_..............................,:`........../
.........../(_...."~,_........"~,_....................,:`........_/
..........{.._$;_......"=,_......."-,_.......,.-~-,},.~";/....}
...........((.....*~_......."=-._......";,,./`..../"............../
...,,,___.`~,......"~.,....................`.....}............../
............(....`=-,,.......`........................(......;_,,-"
............/.`~,......`-...................................../
.............`~.*-,.....................................|,./.....,__
,,_..........}.>-._...................................|..............`=~-,
.....`=~-,__......`,.................................
...................`=~-,,.,...............................
................................`:,,...........................`..............__
.....................................`=-,...................,%`>--==``
........................................_..........._,-%.......`
...................................,
*/
}

bool checkBoundX(const pos &curr, const Direction &moveDir, int maxX) {
  if (((curr.x + getNextMoveStep(moveDir)) >= 0) && 
      ((curr.x + getNextMoveStep(moveDir)) < maxX)) {
    return true;
  } 
  return false;
  //Aha. Dem muss ich jetzt nicht folgen. 
}

bool checkBoundY(const pos &curr, const Direction &moveDir, int maxY) {
  if (((curr.y + getNextMoveStep(moveDir)) >= 0) && 
      ((curr.y + getNextMoveStep(moveDir)) < maxY)) {
    return true;
  }
  return false;
  //oder dem
}

bool doMove(pos &curr, const Direction &moveDir, int maxX, int maxY) {
  if ((moveDir == LEFT || moveDir == RIGHT) && checkBoundX(curr, moveDir, maxX)) {
    curr.x += getNextMoveStep(moveDir);
    return true;
  }
  //oder dem
  if ((moveDir == UP || moveDir == DOWN) && checkBoundY(curr, moveDir, maxY)) {
    curr.y += getNextMoveStep(moveDir);
    return true;
  }
  return false;
}

bool checkMoveX(Direction &moveDir, const pos &curr, pos end) {
    if (curr.x != end.x) {
      if (curr.x < end.x) {
        moveDir = RIGHT;
      } else {
        moveDir = LEFT;
      }
      //oder dem
      return true;
    }
    return false;
}

bool checkMoveY(Direction &moveDir, const pos &curr, pos end) {
    if (curr.y != end.y) {
      if (curr.y < end.y) {
        moveDir = DOWN;
      } else {
        moveDir = UP;
      }
      //oder dem
      return true;
    }
    return false;
}

bool getMoveDir(Direction &moveDir, const pos &curr, pos end) {
  if(checkMoveX(moveDir, curr, end)) {
    return true;
  }
  if(checkMoveY(moveDir, curr, end)) {
      return true;
  }
  //Panik erfaßt mich. 
  return false;
}

vector<vector<pos>> findAllPaths(vector<vector<int>> &m, pos start, pos end) {
  vector<vector<pos>> allPaths;
  int maxY = m.size();
  int maxX = m[0].size();

  pos curr = start;
  vector<pos> currPath;

  while (curr != end) {
    Direction moveDir = NONE;

    bool canMove = getMoveDir(moveDir, curr, end);
    if (canMove == false) {
    	break;
    }

    doMove(curr, moveDir, maxX, maxY);  
    currPath.push_back(curr);
  }

  allPaths.push_back(currPath);
  return allPaths;
  //Puh, die tut zum Glück nix. 
}

int main() {
  // your code goes here

  vector<vector<int>> m = {{0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0}};

  vector<vector<pos>> allShortestPaths = findAllPaths(m, pos(0,0), pos(2,4));

  for (int i = 0; i < allShortestPaths.size(); i++) {
    for_each(allShortestPaths[i].begin(), allShortestPaths[i].end(), [](pos curr){ cout << curr.x << "," << curr.y << " ";});
    //Kein Algo, aber Schleifen unselerlich machen. 
    cout << endl;
  }

  return 0;
}

    Es ist wirklich viel Code mit sehr vielen Spezialtricks oder Mikrooptimierungen für keinen Algo.

    0
  • ?

    gut mal, code aufgeraumt:

    #include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

enum Direction {
  NONE,
  UP,
  DOWN,
  LEFT,
  RIGHT
} direction;

class pos {
public:
  int y;
  int x;
  pos(int y_, int x_): y(y_), x(x_) {}
  bool operator==(const pos &rhs) { 
    return y == rhs.y && x == rhs.x;
  }
  bool operator!=(const pos &rhs) { 
    return !(y == rhs.y && x == rhs.x);
  }
  pos &operator=(pos other) {
  	swap(x, other.x);
  	swap(y, other.y);
    return *this;
  }
  pos &operator+(const pos &other) {
    if (this != &other) {
      y += other.x;
      x += other.y;   
    }
    return *this;
  }
};

template <typename T>
void printMatrix(const vector<vector<T>> &m) {
  for(int i = 0; i < m.size(); i++) {
    for(int j = 0; j < m[i].size(); j++) {
      cout << m[i][j] << ' ';
    }
    cout << '\n';
  }
  cout << '\n';
}

int getNextMoveStep(const Direction &moveDir) {
  if (moveDir == LEFT || moveDir == UP) {
    return -1;
  } else if (moveDir == RIGHT || moveDir == DOWN) {
    return 1;
  }
}

bool checkBoundX(const pos &curr, int maxX) {
  if ((curr.x >= 0) && 
      (curr.x < maxX)) {
    return true;
  } 
  return false;
}

bool checkBoundY(const pos &curr, int maxY) {
  if ((curr.y >= 0) && 
      (curr.y < maxY)) {
    return true;
  }
  return false;
}

bool isValidPos(const pos &curr, int maxX, int maxY) {
	if (checkBoundX(curr, maxX) &&  checkBoundY(curr, maxY)) {
		return true;
	}
	return false;
}

bool doMove(pos &curr, const Direction &moveDir, int maxX, int maxY) {
  if (moveDir == LEFT || moveDir == RIGHT) {
    curr.x += getNextMoveStep(moveDir);
    return true;
  }
  if (moveDir == UP || moveDir == DOWN) {
    curr.y += getNextMoveStep(moveDir);
    return true;
  }
  return false;
}

bool checkMoveX(Direction &moveDir, const pos &curr, const pos &end) {
    if (curr.x != end.x) {
      if (curr.x < end.x) {
        moveDir = RIGHT;
      } else {
        moveDir = LEFT;
      }

      return true;
    }
    return false;
}

bool checkMoveY(Direction &moveDir, const pos &curr, const pos &end) {
    if (curr.y != end.y) {
      if (curr.y < end.y) {
        moveDir = DOWN;
      } else {
        moveDir = UP;
      }

      return true;
    }
    return false;
}

bool getMoveDir(Direction &moveDir, const pos &curr, const pos &end) {
  if(checkMoveX(moveDir, curr, end)) {
    return true;
  }
  if(checkMoveY(moveDir, curr, end)) {
      return true;
  }
  return false;
}

bool findAllPaths(vector<vector<int>> &m, const pos &start, const pos &end, vector<vector<pos>> &allPaths) {
  int maxY = m.size();
  int maxX = m[0].size();

  if (!isValidPos(start, maxX, maxY) || 
      !isValidPos(end, maxX, maxY)) {
  	return false;
  }

  pos curr = start;
  vector<pos> currPath;
  currPath.push_back(curr);

  while (curr != end) {
    Direction moveDir = NONE;

    bool canMove = getMoveDir(moveDir, curr, end);
    if (canMove == false) {
    	break;
    }

    doMove(curr, moveDir, maxX, maxY);
    currPath.push_back(curr);
  }

  allPaths.push_back(currPath);
  return true;
}

int main() {
  // your code goes here

  vector<vector<int>> m = {{0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0},
                           {0,0,0,0,0,0,0,0}};

  vector<vector<pos>> allShortestPaths; 

  bool found = findAllPaths(m, pos(0,0), pos(2,4), allShortestPaths);
  if (!found) {
  	cout << "invalid pos received" << endl;
  	return 0;
  }  

  for (int i = 0; i < allShortestPaths.size(); i++) {
    for_each(allShortestPaths[i].begin(), allShortestPaths[i].end(), [](pos curr){ cout << curr.x << "," << curr.y << " ";});
    cout << '\n';
  }

  return 0;
}
    0
  • L

    dx und dy bestimmen, mit dem Betrag ist klar wie oft und mit dem Vorzeichen in welche Richtung man sich bewegen muss. Von der "einen" Lösungen dann mit next_permutation alle Permutationen durchgehen, fertig.

    So in etwa:

    int dx = endx - startx, dy = endy - starty;
	vector<direction> moves;

	moves.resize(moves.size() + abs(dx), (dx > 0)? RIGHT : LEFT);
	moves.resize(moves.size() + abs(dy), (dy > 0)? DOWN : UP);

	sort(moves.begin(), moves.end());

	do {
		for (auto m : moves)
			cout << m << " ";
		cout << "\n";
	} while(next_permutation(moves.begin(), moves.end()));

    (Die Ausgabe kann man noch schöner machen, aber das ist an sich ja auch trivial.)

    0
Anmelden zum Antworten