Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool sortByX(const loc loc1, const loc loc2)
- {
- return (((loc1.x*100)+loc1.y)<((loc2.x*100)+loc2.y));
- }
- //Above is the alogorithm for sort and next_permutation
- int findlength(vector<loc> dm, loc robot)//finds total length of a path and returns as an int
- {
- int length=0;
- length = ((abs(robot.x-dm[0].x))+(abs(robot.y-dm[0].y)));
- for (int x=0; x<10; x++)//could be x<dm.size() for scaleabilty, but that seems outside the scope of project
- {
- length = length + ((abs(dm[x].x-dm[x+1].x))+(abs(dm[x].y-dm[x+1].y)));
- }
- return length;
- }
- void determineRoute(vector <loc> dm, loc robot)
- {
- int shortestlength = findlength(dm,robot);
- int curlength;
- cout << shortestlength << endl;
- for (int x=0; x<=3628800; x++) // <= value is 10!, since that's the number of paths for 10 diamonds, could be dm.size()!
- //WARNING: Doing dm.size()! would quickly take up too much memeory for non-trivial sizes of dm, because TSP is NP-hard
- {
- next_permutation(dm.begin(),dm.end(),sortByX);
- curlength = findlength(dm,robot);
- if (curlength<shortestlength)
- {
- shortestlength = curlength;
- TSP = dm; // Yay Vectors!
- }
- }
- }
- action choose_next_step(int w, int h, loc robot, vector<loc> dm, ostream &log)
- {
- if (firstrun)
- {
- sort(dm.begin(),dm.end(),sortByX);
- determineRoute(dm, robot);
- firstrun=false;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement