Thread: explanation of the n=np problem please

Hi, I read a thread in this forum (in the pseudoscience section) talking about the famous N=?NP problem. I have seen this and tried to understand this but it doesn't make sense yet.
Can someone please explain this famous problem in simpler terms (like very simple terms)?

I know it has something to do with what is faster: finding the formula or checking if its right?

I don't know a lot about it myself, but let me take a stab. Consider a yes-or-no problem which takes n inputs. For example, given a set S of n distinct, positive integers and another integer k, can you write k as the sum of distinct elements of S? Suppose that the answer to our problem is yes. There are two main things we'd like to do in the context of this problem:

1. decide whether potential solutions are correct;
2. produce solutions

The former is an easier thing than the latter: when you produce a potential solution, you have to be able to decide whether it's true!

Suppose we have some algorithms to do 1. and 2. Oftentimes you can describe the time it takes to perform these algorithms as a function of the number of inputs n. (By "time" I really mean "how many calculations you have to perform".) For each problem, there are good algorithms (fast ones) and bad algorithms (slow ones). We can speak of the minimal amount of time it takes to complete 1. or 2. as being the running times of the best algorithms that exist, and we consider this minimal time to be the complexity of the problem. We can then break problems into "classes" based upon the complexity of 1. and 2.

Two important notions of speed of algorithms we're interested in are polynomial and non-polynomial time. An algorithm is polynomial time if the number of steps it takes is (less than or equal to) a polynomial in the number of inputs n, e.g. n, n², n²⁰+3n⁷, etc. An algorithm is polynomial time if it runs much faster, too--for example, log(n) is much faster, so this is polynomial time. An algorithm which is not polynomial time is... non-polynomial time. In other words, the number of steps grows faster than any polynomial as the number of inputs increases.

Now we define P and NP. NP is the set of problems where 1. has polynomial time complexity. P is the subset of NP where 2. also has polynomial time complexity. The question, then, is whether P is all of NP or whether there exist "hard" problems for which 2. is non-polynomial time. The traveling salesman problem (TSP) is an example of such.

So our poster was claiming that he had shown P = NP by finding solutions to TSP in polynomial time. I believe I debunked him.

interesting, thanks!

and good job on your debunk, lol.

Originally Posted by serpicojr

So our poster was claiming that he had shown P = NP by finding solutions to TSP in polynomial time. I believe I debunked him.

Yup. Thanks for the debunk. I believed it sounded to good to be true but didn't have the maths enough to challenge the way you did.

Dear Serpicojr,

I don't think you debunked me. I got all the more sure that my solution is ok. We had a few conversations and I believe in one you said if you do all the routes then it is ok. Then I don't know why you feel you debunked me when my answer was yes.

Also it seems you cannot use the word non polynomial time it should be non deterministic polynomial time otherwise you will be considered as not aware of the whole subject properly let alone debunk a solution ot this kind of a problem.

Mathew Cherian

To sunshine warrior,

You are more modest in your approach, you accepted the fact that you don't seem to have enough maths to make it look absurd. If you had enough maths then you would have found it otherwise, you might have pursued further why such solutions exists, may be why it creates such solution when each starting city takes it's next city constant and look for combinations etc;. May be one can come up with some theorems or regularities in graph theory or combinations. Even I haven't gone further with this. My only objective was to prove that real mathematics requeired to decipher our environment were presented to us and there hasn't beeen any further progress and probably after Einstine we never had anyone capable enough to work to reach any further if required so.

Hope I haven't crossed the line of civility required by this forum.

Mathew Cherian

Originally Posted by Mathew Cherian

To sunshine warrior,

You are more modest in your approach, you accepted the fact that you don't seem to have enough maths to make it look absurd. If you had enough maths then you would have found it otherwise, you might have pursued further why such solutions exists, may be why it creates such solution when each starting city takes it's next city constant and look for combinations etc;. May be one can come up with some theorems or regularities in graph theory or combinations. Even I haven't gone further with this. My only objective was to prove that real mathematics requeired to decipher our environment were presented to us and there hasn't beeen any further progress and probably after Einstine we never had anyone capable enough to work to reach any further if required so.

Hope I haven't crossed the line of civility required by this forum.

Mathew Cherian

Mathew

As far as I am aware, the P/NP problem is an important one. Since I am hampered not just by my lack of maths, but also by my lack of maths terminology (which makes me unable to pick up on some of the things you say) it was difficult for me to focus my suspicion that you may not have made the breakthrough you desire.

I wish you all the best in any case.

T divided by zero,

Your question is answered as follows. NP and P are all polynomials. Then where does this polynomials appear in different algorithms or what connections has polynomials got to do with algorithms which are just menus for programing computers. It is the count of the 'comparisons' one make in the programs of a Von Nueman architecture computer. How the comparisons increase as the number of entities as reprsented by n increases. That is if a problem can varie from 1 varible to infinite variables then how does the computer respond to such increases. For example if in graph theory there are vertices called nodes and lines connecting these nodes. If there are 5 such nodes for a problem then n=5.
So the question is how the comparisons in the menu or program increase as n increase from say 5 to 10. It is noted that depending on the problem description the increase can be either linear or exponential, the comparison I mean. If it is linear it is called Polynomial Time and if exponential it is called Non deterministic polynomial time and not Non polynomial time as serpicojr explained earlier. He accepts the fact that he is not a deep master of the art of computer complexity and mistakes do happen in such times nothing to worry about.

Hope I made and attempt to lead you to understand complexity in computing.

Mathew Cherian

To Divided by zero:
By the time I thought I explained you the basics of complexity, I found that I didn't the formation of polynomials from which the name NP and P arise.

You go to my paper on http://www.npp.co.in and see under Quick sort and Bubble sort. How the polynomials get formed. Take for example Bubble sort. It is an array of [1,n] of integers. Our objective is to sort them in assenting order. You go to the nth number start comparing with the previous number and if it is lesser than the previous number you exchange their position. So the comparison is 1. Now you compare this (n-1) nubmer with (n-2) nubmer and exchange if (n-1) < (n-2). You keep on doing this by going up till you reach position one and the smallest number will be on top after n comparisons. You now go back to the bottom and repeat (n-1) times. Then (n-2) times and so on and you have the 1, 2nd, 3rd and so on nubmers. If you add up the number of comparisons it gives a series n+(n-1)+(n-2)+......+1 which is equal to n² -(1+2+3+....+n). Like this there are n columns so you multiply the above polynomial by n. Now how much this polynomial is for n variable is or how much comparisons for n variables is got by dividing this by n which gives a polynomial with highest value as n². So in the jargon of complexity theorists we say the algorithm for Bubble sort rise faster than n². Why faster is again another story which is machine level work which I have explained in the positng in the psudo science section my reply to serpico jr.
Now also nⁿ is equal to e^{n log(n)} this is an upper bound comparison and we say the algorithm rise as fast as n log(n) or and exponetial time since the e exponent or little Oh or o( n log (n)). Little o is highly complex than big Oh or O(n).

