Search Abstraction:
-
Initial state- A board with misplaced tiles
-
Search space- Any board generated by sliding rows and columns in a certain way: the first and third rows can only be slid left; the second and fourth rows can only be slid right; the first, third, and fifth columns can only be slid up; and the second and fourth columns can only be slid down.
-
Successor- List of boards from the initial/ current board after moving in L1/L3/R2/R4/U1/U3/U5/D2/D4
-
Goal state- A board with tiles placed in canonical form
-
Heuristic- heuristic function that returns cost of state, which is sum of euclidean distances and absolute difference of each element from its current position to its goal position in the canonical form. the total cost is divided by 200.
As asked, we've implemented A* search with a heuristic function that helps us find the best solution in as few moves as possible. For this, we brainstormed ideas to solve the normal 15-puzzle and then modified it accordingly to suit the 2021 puzzle.
For any given initial board, we can move the first and the third rows to the left while the second and the fourth rows can be slid to the right. In the same fashion, we can slide the first, third and fifth columns upwards while the second the fourth can be slid downwards.
We started off by writing a function that can handle this sliding of a particular row/ column.
We do this in the successor function with the initial state as the input parameter.
Initially, the successor list is empty. We create copies of the initial board and then go on to make variations.
So, let's start by moving the 1st row to the left. To do so, we store the 0th index in a temporary variable. As each row has 5 elements in it, we run the for loop until we cover each element in the row. In each iteration, we assign i+1 to i and at the end of the loop, we assign the 0th index value which was stored in a temporary variable to the last index of the row, which is 4 in this case. The resulting row that we get is appended to the successor's list.
It works the same way for the 3rd row as well, where we slide elements to the left. Here, the indexing would be from 10 to 14.
Coming to the 2nd row, where we slide elements to the right.
Here, between the two required indices, we iterate backwards. So, for the 2nd row, the indices being from 5 to 9, we iterate from the 9th index and work down to the 5th index. In each iteration, we assign the value of i-1 to i. Before the start of the loop, we store the value of the last index in a temporary variable and re-assign it to the 1st index of the row at the end of the for loop.
Again, this result is appended to the successor's list.
The same approach goes with the 4th row but the indices being 15 to 19.
Coming to the columns part-
Here, we have to bear in mind that while using the range function, we'll have to jump 5 indices during each iteration as these indices corresponds to the rows
For the first column-where we slide upwards, our range would be 0 to 15, skipping 5 indices each time. We store the value at the 0th index in a temporary variable and re-assign it to the 15th index after the for loop ends. We assign the value of i+5 to i in each iteration. We then add this to the successor's list.
The same approach goes with the third and the fifth columns with the indices ranging from 2 to 17 and 4 to 19 respectively.
For the 2nd column- where we slide downwards, our range would be 1 to 16, iterating backwards and skipping 5 indices each time. We store the value of 16th index in a temporary variable and re-assign it to the 1st index after the for-loop ends. In each iteration, we work down from 16 to 1, by assigning the value of i-5 to i. We then add this to the successor's list.
The same approach goes with the fourth column with indices being 18 down to 3, skipping 5 indices each time.
At the end of this function, we return the successor's list.
To get the direction of the moves, we created a helper function called, 'returnMove', which takes two parameters- (fromState, toState).
We have discussed how the row and column manipulation occurs in the successor function. Using the same logic, we go on to get the directions of each move.
When the fromstate index= 0 and the tostate index=4, we return L1. The same way,
When the fromstate index= 10 and the tostate index=14, we return L3.
When the fromstate index= 9 and the tostate index=5(working backwards), we return R2.
When the fromstate index= 19 and the tostate index=15(working backwards), we return R4.
When the fromstate index= 0 and the tostate index=15, we return U1.
When the fromstate index= 2 and the tostate index=17, we return U3.
When the fromstate index= 4 and the tostate index=19, we return U5.
When the fromstate index= 16 and the tostate index=1(working backwards), we return D2.
When the fromstate index= 18 and the tostate index=3(working backwards), we return D4.
Now, that we've discussed our idea behind the successor and the returnMove function, let's define our goal state so that we know when to stop.
The goal state for this particular problem is one where for the given range(0, 20), we loop through and check if the value stored at each index is not equal to index+1.
For example, during the 2nd iteration of the loop, value of the index would be 1, so the element stored here should not be 2 but rather, 1 itself. If this holds True, then we return True else False.
In A* search, the main component is the heuristic. Our heuristic function works as follows:
It returns cost of state, which is sum of euclidean distances and absolute difference of each element from its current position to its goal position in the canonical form.
Coming to the solve function, where A* search is implemented:
We start with an empty path string, an empty fringe list and an empty visited list to avoid re-visiting states. Initially, we store priority=0, the initial_board and the path inside the fringe. We then heapify the fringe, so that we transform this fringe list into a heap.
We repeat the following until the fringe is empty:
As we've heapified our fringe, calling heappop would pop off the lowest value in the fringe. The popped off values will be stored in (priority, state, path). Now, we append this state to the visited list. At this point, we check if it's the goal state. If yes, we return the path.
If not,
For every s' that we get from the successor function, If s' is not in visited, we heappush the heuristic cost of that state, that particular state and the path on to the fringe.
If a solution doesn't exist, the method returns an empty list.
Search Abstraction:
-
Initial state- start city
-
Search space- Path from current city to next city and vice-versa(as it's bi-directional)
-
Successor- List of paths from current city to next city and vice-versa(as it's bi-directional)
-
Goal state- Solution from start city to end city as per the given parameter(time, distance, segments, safe)
-
Heuristic- g(s)+h(s), where g(s)- cost from start to current city and h(s)- cost from current to end city
We've applied A* search on the road_segments.txt file to find the shortest route from the start city to the end city by considering parameters like total distance, total time, total segments and number of accidents.
We parse the road_segments.txt file and store it in a list.
The successor function takes 2 parameters- map(i.e., the parsed input file) and the start city.
As the cities are bi-directional, start city can be either the first city given in the input file or the second one. We append the city along with the details like length in miles, speed limit and the name of the highway in a list and return it.
We've created a function called, 'hOfs' (h(s)), and gOfs (g(s)) which returns values, summation of which will be considered as our heauristic for each entry in the fringe when we are implementing A* in get_route We initialize all the parameters like distance, segments, safe and time to 0 and add it to the fringe.
To implement A* search in get_route:
We first heapify the fringe and while the fringe isn't empty, we call heappop which pops off the least value from the fringe as we've already heapified the fringe. We update the values of the parameters and add it to the visited list as well. We call the successor function, and if the next city we get as the end city, we calculate the distance, time, segments the number of accidents and return it. If the next city isn't the end city then, we update these parameters and push it to the fringe.
If no path exists, we return []
Search Abstraction:
-
Initial state- The teams given in the input file
-
Search space- All combination of teams with size 1,2 and 3
-
Successor- List of teams which don't have the names present in current team
-
Goal state- set of teams containing all students included once, with least possible cost
-
Heuristic- 2 complaints for each student who is assigned to someone they requested not to work with. 1 complaint for each student who requested a specific group size and was assigned to a different group size. 1 complaint for each student who is not assigned to someone they requested for. Hence Total no' of complaints calculated on the basis of above constraints
Our idea behind solving this particular problem is to first build a naive solution, using which we'll improve it to get better intermediate solutions(and probably an optimal solution).
We've created a bunch of functions, to navigate our way to the solution.
To parse the file, we use 'ParseFileAndStore' which takes the input file as a parameter and returns the parsed input file as a list.
We've created a function called, 'returnStudents'. This creates a list of students taken from the parsed input.
We create two more such functions, called 'returnStudentAndPref' and 'returnStudentExcl'.
returnStudentAndPref function is to store the preferences of all the students. This is again taken from the parsed input.
returnStudentExcl function is to store the non-preferred student names of all the students. We take this from the parsed input file.
For both these functions, we use dictionaries to store the names as key value pairs.
We've created a function called, 'returnComplaints', which will return the number of complaints for a particular team. It takes 3 parameters-team, students-Preferred and students-not preferred. We initialize complaints to 0 and split the team by '-' to get the individual names of the students; this is being stored in a local variable called, 'students'. We run a for-loop until we cover all the names in students. Here, we again split the team to store the preferred and the non-preferred students separately in lists.
As given in the problem statement, we add a complaint when the team size differs from what was being asked for. We check the length of the students list with that of the preferred list. If they differ, then add a complaint.
Now, we create 2 more functions which will facilitate in calculating complaints for the other 2 conditions- not getting their preferred team mates and getting a team mate whom they didn't want.
'returnStudentDifference' function takes 2 parameters- student list and visited list. For each student name in the student list who aren't in the visited list, we add them to a list called, 'notvisited'.
'returnStudentCommon' function takes 2 parameters- student list and visited list. For each student name in the student list who have been visited, we add them to a list called, 'visited'.
Now we call the 'returnStudentDifference' function which will give us the students who are in the preferred list but not in the local students list. The number of students returned by this function is the number of complaints we add.
For the non-preferred students who were still assigned, the complaint is twice for each such non-preferred student. We call the returnStudentCommon function which will give us the students who are in the excluded list but also in the local students list. For each such person, we add 2 complaints.
The cumulated complaint for a team is returned at the end.
Our successor function takes 4 parameters- students, teamsize, students-preferred and students-not preferred
3 team sizes are possible- teams of 1, teams of 2 and teams of 3. So, we create a list for these 3 team sizes.
If the team size is 1: For each team, we call the 'returnComplaints' function and append it to teamsofOne list along with the team member.
If the team size is 2: For each student in the student list, we create teams which consists of that student and another student from the list. We get the complaints for these teams, and append it along with the team members to teamsOfTwo.
If the team size is 3: For each student in the student list, we create teams which consists of that student and 2 other students from the list. We get the complaints for these teams, and append it along with the team members to teamsOfThree.
The 1st solution that we're yielding is the naive one, where we just take the preferred students into account. We've created a separate function for it, called 'naiveSolution' function, which takes 2 parameters- students and the preferred-students and returns a naive solution.
We run a while loop until we cover all the students. The initial solution is an empty string. If we see a 'zzz' in place of a student name, then we call returnStudentDifference which gives us the name of students who are in the student list but haven't been visited yet. We store this in a list called, 'name'. If after this function, we don't get any names, we break out of the loop. Else, we add the first name from this list to the solution and mark this student name as visited.
If a team hasn't been visited at all, we go ahead and append it to the solution and mark it as visited.
Now, that we've dealt with the naive solution, we move on to the intermediate/ better solutions. We create a function called 'returnExhaustiveList', which takes 4 parameteres- students, studentsPref, studentsExcl, naivesol We call the successor function for teams of 1, 2 and 3. We add all these teams to a list called, 'exhaustiveList' if the complaints of each of these teams is less than hat we found for the naive solution and return it.
Finally, in the solver function, We first yield the naive solution. We then sort the exhaustive list and keep a copy in list Of teams. The idea is to iterate through listOfTeams and find the best possible set of teams by taking choices from exhaustive list with least total cost. This solution along with the cost is returned by the intermediate function. the cost returned is compared with the minimum complaints we found till now, if it is lesser, then we yeild this solution. The execution stops either when we have gone through all teams in listOfTeams or if we found solution with cost=0.
Efforts
We tried using the below heuristic for Part 2.
-> Manhattan Distance
-> Euclidean Distance
-> Haversine Formula for calcultion distances using Latitiude and Longitude.
We found that since city-gps didnt have some cities which where mentioned in the road segment text file. We cannot guarantee that we taken the same heuristic function throughout the problem. As a work around we took the data in road-segment.txt file and calculated g(s) and h(s), without involving city gps.
ExtraCredit:
We were thinking we make a list of all contiguous states. Then while making an entry in fringe, we check whethr the entry's state is either the current element of statelist or the next element of statelist. we add it to fringe only if this is true. This will make sure we are traversing through connected states. if it is the next state, we keep a no' of states count and add it by one. when we check for goal state, we check whether this noOfstates and the length of the statelist is the same. if yes, we can be sure that we have a solution with all states with atleast one city in each state. Unfortunately due to lack of time, we are unable to submit this within the deadline.
Citation:
https://jonisalonen.com/2014/computing-distance-between-coordinates-can-be-simple-and-fast/ http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html https://en.wikipedia.org/wiki/15_puzzle#:~:text=The%2015%20puzzle%20(also%20called,order%20with%20one%20tile%20missing.&text=The%20goal%20of%20the%20puzzle,that%20use%20the%20empty%20space. https://hobbylark.com/puzzles/Rubik-Cube-Algorithms https://magazine.impactscool.com/en/speciali/google-maps-e-la-teoria-dei-grafi/#:~:text=Google%20Maps%20is%20based%20on,pioneering%20founders%20of%20modern%20computing.