3. algorithmen frage zu shortest path

algorithmen frage zu shortest path

  • ?

    Hallo,

    ich hätte da folgende algorithmen frage:
    gegeben eine mxn matrix.
    gegeben ein startpunkt (x,y) and ein endpunkt (x,y) in der matrix.
    suche alle kuerzesten pfade vom start zum endpunkt. es ist nur moeglich vertikal oder korizontal sich zu bewegen, keine diagonalen sprünge.

    einen kürzesten pfad zu finden ist recht einfach:
    beispiel:
    8x3 matrix
    startpunkt: 0,0
    endpunkt: 4,2

    ein kürzester pfad wäre dann: 0,0, -> 1,0 -> 2,0 -> 3,0 -> 4,0 -> 4,1 -> 4,2

    nur wie finde ich alle möglichkeiten...ich muss alle bereits gefundenen pfade mittracken?

    0
  • ?

    robery schrieb:

    einen kürzesten pfad zu finden ist recht einfach:
    beispiel:
    8x3 matrix
    startpunkt: 0,0
    endpunkt: 4,2

    ein kürzester pfad wäre dann: 0,0, -> 1,0 -> 2,0 -> 3,0 -> 4,0 -> 4,1 -> 4,2

    nur wie finde ich alle möglichkeiten...ich muss alle bereits gefundenen pfade mittracken?

    Ist das Problem jetzt alle Permutationen zu erzeugen, die viermal rechts gehen und zweimal runter?

    0
  • ?

    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