-
Notifications
You must be signed in to change notification settings - Fork 1
Home
Welcome to the lem-in wiki!
The goal is to get all the ants from start to the end of the map, as quickly as possible.
We built a program which, given an ant farm description (rooms, connecting tubes, start and finish) and a number of ants, will find a set of paths, and return an optimized list of the ant's moves. The given result will describes all of the ant's moves from the start until the end room.
Would it be enough just to find shortest path from start to end? No. Depending on quantity of ants, the shortest path will block a multi-path solution that will lead to a better optimized result.
What is an optimized result in this project? We are looking to get the minimum amount of steps to get ants to end of the map. Solution would be independent set of paths in order to achieve maximum flow start to the end of the map.
By using B.F.S (Breadth First Search) to explore the nodes by level. We add our starting node to the queue, and then add its’ neighbours to the queue, saving information about parent node. Repeat until we reach the end of map. We mark visited notes and never visit the same node twice. We can then retrace the path of parent’s from end to start, and hence find a valid path.
By using Edmond-Karp’s algorithm, when we mark a link from A to B, we will note that the flow from A to B is 1, and from B to A is -1. As all of our edges in this project have a capacity of 1, the flow from A to B is now saturated. The flow from B to A is NOT saturated, so we can reuse these nodes but traveling in the opposite direction. If we do so, this neutralises flow an and we reset the flow between A and B, and B and A, to 0.
Bottle neck value of maximum flow would be value of start/end room neighbours. Because its maximum ants value that we can send at one step to start/end.