I leave it to you to find for the complexity for Quick sort. You can use my paper from the above website and you see it is O(n). Little ohs are usually intractable using conventioonal computers where as little ohs can be solved or computed using conventional computers. Little oh's are called NP's or non deterministic polynomial time algorithm Bubble sort and little ohs are called P type algorithms or computable algorithms of lower complexity like Quick sort.

Hope now you can solve any complexity problem if you know how to solve them manualy.

Mathew Cherian

Matthew, if you really solved the p=np question then why not submit it and make a million dollars?

btw, thanks for your clarifications!

Originally Posted by Mathew Cherian

We had a few conversations and I believe in one you said if you do all the routes then it is ok. Then I don't know why you feel you debunked me when my answer was yes.

If you check every possible route, this is brute force. This is n! possibilities. n! is not polynomial time. If this (or a slight variation thereof) is your algorithm, then you didn't solve P = NP. If this is not your algorithm, please explain yourself better! The burden is on you to explain it!

To Serpico jr,

First of all you notion that there are n! routes for the TSP is wrong considering the posing of the problem. First of all there is a starting city so if there is n! routes then this assumption fails. There are lesser routes may be n² routes. Here we don't go to the starting city again which violates again the description of the problem that one should touch only a city ones. So this reduces the number of tours for a 5 city tour to just 20 < n².
Then the algorithm is designed in such a way that just the presence of n² doesn't make it o(n²). It is still O(n) for Quick sort. In case you need a psudo code which I developed for someone else on request I am cutting and pasting it below. It is difficult as it is for modern computer scientists, I don't know how you will cope with it. Any how try and see if you understand.
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{ {{{{{{{{

Psudo-code for the solution to NP=P

Type city[C, H, B, M, P]
Type Data
Beg_city, End_city:city
Cost: integer
Tick:Boolean
End data

Array tour_cost[1..5, 1..4] of Data
Temp:city
Start_city: city
List:city; cost, mincost:integer

Begin
Min_cost := 0
Start_city :=city[1]
Tick = false
Fill array with data
Bubble or Quick sort each column of the array in ascending order
List :=start_city; Temp:=start_city
1: Find end_city in data of the start_city

If it is ticked increment start_city to next in the column
Increment till not ticked city is reached tick it and append to the list
Start_city = end_city in data
Go to 1
Do this till all cities are reached
Add up the cost and place it in the cost
If cost < min_cost then min_cost = cost
Start_city = temp and repeat 1 again
Do this 4 times
Now after the 4th iteration increment start_city(column) and temp=start_city
Initialize data except the start_city
Repeat 1
Do complete all the tours by incrementing start_city after 4 steps
At the end data in the min_cost is the minimal cost tour.
++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++
Hope this suffice. I thought on your directives in finding a sort without comparison, I have found one. In simple steps it is you take the data array, subtract the first data from rest. The negative signs are clubbed together and rest discarded. Put back the first data in it’s place and do the same subtraction with the second data. You again discard the negatives. Go on like this till you get one vale which will be the Highest value. Now go back to the last but one discarded list and repeat the whole process you will get the next highest number. Keep on repeating this till you reach the first discarded list and you get a a list in ascending order.

Mathew Cherian

Thank you sunshine warrior and divided by zero for your kind replies.

To divided by zero why I try to solve this problem, it is not foir the money involved in the first place. It is just to prove a point that present day knowledge of Mathematics is not limiting in explaining everything around us. Another reason it is a policy to never make anyone take easy routes out which will take humanity to dead ends. As the old saying goes 'taking easy routes makes some Trees and all Rivers crooked'.

Hope that is sufficient reason to worry about doing this problem when you can.

Mathew Cherian

Okay, let's suppose we have a starting city and an ending city. Then there are (n-2)! routes. You're very concerned with comparison. This is certainly an important part of the problem. Calculating the lengths of the routes is another part of the problem. Ignoring the comparisons, if you want to consider all routes, you have (n-2)! things to calculate. That's why brute force takes too long.

Originally Posted by Mathew Cherian

Thank you sunshine warrior and divided by zero for your kind replies.

To divided by zero why I try to solve this problem, it is not foir the money involved in the first place. It is just to prove a point that present day knowledge of Mathematics is not limiting in explaining everything around us. Another reason it is a policy to never make anyone take easy routes out which will take humanity to dead ends. As the old saying goes 'taking easy routes makes some Trees and all Rivers crooked'.

Hope that is sufficient reason to worry about doing this problem when you can.

Mathew Cherian

well if you submit your solution then you will know if it is right or wrong.

To Serpico Jr,

There is no end city. The problem wording is one to choose a start city and keep moving so that the Traveling Salesman touches each city ones and not any more. One is supposed to find the minimimal cost of such a tour. When you have finished all cities ones you stop at which ever city is the last in your tour. You need not go back to the start city since that will make two tours to that starting city.

So if cities are C, H, M, B and P and you start from C there will much less than n! tours since or (n-2)! tours. There may be n² tours if one modifies the problem so that one goes back to the starting city from the last city. Then this violates the problem definition. So there will only be for this problem (n² - n) tours under problem definition. If you extend the problem to go back to starting city then there will be (n²) paths. That doesn't mean that it is an n² algorithm and eponetial. Since we use Quick sort it is again O(N) in the later part of the problem where N = n x n.

I would also like to answer Divided by zeroes question why I am insistant on comparisons. This is the basic meassure used by the formulators of the theory of complexity in analysing various NP and P problems. The reason is very simple, it is that it is comparisons that take up most of the computers time in computing results. Each comparison is not just one cycle of the computer time instead it is many cycles depending on the different machines. An expanded answer to that is given in my previous posting in Psudo Science replies. Please refer to that. One should know the inner working of a computer to understand that I believe.

Mathew Cherian

Mathew, submit your findings. Stop wasting your time with us and go give them your millennium problem solution. If they approve then you deserve the right to inform us.

If they disagree then you know something is wrong and can fix it.

The only reason you would not show your solution to Clay Mathematics is because you are scared of the future. You are probably scared of their denial and effectively your time wasted.

Please submit your findings. Its the only way to know for sure if you are correct.

Is this the issue? That you can't count? Matthew, if you start at a given city and then don't care where you end up, there are (n-1)! possible paths. You have n-1 choices for the first city you go to, n-2 for the next, n-3 for the next, etc., until you're at the last city. This is (n-1)!. Not n²-n. If the latter were the case, the problem would have been solved long ago.

Table for one set tour

I 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

5 5 5 5 5

1 3x4=12 3x2=6 2x1 =2 = 21- 1 =20 < n²

Now I cannot draw an arrow in this window. You can do this by yourselves.
You take starting city 1 column 1 to 2 in column 2 .
From 2 in column 2 an arrow to 3,4 and 5 in column 3.
From 3 in column 3 to 4 and 5 in column 4
From 4 in 4th column to 5 in last column.

If you count the number of traverses it is given in the last row of the above table which is equal to 20 < n²
Since there are 5 cities that make the number of traverses 20 x 5 = 100 which is not n!. n! is 120.
What I am saying is even if it is n! it doesn't matter since the ordered algorithm jumps to the next city for calculating the route cousts, without a comparison which won't slow down the computer. Once it finishes with one set of tour it increments as I have shown in the algorithm and psudo code. It still is O(N) where N= (n²) - n which is compared in each of traverse and stored. You can either compare as each data is formed or store it in an array and Quick sort both making it O(N).

I had tried to draw the arrows in Word and cut and paste on this small window but this is not accepting the arrows only the numbers, hence I ask you to draw the arrow and see for youselves.

Factorial sign is not the nemesis it is how we tame the number crunching by reducing comparisons which I explained previously to you. Just by seeing some number close to n! one need over conclude that the process is insurmountable.

The idea is rather than just jumping at random the problem is reduced to an orderly form for the computer in each step so that it won't crash or the program though is still complicated won't be that complicated if it is not ordered.

_______________________
Mathew Cherian [/img]

Mathew

I might be suffering from a language problem here, or genuinely, as may be the case, a maths deficiency. Please bear with me, therefore.

From the explanation you have given of this table, here's what I have taken out.

1. Order your cities from your named starting city in terms of the next nearest city to them. So 2 is the closest city to 1, 3 the closest city to 2 (except for 1), and 4 is the closest city to 3 (except for 2) and so on.

2. You therefore start seeking various possibilities of itineraries not from city 1, but from city 2 (1 to 2 possibility is only 1 since you are jumping there directly).

3. You 'fill out' this calculation by taking each city in turn and calculate the same number of possibilities (f(n-1), since the first step is a given).

Now there appear to be some issues here to deal with:

a. For each now starting city, given the qualifications mentioned in 1 above, you will have to take a new order. Suppose, for instance, that not only is 2 the closest city to 1, but 1 is also the closest city to 2. Then your second table will be 2 -> 1 and then from 1 to whichever city is second-closest to 1, and so on. Thus, each new table will require a new re-ordering process.

b. Once you take that re-ordering into account, the amount of work you do is not greatly reduced.

c. Most importantly, you have no assurance that starting with the nearest city to your starting point (going from 1 directly to 2) necessarily gives you the optimum route. In fact it might be the case (anyone?) that it is possible that no single starting city has, as its second step, the nearest city to it. Therefore your algorithm may well be incomplete - it does not exhaust the possibilities.

d. Finally, it is worth mentioning that when you show, as proof, the calculation 20 < n², it would be easier to evaluate the truth or otherwise of that statement if you, instead, showed the '20' in terms of n rather than as a number. It will help us, and you, predict its behaviour as n gets larger.

Don't know if I've interpreted your method correctly (or even if my maths is up to the job), but these appear to be some problems you may face.

cheer

shanks

Let me put it this way. Look into my table given above. In the first city first column you order it to 2 as the minimal cost from 1 , the second one you order it to 3 as the minimal cost from 2, the third on ordered to 4 as the minimal cost and 4th to 5th.
Now shuffle the whole matrix and Quick sort you will see the shortest route at the top row.
You can draw a graph out of it.


In my last posting I said there will be around 100 tours. It will be much lesser may be only close to 20 because of the sorting where we look for the minimal route from top down for each tour from that city.
_____________________
Mathew Cherian

Matthew, something is being lost here. I have no idea how you are choosing your paths, and you do not even begin to suggest why your set of paths must contain the minimal path. So, please, in very careful, precise language, explain:

1. the set of paths that your algorithm considers;

2. why the minimal path is in this set.

Do this in full generality, not just for the case n = 6.

This is not the first time I've asked you to do this. Your refusal to answer these questions is getting annoying.

C<space=4>H<space=4>B<space=4>M<space=4>P<space>

CB533 HP548 BM331 MB331 PH548

CM681 HB562 BC533 MC681 PB625

CH1095 HM688 BH562 MH688 PM1166

CP1221 HC1095 BP835 MP1166 PC1221a

In the above table take a data say CB533 which means tour from C city to B city costs 533. Now suppose C is the starting city.
Here the table is sorted.
CB533 is the minimal cost. Underline this data and place 533 next to C and star it.
Now this data points to B go to B column.
Here check up the first data see where it is going. If it is going back to C ignore this data and go to the next highest data. Since the first data is not going back to C we can choose this as our candidate. It is BM331 which mean from B city to M city. Underline this city add it’s cost to the first starred cost and place it next to B and star B.
Move to M column since that is where minimal cost from B is pointing to.
Here again first data is already traversed second data is already traversed so third data is the candidate which is MH688. Do the underlining and adding and starring this column.
Now you go to the H column where because that is where the previous tour points to.
Here again the first data satisfies the candidature requirement of not having the end city not traversed before and which is minimal, which is HP548.
Underline this data and add this to the previously got sum (in column M ) put it next to H in row 1 and star it to mark it as traversed.
Now this shows that the next and last city is P from HP548 and go to that column.
Which finishes the 5 city tour. The data in H star is the minimal cost.

Actually this gives the minimal tour for this graph where I have chosen actual data.
For general cases we can modify by reinitializing( by removing stars and underlines and sum) the table above after each tour and starting at the same city with a next city other than the city chosen in the first tour.

Even for more complicated tours we can even do exhaustive searches by keeping the second city also constant along with the first city and traversing combinations of other cities.

In my experience(limited of course for lack of facility adequate) the las two types of searches are unnecessary for any type of graphs unless one creates a random graph to just break the algorithm in which case the last two types of searches will nullify the problem.

Now your question why I feel the just one search produce the result or my rational.

Rational: The data is sorted in ascending and in the first search we pick up all the minimal routes all others are above this route.

_______________________
Mathew Cherian

I won't be able to make explanations beyond this. I suggest you take my paper write down the table there without the underlines and stars and work out the algorithm as I have given above. You will find that the minimal cost appears in one search which is 2100. If you try others you will see that others are all above this. You should do the underlining and marking stars and adding exactly as I have desribed.

You can still ask me doubts, I shall try to clear it as best as possible the only thing I ask you is do it manualy ones before asking.

________________
Mathew Cherian

Originally Posted by serpicojr

Do this in full generality...

Dude, I'm a mathematician. I'm not convinced by doing one example that you cooked up. I want to see your general algorithm.

If you have answered bacik without working out what I have writen there any type of algorithm I write may not be decipherable to you. Ones you work it out with underlines and stars and you create any kind of grpahs with your own weights added will work the way with the underline star sum algorithm I have designed in this work.

This problem is not simple as you can see and some people like Cambridge mathematicians has offered a price. If someone could just look at it and want to see how it works then it can only be a problem that everyone can solve, in which case this prize wouldn't have been there in the first place.

I have heard of Mathematicians who can read english. Hopefully you wil take it in lighter sense, hope you know what I mean. If you want to know this the only way you can do is working this simple example out ones. Then the general case will follow when you create your own graphs eiven to n cities you can choose n then. Otherwise I don't know how to teach you this, since this algorithm is already there in my paper. I have expanded it for you to work out this with a pen and paper. Please do it and ask Mathematician or not.

___________________
Mathew Cherian

I have heard of mathematicians who can write English.

Mathew

Your further explanation seems to me to demonstrate that my earlier interpretation was not far off.

Your method

1. Measure all the distances between each pair of towns. If there are n towns, this number is (1 + 2 + ... + n-1).

2. For each town, create its own table of distances for single journeys. There are n tables, each containing n-1 items.

3. Arrange each table in ascending order (in terms of distance). I believe there is another thread (either on this topic or...) in which serpicojr showed how many steps the ordering takes.

4. For any given start point, you choose the nearest town to it. You do not have to 'check' anything here so the available choices are exactly 1.

5. For any subsequent town chosen, next choose the nearest town that has not so far been chosen. Each table will have to be checked up to m-1 items, if the town being checked is the mth town to have been chosen. The maximum checking you have to do, therefore, for any total route, is the number in 1 above.

6. So far so good. You have an algorithm for generating routes. It does not, from what I can tell, increase in polynomial time.

7. Here's the problem. Your algorithm literally checks only n possible routes. In fact, it is incapable of generating more than 1 possible route per starting point.

8. You presume that you have nevertheless, using this algorithm, generated the most efficient route. Or at least unless towns are deliberately chosen to break the algorithm.

9. There is no evidence (from what I can see) that your algorithm is, in fact, efficient in this way. Further, you have provided no calculations regarding what percentage of possible networks could break your algorithm. Unless you can estimate this, you can have no idea as to whether or not they are significant. The number of totally possible routes is, I believe, (n-1)! , so there are many you haven't checked: what guarantees do you have?

Now I appreciate that my maths is crude, some of my assumptions may be wrong, and that I may be misinterpreting you in some way. For this, I apologise.

But... unless you can address (or have already done so in a way I missed), my points 7 to 9, I cannot believe that you have been successful in your aim.

Regards

shanks

PS: Serpico - please correct any mistakes you see.

To Sunshine warrior and Serpicojur,

You don't seem to understand. I shall explain it in simpler for one more time.

I hope you know how a matrix is created the determinent type with columns and rows. You convert your TSP graph into a matrix which I had given in my paper and replicated here above post.

Now you sort out each colum in ascending order. This means each number from top will be higher than the previous one above.
Each city has one column.

1)Now you take the (1,1) data item which is taken as the starting city. This will be a minimum since data is in ascending order. This data also contain a direction to a city.

2)Step into that city where it is pointing to and go to that column. Here we have data again in ascending order. You take the first data and see if it is already traversed. For example if you come from CB you should ignore BC if it is a minimum. Jump to the next data in the column tes if it is again traversed like above. Repeat testing data until you reach a non traversed city and consider that as the candidate. Add this data to the first data. Check where it is pointing to and go there and repeat 1) till all cities are finished.

In this you get the optimal ie; the minimal route in one traverse since all the routes selected will be above others and even if some cities are above when ignoring when tested for already traversed those cities will already be in our optimal path in a previous tour.

I use the underline, star and sum method so that one can mark cities as you go along traversing.

There are no n! or (n-1)! routes to be searched in this algorithm. There is only 1 and only one route traversed which will be the optimal route. If you can figure out what I wrote you will understand. Else I believe you will have to spend some time with the matrix and apply what I said slowly to get a feel. This is a new type of algorithm so I believe you will have to get used to the method. Don't get prejudiced by the conventional mathematics of factorial etc; in this algorithm. You have to start with a new mindset so that the method can be mastered and once you do that things will turn out to be easy.

___________________
Mathew Cherian

Dear Mathew

If your algorithm genuinely found the shortest route then what answers does it come up with for this problem?

Positions in x,y terms.

A = 0,0
B = 0,4
C = 3,4
D = -12,-5
E = -12,0
F = -3,4

Now I've used what I believe to be your method to calculate route distances that take in all these points once and only once.

Here are the distances I get using your method, from different starting points:

A = 28.92
B = 27.85
C = 26.85
D = 26.85
E = 29.73
F = 33.28

The routes, respectively, are:

ABCFED
BCAFED
CBAFED
DEFABC
EDFABC
FABCED

You could perhaps do the calculations yourself to confirm this.

The problem is that this is a simple example, not particularly subtle, yet I come up with two alternative routes for F as a starting point, both of which are shorter than yours.

FCBADE = 32.07

and

FCBAED = 31.07

I did not even have to do an exhaustive search, just used good old heuristic intuition.

Tell me what I have done wrong here.

cheer

shanks

sunshinewarrior: Good job! Maybe you'll convince Matthew that he has to look at more than just one data set!

Matthew! Matthew! Matthew! We've finally made a breakthrough! That is the most lucid post you've made yet! Congratulations! I understood what you said! Yay! See how effective it is to describe things in clear, precise, general language?!

Matthew! Matthew! Matthew! There's more to this breakthrough! We can now judge whether you're right or wrong! The jury says: you're completely wrong! That algorithm does not necessarily produce the optimal route! If it were that easy, people would have solved this eight million years ago and would be sipping drinks on the beach and the Clay Institute wouldn't even offer you a coupon to Bennigan's for solving it! But it's not that easy!

Look, sunshinewarrior was able to come up with a counterexample to your algorithm in like two seconds (okay fine a little over an hour)!

Even worse, consider the following:

Originally Posted by Wikipedia

The nearest neighbour (NN) algorithm (the so-called the greedy algorithm is similar, but slightly different) lets the salesman start from any one city and choose the nearest city not visited yet to be his next visit. This algorithm quickly yields an effectively short route.

...

For each n>1, there exist infinitely many examples for which the NN (greedy algorithm) gives the longest possible route (Gutin, Yeo, and Zverovich, 2002).

Your algorithm sometimes produces the WORST route! I'm sorry, Matthew, but that's pretty bad!

Back to the drawing board!

Oh, and your use of the word determinant in the context of matrices is also wrong.

Dear Shanks,

What you have proposed is not a Traveling Salesmans problem. It look like a Random walk problem specified in Cartesian co-ordinates. Cartesian co-ordinates is not the method by which Grpah theoretic problems are modeled.

Graph theoretic problems have Nodes and Places(edges). The edges are directed and carry a weigt. The places can be unidirectional or multidirectional.

TSP is a multi-directional graph theoretic problem. Each place has a weight. In TSP we call this weight the cost between routes.

So if you cannot convert your problem to Graph theoretic then my algorithm won't be of any use. Moreover even if distance between points in your case can be found out using Solid Geometry so if A(0,0) and B(0,3) then distance between A and B is Squrare Root (x2 - x1)² + (y2 - y1)² which is 9 so it is AB9. We have to convert all these points in this form and get a graph for the TSP before one can apply my algorithm which you haven't done.

Moreover there should be direction from each node which has to be calculated. I shall try to do it in future from your formula and let you know what happened. I think something is wrong with your interpretation and I shall see what it is. Only thing is give me a few days time.

Moreover there cannot be integers and the numbers cannot be so close which though is not a criterion for TSP, it will make it more easier to solve.
Also I see some points in the negative quadrants which is not allowed. I will check up and let you know give me a few days.

______________________
Mathew Cherian

Originally Posted by serpicojr

Look, sunshinewarrior was able to come up with a counterexample to your algorithm in like two seconds (okay fine a little over an hour)!).

Dear SerpicoJr,

I don't think Shanks came up with a counterexample let alone one has to check up whether it is valid TSP problem formulaltion. I shall do all the maths and see, if it produces any negative numbers, I will stop and let you know because we can work only in the 1st quadrant not in others.

If he gave me the graph in the form I prescribed it could have been figured out in short time. He expects me to calculate all the weights from Cartesian system converted to weights. I shall do that. If some weights are negative, then sorry I won't proceed and let you know.

Wikipedia progpagates only the state of the art of the present not of the future, so let us wait, when they include mine in theirs.

___________________
Mathew Cherian

Dear Shanks and Serpico jr,

I was writing down the numbers you threw at me and found that you are on the wrong track. If you say A and give a number then the formulation of TSP of yours is wrong. From this you bannot figure out whether my algorithm is wrong.

Even if we take it as the distance of A from (0,0) then is going toe be 0 not the double digit real number you gave.

I shall try to correct it forumulate a TSP from your number, use my algorithm and give you the result sometime in future.

Cheerio
______________
Mathew Cherian

Dear Shanks,

Let me quote your numbers,

A 0,0
B 0,4
C 3,4
D -12,5
E -12,0
F -3,4

The TSP Table I derived from this is as follows(SORTED), luckly I didn't get any negative weights. Moreover I feel it is a restricted case not a general case because there are lots of equal weights. In any case my algorithm works perfectly with this data.

AC5 BC3 CB3 DE5 ED5 FB3

AF5 BF3 CA5 DF9 EF10 FA5

AE12 BD12 CF9 DB12 EA12 FE9

AD13 BE13 CD15 DA13 EB13 FD9

AB16 BA16 CE16 DC15 EC15 FE10


Working up my Algorithm we see the shortest route is A-C-B-F-E-D=25

The next highest route is A-F-B-C-D-E=31. All other routes are above this.

So the assertions of Serpicojr and your worries are unfounded.

I have to say that you are all worried and prejudiced by so long years this problem remained unsolved and lots of gobledeguk has been incorporated into budding minds which they cannot leave it easily.
NB: Once Serpicojr called me that I cooked up the problem and now I have shown it works in the problem you posed. So,

Cheers

_____________________
Mathew Cherian

Originally Posted by Mathew Cherian

What you have proposed is not a Traveling Salesmans problem. It look like a Random walk problem specified in Cartesian co-ordinates. Cartesian co-ordinates is not the method by which Grpah theoretic problems are modeled.

This is a TSP: he let the vertices be points in the plane, took the complete graph on said points, and specified the weights to be the Euclidean distances between the points. It's a graph with weighted vertices. Its a TSP.

Graph theoretic problems have Nodes and Places(edges). The edges are directed and carry a weigt. The places can be unidirectional or multidirectional.

My understanding is that the asymmetric TSP ahs a trivial reduction to the symmetric TSP, so this point is moot.

if A(0,0) and B(0,3) then distance between A and B is Squrare Root (x2 - x1)² + (y2 - y1)² which is 9 so it is AB9.

Matthew: do the math. This would give you, using your horrid notation, AB3.

Moreover there cannot be integers and the numbers cannot be so close which though is not a criterion for TSP, it will make it more easier to solve.

The size of the numbers doesn't matter--multiply by a large number and suddenly the weights are large without changing the problem!

Also I see some points in the negative quadrants which is not allowed.

Sorry, but this is absurd, Matthew. Just translate the points into the first quadrant if you can't wrap your mind around the idea of points lying in other quadrants.

Now... Matthew... your arithmetic is completely wrong. The numbers you calculated aren't right. The actual table you should get is (rounding to 2 decimal places):

<pre> A B C D E F
A 0 4 5 13 12 5
B 4 0 3 12.04 12.65 3
C 5 3 0 15.03 15.52 6
D 13 12.04 15.03 0 5 9.06
E 12 12.65 15.52 5 0 9.85
F 5 3 6 9.06 9.85 0</pre>

So try it with these numbers. I tried out sunshinewarrior's solution and, unfortunately, it isn't a solution: I find the minimal path to be FBCADE, which is also the path your algorithm generates. Have no fear (or, perhaps in your case, have fear), though, because your algorithm fails when you start at A. The shortest path is ACBFDE with length 25.06. Your algorithm generates either ABCFDE or ABFCDE, each of which has length 27.06.

Wikipedia progpagates only the state of the art of the present not of the future, so let us wait, when they include mine in theirs.

Dude, the Wikipedia article, which references a refereed paper, says your algorithm is no good. Sunshinewarrior and myself just showed it's no good. It's no good.

I have to say that you are all worried and prejudiced by so long years this problem remained unsolved and lots of gobledeguk has been incorporated into budding minds which they cannot leave it easily.

Buddy, just because you don't understand something doesn't make it gobbledygook. When a majority of the participants of some discipline agree with a result that you don't understand, suddenly the burden is on you to understand it. You can ask for help, and people will gladly give it to you. But you don't have the right to dismiss it because you don't get it.

Alright. Correct me if I misunderstood the algorithm, but here's my try.

First, the graph:

Code:

\.A.B.C.D.E.F
A.0.1.2.3.4.5
B.1.0.1.2.3.4
C.2.1.0.7.2.3
D.3.2.7.0.1.2
E.4.3.2.1.0.1
F.5.4.3.2.1.0

Or in your notation:
AB1 AC2 AD3 AE4 AF5
BA1 BC1 BD2 BE3 BF4
CA2 CB1 CD7 CE2 CF3
DA3 DB2 DC7 DE1 DF2
EA4 EB3 EC2 ED1 EF2
FA5 FB4 FC3 FD2 FE1

Sorting the columns gives 6 routes:
A-B-C-D-E-F (Total 16)
B-A-C-D-E-F (Total 16)
C-B-A-E-F-D (Total 16)
D-E-B-F-A-C (Total 22)
E-D-F-C-B-A (Total 12)
F-E-D-C-B-A (Total 16)

So you would conclude that E-D-F-C-B-A is the optimal route, right? However, the route A-B-C-E-F-D has a total of only 10, meaning that your algorithm did not find the optimal route. If I didn't get your algorithm right, can you show, step by step, how you apply it to this graph?

Personally I have an algorithm that I thought was a step towards solving the NP-Complete graph coloring problem. The trouble was, I couldn't prove that it always gave the right answer. (I couldn't find a small counter-example to prove it didn't either.) Without that proof, I knew I couldn't claim that I had solved graph coloring. Without a proof (and there are atleast a few standard techniques for proving that a greedy algorithm works, and this would be classed as a greedy algorithm) you cannot say you've solved this problem.

Also note that a single counter-example completely disproves your claim. There are plenty of polynomial algorithms that work on most graphs or on a specific type of graph or gives an almost-perfect answer, but there is currently no polynomial algorithm that always works perfectly on all graphs.

Looks good to me. I'm curious what Matthew has to say...

Serpicojr,

Atleast I believe you have learned to walk through my Algorithm. You say my algorithm produces the shortest route is ABCFDE which is 27.06, Bingo you are right. Now you come up with another shortest route but that is a different starting city.

The problem stipulates that the starting city should be constant when solving the problem. If you choose different city to start with for same problem then it becomes a different problem.

Let me state the problem one more time. There should be a STARTING CITY. One can traverse a city only ones and you cannot step into a city no more than ones. You stop when all cities are covered.

I don't see anything wrong with my algorithm, you will also see it that way when you apply the directions of the problem properly.

There may be other shortest routes when the STARTING CITY IS ALTERED. Then it is a different problem altogether. One suggestion is do all the cities as starting city( which is not stipulated) and from the five soltutions choose the least cost route.

This suggestion doesn't prove that my algorithm is wrong. It works for such an unnecessary endeavour also, when the problem is expanded.

Usualy this is impractical because the Traveling Salesman starts from one city alway which may be the HeadQuarters of the company. If he has to go to another city to start then that will add up to the cost.

Formulating the problem your way will make the TSP table more ambiguous becuase traverse to the same city is given eventhough it is zero the programer will have to add additional code to complicate to circumvent this inclusion.

Algorithm is alright and is working to me.

_________________
Mathew Cherian

You know, in my last post, I was thinking of saying, "I bet Matthew will object to your [MagiMaster's] post because you don't have a starting city." But I decided I shouldn't jump the gun, that maybe Matthew wouldn't make such a silly criticism. I gave him the benefit of a doubt. I guess I was wrong.

Anyway, Matthew, notice that for my counterexample, I chose the starting city A. Your algorithm produces ABCFDE with length 27.06. But the true minimal path is ACBFDE with length 25.06. Open your eyes: these paths have the same starting city. I followed your conventions, and I still found a counterexample.

To MagiMaster:
I think you understood my Algorithm but violated the problem formulations. All your routes start at different cities which is an extension of the problem probably which if required or not is first of all to be ascertained.

In the answer to Serpicojr I have restated the problem please refer to that. One need to find only the shortest route from one single city as STARTING CITY. This should be kept in mind.

I accept the fact that this is not an easy problem, one forgets one thing when doing the other thing. All these things have to come together for a complete solution. I hope I made the idea clear.

Ones you keep a starting city and solve using my algorithm you will see that it works. The reason why I said your is an extenstion is explained in the above posting to Serpicojr, the HeadQuarters constraint.

I worked out you said 10 is the minimum route, I calculated ABCEDF=7 as the shortest route starting form A.

You need the step, please take it.

1)You specify a starting city.
2)There you take the minimum cost city which will be the top most in sorted column( in my type of table). Underline this city and mark the city in first row with a star and write down the cost there.
3) Move to the next city where this minimal cost is taking you to. Repeat 2 and either you mark the cost or add to the previous cost.

When you reach the last city either the sum on top of the city previous will be the minimal cost or if you add up the individual costs got it will be the minimal cost.

STARTING CITY, STARTING CITY, STARTING CITY please keep this constant to include the problem formulations. Your type of problem is just an extension and my view is expressed in my above posting for the same.

Cheerio!

_________________
Mathew Cherian

Alright. The normal statement of TSP says that the salesman must return to their starting city. So for ABCEDF, you would normally have to include the FA return distance, giving a total of 10. Also, if you're making a loop, the starting city should be inconsequential. (Rotating the points around the loop gives the same total for the loop.)

Since you say the starting city is important, I'll assume that you're talking about TSP where you don't have to make the return trip. In that case, I'm not sure how to apply your algorithm. Can you walk us through it step by step?

Originally Posted by serpicojr

<pre> A B C D E F
A 0 4 5 13 12 5
B 4 0 3 12.04 12.65 3
C 5 3 0 15.03 15.52 6
D 13 12.04 15.03 0 5 9.06
E 12 12.65 15.52 5 0 9.85
F 5 3 6 9.06 9.85 0</pre>

Serpico

I probably used the spreadsheet incorrectly, but my values were slightly different. Could you confirm this for me?

Basically, my A column matches yours, but the others don't. I have:

B = 4, 0, 3, 16.76, 16, 8.06

C = 5, 3, 0, 17.89, 16.28, 7.07

D = 13, 16.76, 17.89, 0, 5, 12.73

E = 12, 16, 16.29, 5, 0, 9.85

F = 5, 8.06, 7.07, 12.73, 9.85, 0

I belive I'd orginally specified D as -12, -5, and therein may lie the difference: since I've seen it quoted as -12, 5 elsewhere on this thread.

I'm still of the opinion (and your explanation of the way I'd set it up was spot on: of course it is trivial to add 20 to each number and put them all in quadrant 1 if necessary) that in my original formulation I genuinely found two routes that 'beat' Mathew's.

Again - you're better at this maths lark than I am, so I'll bow to your judgement on that one.

On a related note, it occurs to me that if the problem were re-stated as a 'loop' problem (ie, you have to return to start) then every network will necessarily have a single shortest loop. That is, the same loop would have to be used no matter which starting point you chose.

Further, it seems as though, for any given starting point, you should be able to use this loop to determine the shortest traditional (non-returning) route, by eliminating the longer of the two distances attached to whichever starting point you chose.

Is this correct?

MagiMaster,
The algorithm still works, the steps are same as the above I have given, I shall repeat it below.

1)You specify a starting city.
2)There you take the minimum cost city which will be the top most in sorted column( in my type of table). Underline this city and mark the city in first row with a star and write down the cost there.
3) Move to the next city where this minimal cost is taking you to. Repeat 2 and either you mark the cost or add to the previous cost

