You are right, of course. My bad.
1 Like
IMO how to define a traveling problem :
- S is the list of stations. Typically itās an array of station, so we refer to them by their index in the array, ie Si is the ith station. For easiness we just use an array of names, so we can refer to them.
- O is the origin. Actually itās the first station of the list. That is, we start and stop at S0.
- R is a route. A route is a permutation over the list of stations, with S0 fixed. R(i) is the ith station in the route.
- D is the function of distances between the stations. Does not matter the internal representation, as long as we can have D(i, j) the distance from station i to station j. Typically itās a matrix, since each distance will need to be searched for at list once(no need for caching).
- D( R) is the total distance of a route. That is, the sum of the distances of each individual trip i D( R(i), R(i+1) ) plus the distance from the last station to the origin.
The goal is thus to find the route R which produces the lowest distance D( R).
The number of possible route are (n-1)! since itās the number of permutations of (n-1) items.
If you donāt go back to the origin, then the number of possible solutions is the same: the solution space is exactly the same.
The solution space being the same does not mean that the complexity of an algorithm is the same. Itās only the complexity of a naive algorithm that searches all possible solutions.
1 Like
Agreed on all counts. I almost did a more formal post, but then I figured you would just clean it up for me 
I tried this after reading your comment. I created a very inefficient route with 8 waypoints and a total of 86 jumps. I plugged it into the EvE client and my script. Both reduced the trip to exactly 41 jumps, but did not put the waypoints in exactly the same order.
I didnāt want to have to deal with using multiprocessing.Manager() to communicate between the two threads. With threading, I could just use global variables.
Iām on Linux, but I figured most people are on Windows, so I compiled the script with py2exe in wine.
The script works by creating an array of waypoints from the values entered by the user. A route is then created from the origin to each of the waypoints. Whichever is the shortest is kept. Then the same thing is done with the waypoint that was chosen to find the next closest waypoint. This continues through the entire array.
The weak point in the script is when the distance from the current waypoint to all of the remaining waypoints is the same. At this point, no optimal route is found and the first unused waypoint in the array is chosen as the next destination. From there, the script once again finds the next closest waypoint.
This is a downfall because the route that comes after this is not considered in the selection. All of the remaining waypoints would need to be used as the origin and routes created from from this point forward to find the optimal path for the remaining waypoints.
This would greatly increase the time it takes to complete the route and so far it seems that there is not much efficiency lost when the optimization is basically paused and then resumed due to reaching a point where the current waypoint is the same distance from all of the others.
Based on Shai_Hulud and Anderson Getenās explanations of how this should be done; i guess it would be possible to add the return path to the origin at the end (or not) and get the total distance of the trip. Then, run the entire thing again, using the next best route and get the total distance again. This could be done for all possible combinations, then the route with the shortest distance would be chosen and displayed to the user. Based on your explanations, this would be the TSP. The problem is, doing this would take an incredibly long time regardless of whether or not the return path was included. It would, however, eliminate the weak point in my script in regard to optimization.
As it is, the script does optimize open ended routes over 12 waypoints which is impossible using the āoptimizeā button in the EvE client. It might not perfectly create a minimum Hamiltonian path, but it will not crash your game, and your route will be shorter.
If you guys can improve it, feel free. I do not have a PHD. This is just a hobby for me.
1 Like
@Maverick_Togenada
What you made is an heuristic to search for a solution. However it does not provide the optimal solution.
example with O the origin and 3 destinations A, B, C :
1337 graph
A - 2 - C - 2 - B
\ | /
11 10 11
\ | /
O
In this example your heuristic finds the solution (O, C, A, B) which is total distance is 10+2+4=16 while a better solution is (O, A, C, B) which is total distance 11+2+2=15.
Heuristic are mandatory when searching for optimal solutions, however they alone canāt provide an optimal search.
1 Like
Oh itās actually much easier than using the manager. All you need is mmap. If you donāt care about windows users, using fork() makes it incredibly easy to create a seperate process. In windows itās a bit of a mess, but not really that bad ā¦ itās rather weird when one is used to forking.
Seriously, when you ignore the built-in things in that regard and just use an anonymous memory mapped file for sharing data, then it becomes super easy and works like a charme.
Source: When I was still coding in python I did that all the time. The best example was me writing a python program to create motion-vectors of my webcamās input, in real-time, using four processes, mixed with x86 assembly. 
And in regards to compiling ā¦ you might want to take a look at Nuitka.
Anyhow, I donāt mean to tell you how to do things.
You just tickled my fancies with this.
It might not always find the 100% absolute best path, but it does significantly improve the route based on the given waypoints. You can see in the example given where I entered 8 waypoints in an inefficient order, the script reduced the length of the route from 86 jumps to 41, the exact same level of optimization provided by the EvE clientās optimization function.
I think sometimes there is a difference between āoptimizingā and āoptimalā where you are making something more efficient as opposed to making something perfect.
The benefit is that you can enter over 12 waypoints in the script and let it run in the background. The EvE client becomes unresponsive when this is attempted with the built in optimization function.
As far as I can tell, the situation described in the graph does not occur frequently enough to significantly hinder improvement of the route.
What would be your suggestion to handle the situation represented in the graph and therefore improve the optimization of the route without increasing the time it takes to complete to an unbearable level?
You seem to be an expert in this field and any help you can offer would be appreciated. I like learning new things and programming is a fun hobby for me. If anything I make or contribute to becomes useful or fun for others, it is a good day.
Iām glad youāve found it interesting. I guess if youāre reading from a file, it doesnāt really matter which process or thread is doing it. I think you must know a better way of doing this than I do. Iāve tried it with sql and txt files, but I was reading from them in the main thread with the tkinter after() function and it was too slow, causing the gui to stutter. If you want to change the script to use multiprocessing, that would be awesome. Currently, itās probably better to run the script with āpython route_optimizer.pyā if you can, instead of using the exe file. py2exe was the only way I knew how to create the exe file and may not be the best solution, especially running it with wine.
Itās a memory mapped file, which is like virtual RAM, aka a swapfile. An anonymous one doesnāt even have a file backing it up and is purely in RAM.
https://docs.python.org/2/library/mmap.html
There are differences between windows and linux, but I forgot. Itās something about anonymous memory mapping. Itās not really that important. The thing is that every process can connect to it and thus share data, super fast, because itās all just arrays in RAM and the writes to disk are, if any, transparent.
compared to what ?
Your algorithm does NOT solve the āshortest pathā. Thatās why itās faster.
Just because it can find the best solution does not give any information on the general case.
No. To optimize is to find the best given a set of criteria. In your case you can not affirm you always find the best, so this is not optimization.
Sure you can trade of precision for research time ; but then you are no more doing optimization. You are doing enhancement.
https://en.wiktionary.org/wiki/optimum
How do you know it ?
In some cases (3 destinations ! Itās not āunfrequentā) it can produce a result worse than the eve router.
To make a correct optimization program. Your algorithm only find the best solutions in a very specific subset of programs, just because it āseemsā to find the best solutions in some cases is not enough to ensure it does.
There is no āmagicalā solution. It is known to be an exponential combination problem, you can NOT find an optimum with a non-exponential time - unless you have much more restrictions on the problems you address.
You made a greedy algorithm that is thus sub-optimal in the general case.
2 Likes
Compared to the route entered by the user. Unless the user has already taken the time to plan an efficient route, in which case they would have no need for the script.
Cool! I will rename the script to āroute_enhancerā. These are just words. You can see here that āoptimizeā can mean that youāre making something more efficient. Either way, arguing over the word is pointless.
I know it from running the script over and over again with different waypoints. The EvE router does not work at all for large numbers of waypoints which is the whole purpose of this thread and the script, so I donāt see how it could be worse.
Fair enough. Iām not an expert.
I did add something to the script which shows the total distance of the path before and after it has been processed. You can try it out yourself and see it works!
If you try it out, you will see that it does give you a shorter route for long lists of waypoints which is the intended purpose. This is not possible with the EvE route management āoptimizeā button which is the purpose of this thread.
Here is an example where I added 17 systems with ice belts from dotlan in a reasonable order:
Here is another where iāve intentionally added an inefficient route and allowed the script to improve it.
If you can do it better, please do. The code is here. I claim no right to it. Or if you tell me something I can do to make it better, I will try.
Thanks for this info! I hadnāt heard of mmap until now. Probably a good thing for me to learn. I will try to use it sometime.
In computer sciences āoptimizationā has a very precise meaning.
I made you an example of which it can be worse with.
Just because you canāt find the āworse scenarioā does not mean they are not present.
Here is my route : From Nomaa, go to Ukkalen, then Akkilen, then Silen. This is 12 jumps.
Your algorithm gives Nomaa, Akkilen, Silen, Ukkalen, which is 13j.
What I claim is that
is actually false, according to your algorithm.
I told you before it is not possible to resolve a TSP-like problem with a greedy algorithm - AFAIK
2 Likes
The EvE route management āoptimizeā button does not work at all for long lists of waypoints. That is why I said āI donāt see how it could be worse.ā This script will occasionally run into the situation you have described, but it will be within a longer list of waypoints. There is no point in using the script to handle a route of 4 waypoints. The EvE client can already do that.
Iāve yet to see a situation where the script runs into a waypoint where all other waypoints are the same distance away, moves on, continues to process the waypoints and then the route is longer than the original. If iāve already traced my route on the map to make it as efficient as possible and then entered it into my script, it just leaves the route as it is for the most part, which means I didnāt need to use it anyway.
Yes, you are right. The script finds the best route that it is capable of finding, but not the 100% best route.
Ok, thank you for at least thinking about it. I guess this is the best I can do with it then. It will give you a shorter route if you enter a long list of waypoints that you have not already scrutinized meticulously and it can handle routes with over 12 waypoints so I hope it is somewhat helpful to someone with regard to the purpose of this thread.
The total number of jumps are displayed before and after now, so if the script somehow runs into a situation like thisā¦
A - 100 - C - 100 - B
\ | /
100 99 100
\ | /
O
ā¦you will know that the result for the entered waypoints is not ideal. Otherwise, if the route is improved and is better than what you entered, then you will know that you can use it.
The same can be said for any algorithm that finds a random solution. It does not say anything about the enhancement properties of your algorithm.
No, that not how algorithmic works. You have to prove that your algorithm has the properties you affirm. However itās as useful as ārandomā algorithm if you donāt prove anything about this algorithm.
As the wikipedia says about your algorithm
For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: āAt each step of the journey, visit the nearest unvisited city.ā This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.
1 Like
Itās not a random solution.
It does what I said it does. You can read the code. You can try it yourself.
Yes, I know. Iāve been reading about it here āā¦a greedy algorithm) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path.ā
This is how it works and I really donāt think itās as terrible as you would like me to believe.
Iām going to post my script in the third party development forum. The OPās question has been answered and I donāt want to continue this back and forth. It is no longer productive. Thanks for the good conversation. o7
To expand (just a bit)ā¦
In many ways @Maverick_Togenada, your algorithm is similar to the genetic algorithm I described and briefly tested in this thread. Both approaches attempt to find a āgood enoughā solution.
Notable differences:
- I never claimed mine to guarantee an optimal solution (although you seem to have mostly come around on this on yours too)
- I found a metric to compare how close my solution is to optimal, by designing the test search space in a way such that I know the optimal solution even when the space becomes intractably big.
So far your best metric has been a couple comparisons to results from EVEās optimization, but for small routes which EVE is able to guarantee an optimal solution. This fails to demonstrate your algorithmās accuracy on big routes (13+ waypoints). You have also demonstrated that your accuracy is better than a single random guess (initial input order), but there is a wide gap between optimal and a single random guess.
@Maverick_Togenada since you cannot know the optimal orderings of large routes for at least pseudo-random large lists (as I did in my contrived test space), this is the standard baseline metric of evaluation. You can demonstrate how good your algorithm performs on various search space sizes by comparing to a completely random search that examines the same number of potential routes as that examined by your algorithm. Do a number of paired trials on the same waypoint lists for each (using a consistent length, say 20), then compare average total distances of best routes for each method/run. Comparison to a random search is often used as a baseline in evaluating genetic algorithms, or methods similar to yours.
Ideally you would also compare to other known methods in this domain (like genetic algorithms) to get a better ranking, but just by comparing to a random search you will be able to say something like āit works this much better than a random search.ā Also keeping individual results would allow more statistically sound method of comparison using a hypothesis test, but not sure this will really be needed for just comparison to random search.
Computer SCIENCE
TL;DR
You have not yet proven your results to be better than random search
You need to read carefully. We have pushed you to correct your initial claim that you had solved TSP in polynomial time (whether you knew you were claiming this or notā¦), and have since corrected unsubstantiated claims.
Neither of us have said itās not a viable option, just that you havenāt demonstrated how viable. This type of assessment isnāt made by āread my code.ā Itās determined through science.
Thanks for the positive response. You at least seem somewhat optimistic about what I created. I donāt think iāve created anything that hasnāt been done before. This quote from wikipedia āā¦lets the salesman choose the nearest unvisited city as his next move ā¦the algorithm on average yields a path 25% longer than the shortest possible path.ā describes quite accurately what iāve done afaik.
So youāre saying to take 20 waypoints, put them in a random order and check the length of the trip. Then take the same 20 waypoints, put them into the script and check the length of the result. Then, do the same for a different group of waypoints. Repeat X number of times to study the effectiveness of the algorithm?
I think iām going to post what iāve made in the third party development forum. I feel like this thread is off course, although not entirely off topic. Itās supposed to be about EvE not optimizing routes above 12 waypoints. I donāt want to make it all about this thing that I made.
1 Like
Small correction:
Look up random search (itās easy to implement). Basically if we allow it N guesses, it guesses N random iterations of the list of waypoints and returns the best one found.
Key here, though, would be to base N off of the number of routes considered by your algorithm for a list of that size (so itās fair). This can be found analytically or by putting in a counter for each time you consider a unique route. By āconsiderā I mean each time you compare your current best route to another.
edit: The data from that wiki is helpful too. I have no reason to doubt the ā25% longerā part (although such is vague, probably changes with list size).
edit_again: Random search seems dumb, probably, but itās just meant as a baseline. Showing your algorithm does better than it proves your algorithm is doing something more than just guessing =)
This is why comparison to other techniques in the domain is important if you want to show your algorithm should be used over others that are also better than random search.
LOL, yeah. I definitely have not solved that. I didnāt mean to claim anything like that. Just that iāve created some sort of work-around for the problem stated in the OP. Sorry about that.
1 Like
Learn to read my posts idiot. Just READ MY POST and stop thinking I do care whatsoever about you. Because I donāt. I only care about you affirming things like āI made a TSP optimizer in polynomial timeā which other people, who canāt read your code, will believe while it is complete retard shĀ”t.
You are a complete ignorant who does not care about making other people believe complete wrong things. You are the āgood idiotā who makes people believe earth is flat because he canāt realize he said something stupid. You are the root of retardness in eg. CODE. people, who are not able to discuss science and thus accept what another idiot said because it floats their boat.
You should be ashamed of affirming you made an āoptimizationā tool . Claiming it once is just an error and normal, but you keeping affirming that false thing is stupidity spreading.
No it does not . You affirm false things and thus are a shitty developer.
I donāt care about your code. Your algorithm is well explained, and it tells your program is NOT optimizing, and without any more proof from you itās as good as a random search.
2 Likes