So, graph theory was firstly (and mainly created because of that actually) used in economy. Indeed, it allows, for example, to find the shortest path to go from one city to another. So, let's show how it works. :) 120 : angle of the shortest path between three points. The length of the shortest road between three cities is obtained like this : you draw three points A, B and C in the plane and now, the aim is to find a fourth point (let's call it D) which is placed such that : m(CDB) = m(BDA) = m(ADC) = 120\uffff where m(stuff) denotes the measure of the angle "stuff" (in degrees) so, come on, take a piece of paper, a pen, and start drawing ;) let me know when you get it 10 years and 4 failed calculus courses later... :) erm.. allow me to ask for some.. clarification what exactly is it that you want us to do? :P I mean, alright, points A, B, and C. Randomly drawn. oh we're supposed to do something? draw three points the traveler salesman problem? yes P = NP? ;) well, a special case of it ;) yep it was my passion for like 2 years eh.. lol haha, no, I am not going to prove (or disprove) P = NP tonight :p and, I don't want to hear : i can guess it xD P = NP <==> P - NP = 0 <==> P(1 - N) = 0 <==> P = 0 or N = 1, q.e.d. ;) that was my first thought as well lol haha :) So, did you get the case n=3 points? Can this be done for any three points? yes :) well it is true if each of the angles of the triangle ABC is less than 120\uffff, to be precise. (only if) less? argh ehh wait.. Oh ah.. nvm. xD :) so, got it? ... ok I believe this will REALLY help you : http://www.utdanacenter.org/mathtoolkit/downloads/geoassess/geo_2_steiners.pdf take 5 mins. to look at it then, tell me when you're done for those who think they got the case n=3, have a look at : http://www.delphiforfun.org/Programs/traveling_salesman.htm now, if you think this is still too "childish" for you : http://en.wikipedia.org/wiki/Traveling_salesman so, by now, as soon as you're done with reading and/or understanding, let me know I miss my triangle.. so, did you have a look at this chapter about the Steiner's point? humz.. the quickest way would be to print a dot and 3 lines each 120 degrees with the dot, then just shove the paper around and rotate till it fits. >_> Till it meets the requirements noted earlier. Where is my geometry triangle.. I read it alright but I can't even answer the first problem in scaffold questions mmk well, look at the solution and then you'll try to solve the second problem by yourself oh, you said the 'scaffolding questions'.. in this case, don't worry as long as you managed to understand how to draw the point D and noticed that it is indeed the shortest point (I mean, intuitively) then it's alright! ;) so, are you all done with reading? Ok, I'll go on. Now that we've seen the case with 3 points, guess what we are going to study? :) cases with n points? not that quickly simply : n=4. So, we have a quadrilateral ABCD. Ouch, long word.. haha :) you mean a plane right? ? you dont know what a quadrilateral is? Daedalus, he means a four-sided shape :P quadrilateral : polygon with 4 sides and four vertices a polygon with 4 sides that thats grade 3 geometry lol yeah, a plane. xD err no? a plane is an infinite surface For me it is.. mmm where do you come from? (if I may ask) netherlands The netherlands. *points to IP* okay And i'm in the "highest" class of education but I'm still feeling stupid. and how do you say so in Dutch? (if I'm not wrong with the language :-/) vierkant. (fourside) viereck in german I thought. *-) well from what I know, a vierkant (or kwadraat) is just a square meaning that the 4 sides are equal and the 4 angles each 90 degrees. yeah that's right.. but a plane is a vlak. what I'm talking about is a : vierhoek ah. now, it's talking? :) yeah continue.. okay ;) So, we take a point E in the center of the quadrilateral. With E and two of the points we look for the triangles whose angles are less than 120\uffff, so we are back to our previous case. ;) You have to adjust E little by little. ok? yes.. alright, now I will let you all finish to read all the links I mentioned. ;) the lecture will be continued in (more or less) 10 mins. for those who have already read it all, consider it as a little free time! ;) :qwertydawom!qwertydawo@bu-61EE8C6D.fbx.proxad.net TOPIC #lecture :Lecture going on. - Read! :p - 10 mins. until we go on. That computer beats me by far. The TSP program 2000 miles.. i wasn't too far off this time th *tho Just pick the points that are closest to each other each time. :D We got the same result for 20 cities. :D hehe :) but that has little to do with the actual math behind the program.. >_> yes lol So, let's go on. ;) :qwertydawom!qwertydawo@bu-61EE8C6D.fbx.proxad.net TOPIC #lecture :Lecture going on. Let us now study the "Traveling salesman problem". How to minimize the path of our salesman going from city to city. ?* easy, from the starting dot, calculate the distance of each next city, then pick the one that's closest. *dot == city This problem seems pretty easy, eh? it seems? :| It isn't? nope it's NP Damn hey my method works okay as well. >_> Well, it becomes extremely complicated when the number of cities increases. Let us illustrate the problem. That's why the exhaustive search takes so long. *-) With my car, I say I can take back two of my friend -adrian and bot- to their home. I begin with adrian, and then bot, or the contrary. Then, the day after, I also propose it to Ch4r. what? oh k In the first case, there were two locations, 2 possibilities. Now that I propose to take Ch4r back too, *adrian then bot then Ch4r 3! = 6 ;x *adrian then Ch4r then bot *bot then adrian then Ch4r yes Ch4r ;) so, end the list! :) *bot then Ch4r then adrian *Ch4r then bot then adrian *Ch4r then adrian then bot exactly. :) So, we have 3 locations, 6 possibilities. The explanation (of this 6) : 3 choices for the 1st location 2 for the 2nd one and only one for the last one : 3*2*1 = 3! = 6. And then, the week after, Daedalus comes with us. yeey *adrian then bot then Ch4r then Daedalus *adrian then Ch4r then bot then Daedalus Save the typing, I think we get this part, is it really important? *etc. lol nvm. xD :) So : 4 locations 4! = 4*3*2*1 = 24 possibilities (no, I wasn't going to write them all! :P) 4*3*2= 24 options. yep :) 120, 720, (4900+140).. And now, say I want to take 10 people back.. (it appears that my car is in fact a BIG car.. :P). hahaha 10 locations It increases drasticly 10*9*...*3*2*1 = 3628800 possibilities .... Sweet and with 100 people (do I have a plane or what? :P) lol it really goes high.. 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 100! = 0.933*10^(158) possibilities o_O hahaha thank you Ch4r for the exact value :) You also got a lot of friends btw. np ;) You also got a lot of friends btw. --> haha, yes :) To have an idea of what this incredibly big number represents : even with the maximum velocity of the computers nowadays let's say 1 nanosecond to examine one possibility it will need 10^(158) ns to examine them all, that is 10^(149) seconds. there are almost 10^7 seconds in a year so, it will take 10^(142) years the age of the universe is almost 10^(10) years so, it will take 10^(132) times the age of the universe OMFG! :) lol nice so essentially, another 10-20 big bangs will happen till all possibilities are explored != :)* so, well, if I decide to take back the 157 members of BU, hehe.... Now, you're probably interested in knowing the solution to this problem, aren't you? I'm very curious, and hoping it doesn't involve really hard math, because i'm kinda bad at it. ACTION nods :P Well, the solution giving the optimal path to our salesman is NOT simple. During the past centuries, guides were published to help to organize the tour. In fact, a general solution for any number of locations or any lengths between the steps is not known at the moment I write this. Here, I will show you a possible method : Our salesman wants to go through each dot of the tour, in fact : via the shortest path, without going twice at the same place What's the shortest path passing through all these points? Let us assume the points are the vertices of a parallelepiped in n dimensions. We denote the vertices by 000...00, 000...01, 000...10, etc. So, in 2D, with 4 points, the vertices would be : 00, 01, 10, 11 in 3D, with 8 points : 000, 001, 011, 010, 110, 111, 101, 100 gray code We organize the lengths of the parallelepiped from the greatest to the smallest, and we begin with the vertice 000...00. We can do this without loss of generality. *vertex yes, vertex, sorry ;) dw, it's the part i got. ;) The solution is unique. It consists, for the salesman, to go from one vertex to another using the Gray code, like you noticed! ;) Adleman managed to build an ADN computer who solve one version of the traveling salesman problem. The ADN computer needed one week, while a classic computer would have needed years.. but this was just for one problem? oh, by the way : ADN = DNA* Daedalus, you can have a look at (just the beginning) : http://web.cecs.pdx.edu/~mperkows/temp/June16/dna2.pdf So, now, let's introduce the notion of "polynomial problem" 1/ Sorting problem. Sorting 1000000 objects should take about 1000 times more than sorting 1000 objects. In fact, the simplest sorting programs take a time proportional to the square of the number of articles to be sorted. The theoricians of the complexity were able to show that the quickest possible sorting program would require a number of steps proportional to the number of objects, multiplied by its logarithm. (For those who are already confident with this idea of complexity, it means, that, if we have n objects, the simplest algorithm has a complexity of O(n^2) while the 2nd one has a complexity of O(n*ln n)) 2/ Polynomial problem. The problems whose solution can be computed in a time at most proportional to a given power of the size of the problem are said to be of polynomial type, or P. Nowadays, with the computers, they are considered as easy. 3/ The T.S.P. Find the shortest path to visit once and only once a set of given cities. The best exact solutions found are tantamount to make the program examine almost all the possible paths. The number increases exponentially with the number of cities. (see the solution above) 4/ Non-deterministic problem To solve the problem of the salesman, we can imagine a computer which would be able to browse simultaneously all the possible paths. When arrived at a "crossroad", the machine separates into two parts and browses simultaneously the two paths. Then, this machine could solve the problem in a polynomial time. These problems are said to be NP. The connection of the components on a circuit is of this type. Same goes for the automatic reasoning. 5/ Practically speaking : We have never been able to transform a NP problem into a succession of problems of type P. We always proceed with approximative methods which do not guarantee the quality of the answer at all, and which are sometimes really.. sucking. This problem to know if, yes or not, P = NP is still open, and if you can prove or disprove it, you can win $1 million as it is one of the seven Millenium problems. (cf. http://www.claymath.org/millennium/) And, I will let you meditate on this, as this lecture now comes to its end. :)