One reason why you cannot follow the algorithm is the way you represent the table. You include 0 weights for say A,A cities directing to itself. You can remove these cities and give directions along with the weights. This will help in finding the direction to which city from a minimal cost. Suppose if it is AB5 means graph is directed from A to B and the weight is 5. When you sort this direction go along with the weight.
If you sort a table without the direction then the weights will get misdirected wrong weights going to wrong cities.

In your case comparing with my above statement, if A is the starting city you will pick up 0,0 where as it has no direction except to itself which is an unnecessary route. If it is not there you will pick up the next directed route to start with. Keep this weight in ming or add it. See where it is going. If it is AB then go to B column, find the minimal route to which ever city. Add this weight to the previous weight. Go to the city pointed to by this minimal route and so on till last city is reached.

Some might require the looping back to the starting city, I am not sure. Commonsense tells us that this will make a second trip to the starting city. Moreover cities don't come in 5 in a cluster. There may even be 100's. So if I am not confusing you such a tour can be divided into many 5 city tours to complete, in which case going back to starting city will be a Dud direction. This happens later and we need not worry about it now. Violation is visible in such tours of going back or looping where one makes a second trip to starting city.

I think I had worked up the loop also, in which case my algorithm still works.

______________________
Mathew Cherian

Originally Posted by serpicojr

