Algorithm Performence

First, we will present the results again:

Case	Graph	Pokemons	Time	Agents	Grade	Moves
0	A0	1	30 sec	1	152	52
1	A0	2	1 min	1	526	188
2	A0	3	30 sec	1	284	85
3	A0	4	1 min	1	569	194
4	A1	5	30 sec	1	105	44
5	A1	6	1 min	1	472	186
6	A1	1	30 sec	1	79	31
7	A1	2	1 min	1	312	155
8	A2	3	30 sec	1	73	35
9	A2	4	1 min	1	325	153
10	A2	5	30 sec	1	65	32
11	A2	6	1 min	3	1429	566
12	A3	1	30 sec	1	40	26
13	A3	2	1 min	2	217	177
14	A3	3	30 sec	3	115	123
15	A3	4	1 min	1	234	117

We will notice a few things:

1. Most of our algorithm uses the shortest path algorithm to calculate which Pokemon is best for capturing it. This means that inevitably, cases where there is only one agent and one Pokemon are the most effective cases. That is, all that is left for the agent is to find the most allotted way to Pokemon and from there go to the next Pokemon. There is no decision tree here. One of the interesting things to crack about from this is why there are projects of people whose such trivial cases have been better or worse. It is said that this depends on the manner of the connection between the divisions (Especially to the client). In addition, an overloaded graphical interface complicates the program and slows it down.

2. Our algorithm gets more meaning in more complex cases. That is, when there is a choice tree for some agent for which of the two Pokemon to go. When the distance between them is equal, you should go for the Pokemon with the higher value. But when there is a distant Pokemon with a high value versus a Pokemon with a low value - the problem becomes more complex. In general, we will always prefer the way that includes as many Pokemon as possible. Then the nearest Pokemon (type of TSP), regardless of its value. Here it is worth noting that a calculation that also includes a value is more complex and can be long and very complicated.

3. We came to the conclusion that it is best to place the agents at the beginning as close as possible to the Pokemon, because the location of the Pokemon is already given to us at the beginning of the game.

4. We had an idea we wanted to implement, but we were not successful due to the pressure of time and the load on the rest of the courses and assignments. We will present it now. In our opinion, instead of looking at Pokemons, it is more correct to look at the way with the most score. That is, it does not matter how many Pokemons are collected along the way, but how much the score of this way is worth. If we can mark each path in a graph for each agent as a path with value, and build a function that calculates dependence on score and time, it can bring us the ideal solution. Of course one should think of an algorithm as efficient as possible. But this is a task we currently do not have time to complete. Maybe we will do that in the future.