Anyway, Matthew, notice that for my counterexample, I chose the starting city A. Your algorithm produces ABCFDE with length 27.06. But the true minimal path is ACBFDE with length 25.06. Open your eyes: these paths have the same starting city. I followed your conventions, and I still found a counterexample.

Originally Posted by sunshinewarrior

I probably used the spreadsheet incorrectly, but my values were slightly different. Could you confirm this for me?

I'm sorry, I don't really have time today to check this. In any case, I don't think it matters to our criticism of Matthew's algorithm--all we have to do is specify numbers, and it doesn't matter if they come from geometry or not. It's just an added bonus if they do!

I'm still of the opinion (and your explanation of the way I'd set it up was spot on: of course it is trivial to add 20 to each number and put them all in quadrant 1 if necessary) that in my original formulation I genuinely found two routes that 'beat' Mathew's.

It's not an opinion, it's a fact.

On a related note, it occurs to me that if the problem were re-stated as a 'loop' problem (ie, you have to return to start) then every network will necessarily have a single shortest loop. That is, the same loop would have to be used no matter which starting point you chose.

Indeed this is true!

Further, it seems as though, for any given starting point, you should be able to use this loop to determine the shortest traditional (non-returning) route, by eliminating the longer of the two distances attached to whichever starting point you chose.

My intuition suggests this may not be true, but I'm not a graph theorist and my intuition isn't trustworthy in these sorts of problems. But my thinking is this: finding a short loop seems to nudge the solution in a direction so that the distances attached to the starting point are short, whereas finding a short path from said starting point only cares about the distance to the next city and not the distance from the starting point to the final city. As an illustration, consider the numbers that I used. Any short path starting at A, B, C, or F ends with DE or ED, I believe, because D and E are close to each other and far from everyone else, which themselves are close to each other. But if I took a short loop, either I could find a consecutive triple of guys from A, B, C, and F, or I would have D and E are separated by two points in any direction. In the former case, say I had the string ABC, then starting at B and deleting BA or BC would not give me the optimal path from B. In the latter case, D and E are not consecutive, which should always happen if I start at A, B, C, or F.

Originally Posted by serpicojr

Further, it seems as though, for any given starting point, you should be able to use this loop to determine the shortest traditional (non-returning) route, by eliminating the longer of the two distances attached to whichever starting point you chose.

My intuition suggests this may not be true, but I'm not a graph theorist and my intuition isn't trustworthy in these sorts of problems. But my thinking is this: finding a short loop seems to nudge the solution in a direction so that the distances attached to the starting point are short, whereas finding a short path from said starting point only cares about the distance to the next city and not the distance from the starting point to the final city. As an illustration, consider the numbers that I used. Any short path starting at A, B, C, or F ends with DE or ED, I believe, because D and E are close to each other and far from everyone else, which themselves are close to each other. But if I took a short loop, either I could find a consecutive triple of guys from A, B, C, and F, or I would have D and E are separated by two points in any direction. In the former case, say I had the string ABC, then starting at B and deleting BA or BC would not give me the optimal path from B. In the latter case, D and E are not consecutive, which should always happen if I start at A, B, C, or F.

Of course. Ta.

Arg. There was a power surge in the middle of me typing a long post, so here's the short version. :P

If I understood the algorithm right this time, and I don't think I do... (Mathew, walking us through an example would help everyone understand your algorithm much better). Anyway, how about this then:

Code:

Adjacency matrix:
\.A.B.C.D.E.F
A.0.1.2.3.4.5
B.1.0.1.2.3.4
C.2.1.0.1.2.3
D.3.2.1.0.1.2
E.4.3.2.1.0.9
F.5.4.3.2.9.0

Adjacency list:
AB1 BA1 CA2 DA3 EA4 FA5
AC2 BC1 CB1 DB2 EB3 FB4
AD3 BD2 CD1 DC1 EC2 FC3
AE4 BE3 CE2 DE1 ED1 FD2
AF5 BF4 CF3 DF2 EF9 FE9

Sorted adjacency list:
AB1 BA1 CB1 DC1 ED1 FD2
AC2 BC1 CD1 DE1 EC2 FC3
AD3 BD2 CA2 DB2 EB3 FB4
AE4 BE3 CE2 DF2 EA4 FA5
AF5 BF4 CF3 DA3 EF9 FE9

The first thing in the A column is AB1, so we go to B.
The first thing in the B column is BA1, but I assume we skip anything that has already been visited. So then next step would be BC1.
Then CD1, then DE1, then all that's left is EF9. The final path would be ABCDEF for a total of 13. However, the path ABCEDF gives a total of 7. Again, if I did something wrong, can you work the example out yourself so we can see how it's supposed to be done?

How can you say that it is a counterexample, when one hasn't tried out all the possibilities. My psudo code and my algorithm says all the possible outgoing cities should be tried out before the minimal route can be ascertained.

You should understand that this is required to include all the general cases like low weights, closer weights etc;.

Then you might ask me why I accepted it as shortest the 27.06. I will have to say I was busy with something, I came back and saw a posting, which I didn't even read whose it was, which I thought said the minimal route found out was 27.06. I went back made only one try and confirmed it. I didn't try out the other possibilities. Now I tried the other possibility and found that 25.06 is minimal.

My algorithm includes n searches even more to take into considerations the situations mentioned above. It will turnout to be O(n).

The message I tried to covey through this is that an ordered matrix with a well defined traverse algorithm can reduce the number of searches to reduce the complexity to O.

___________________
Mathew Cherian

My wonderfully intelligent fiancee came up with the most tremendous counterexample today at lunch. Kudos to her for its utter simplicity! So consider the follow diagram.



We're starting at Star City and we want to travel to all of the Boring Circle Cities. Let's assume that the 8 cities on top are laid out on a line, and each city is 1 mile from the city next to it. Let's assume that the Outlying Circle City, the one on the bottom, is 2 miles from Star City, and so let's naturally assume that Outlyig Circle City is (4+n²)^1/2 miles from the n-th Circle City to the right of Star City (we're just using Pythagoras here). Your algorithm would suggest this path:

Star City -> 1st Circle City -> 2nd Circle City -> 3rd -> 4th -> 5th -> 6th -> 7th -> Outlying Circle City

This is obvious. The length of this path is 7+(4+49)^1/2 > 7+49^1/2 = 14 miles. But a shorter path is:

Star City -> Outlying Circle City -> 1st Circle City -> 2nd > 3rd -> 4th -> 5th -> 6th -> 7th

This should be obvious, but note that the length of this path is 2+(4+1)^1/2+6 < 2+9^1/2+6 = 11 miles.

Argue your way out of this, Matthew, and I'll nominate you for the Oscar.

Okay, I was lazy this time, Matthew, just as you were last time. I didn't read your new post, the one in which you so gingerly fail to mention that it was I who provided a counterexample to your algorithm. You're right, you can fix up your algorithm to patch up this hole. But the point is that your algorithm, as you stated originally, is not correct.

So, Matthew, please, if you really think you've solved this problem, then provide an algorithm which takes into account all counterexamples--in other words, an algorithm which works in generality. The burden is on you. If you patch up your algorithm to fix the handful of counterexamples we've come up with, that's nice, but that doesn't prove that more don't exist. You have to show things IN GENERAL.

Serpicojr,

I thought about your question of yesterday and todays circle city problem. Let me answer the first one first.

In it you say you come up with 25.06 as the minimum. In my algorithm I have also stated in my post that there are 12 possibilities for the second city, 6 for the third city, 2 for the 4th and one for the last making it 20 possbile tours which takes care of you route.

Moreover if you try to break my algorithm by just reducing CD route to say 5 and finding another shorter route you will see that it will produce a tour of 21 (AFBCDE)which is even shorter. But the truth is this will again come into the purvey of the algorithm. How this happens again is in a chnaged network weight you will make other citiy tours also shorter. So such things won't pay.

For your fiances solution is wrong, first of all the route length is not 7+ ... in the first place it is just 7. In the second shortest route it will be more than 7 because of the obvious reason that you are traversing 8 cities which is more than 7 required. In fact the distance in the redundandant city tour will be 2+sq.rt of 5+7 which is obviously greater than 7. So it is not even shorter route let alone whether it is a valid tour due to a city beign toured more than once.

______________________
Mathew Cherian

For your fiances solution is wrong, first of all the route length is not 7+ ... in the first place it is just 7.

If you have 9 cities, then your trip must have 8 legs (i.e., trip from one city to the next). If each distance is at least 1, then the minimum length of a trip must be at least 8. In fact, a less wasteful version of the same argument shows you must get at least 9, since one of the distances is at least 2. Use your brain a little bit, Matthew. It does more than just make sure you don't forget to breathe.

In it you say you come up with 25.06 as the minimum. In my algorithm I have also stated in my post that there are 12 possibilities for the second city, 6 for the third city, 2 for the 4th and one for the last making it 20 possbile tours which takes care of you route.

First of all, I don't see how you got the numbers 12, 6, and 2. Shouldn't it be 5 for the second city, 4 for the third, 3 for the fourth, 2 for the fifth, with the last being uniquely determined? Second, ignoring that your numbers are wrong, how did you get 20 from your numbers? Shouldn't it be 12*6*2 = 144? It looks like you did 12+6+2=20. If you did, I've been biting my tongue, but I can't do so anymore: this is really stupid. When you make a bunch of choices, you multiply the number of possibilities for each choice to get the total number of choices, you don't add them.

Oh my Lord, Matthew, is that it? You think that the total number of routes is like n² because the sum 1+2+...+(n-1) is n(n-1)/2? Dude, it's not. It's (n-1)! routes. Matthew, it's this sort of junk--everything that I've discussed in this post--that makes me doubt you can even do basic math. You're not even capable of counting, so I have no idea how you can even think that you can solve the TSP.

Serpicojr,

Let me answer one by one.

About your fiances question first, if there were 9 cities then there will be 8 paths. In any case if you choose the second city as the outlier city then it cannot go to the 2nd city again in the top path, it has to go to the 3rd city else the problem criterion is violated. You go to the second city again which make the pathe 9 instead of 8.

The second question is why the second city has only 4 instead of 5. You start from a city say C, that is excluded in the second column(for easy understanding) otherwise it will be like violating the problem stipulation of not touring the city twice. Se if you go to B from C which is BC, in the second column you ignore CB which is a direction backward. That leaves only 4 cities. The next city has two cities to ignore the starting city and the next city toured. 4 x 3= 12 for the second city. Like that for each column.

Your thid question pertain to Bubble sort. It is,

n x n² - n(1+2+3+.....+(n-1) the whole divided by n.

You can see that the second term has a minus sign there which makes your arguement false.

_______________________
Mathew Cheiran

Originally Posted by Mathew Cherian

Serpicojr,

Let me answer one by one.

About your fiances question first, if there were 9 cities then there will be 8 paths. In any case if you choose the second city as the outlier city then it cannot go to the 2nd city again in the top path, it has to go to the 3rd city else the problem criterion is violated. You go to the second city again which make the pathe 9 instead of 8.

The second question is why the second city has only 4 instead of 5. You start from a city say C, that is excluded in the second column(for easy understanding) otherwise it will be like violating the problem stipulation of not touring the city twice. Se if you go to B from C which is BC, in the second column you ignore CB which is a direction backward. That leaves only 4 cities. The next city has two cities to ignore the starting city and the next city toured. 4 x 3= 12 for the second city. Like that for each column.

Your thid question pertain to Bubble sort. It is,

n x n² - n(1+2+3+.....+(n-1) the whole divided by n.

You can see that the second term has a minus sign there which makes your arguement false.

_______________________
Mathew Cheiran

Mathew

Are you saying that for each "traverse" you make, you check out ALL possible combinations resulting from it?

Otherwise I cannot see how what you say is making sense.

Regards

shanks

Sunshine warrior,

It can possibly be construed like that.

To elaborate, for the first City you start from, the second column will have 12 possibilities, the third 6 the fourth 2 and last 1.

Like this there will be 4 traverses for one city to each of the other cities making it altogether 80.

_________________
Mathew Cherian

Matthew, I'm done.

Originally Posted by Mathew Cherian

Sunshine warrior,

It can possibly be construed like that.

To elaborate, for the first City you start from, the second column will have 12 possibilities, the third 6 the fourth 2 and last 1.

Like this there will be 4 traverses for one city to each of the other cities making it altogether 80.

_________________
Mathew Cherian

but if they're ordered, surely it will be only one possibility each?