tag:blogger.com,1999:blog-58764837845036635232012-02-16T06:49:14.594-08:00Traveling Salesman problemBOCUT Adrian Sebastianhttp://www.blogger.com/profile/11925094541682745312noreply@blogger.comBlogger11100tag:blogger.com,1999:blog-5876483784503663523.post-29230560449382963952009-07-01T07:49:00.000-07:002009-07-18T01:38:47.490-07:00This is an combined algorithm that produces all the roads on a graph and that can be used also for cost problems, not only for minimal cost, also for maximum cost road/cycle problems. <br />It is known that the Dijkstra algorithm can be applied only for the minimal road/cycle. <br /><br />Let’s consider the graph with 4 nodes given by the following matrix:<br />A = 0 1 1 0<br /> 1 0 0 1<br /> 1 0 0 1<br /> 0 1 1 0<br />If we want to determine the Hamiltonian circuits we can use a combination of two algorithms: Kaufmann and Strassen.<br /><br />Using the Kaufmann algorithm we obtain by calculus:<br /><br />L = 0 12 13 0<br /> 21 0 0 24<br /> 31 0 0 34<br /> 0 42 43 0<br /><br />L~ = 0 2 3 0<br /> 1 0 0 4<br /> 1 0 0 4<br /> 0 2 3 0<br /><br />L2 = L * L~<br /><br />From the Stassen algorithm we obtain:<br /><br />M1 = 123,341 0<br /> 0 214,432<br /><br />M2 = 341 312<br /> 421 432<br /><br />M3 = -123 124<br /> 213 214<br /><br />M4 = -341 342<br /> 431 -432<br /><br />M5 = 123 134<br /> 243 214<br /><br />M6 = 0 312,-124<br /> -213,421 0<br /><br />M7 = 0 134,-342<br /> -431,243 0<br /><br />C11 = 0 0<br /> 0 0<br />C12 = 0 124,134<br /> 213,243 0<br /><br />C21 = 0 312,342<br /> 421,431 0<br /><br />C22 = 0 0<br /> 0 0<br /><br />If we want to determine all the circuits with length 1->n, this algorithm is polinomial.<br />For each step – each Lk (the k-th power of L), using the Stassen algorithm we use k^(log2 (7)) steps; if we want to determine all the circuits we have to done S operation, where S = sum(x^i) with x from 1-n and i = log2 (7).<br />We can see an explanation of how to compute all these sums on:<br />http://mathforum.org/library/drmath/view/56018.html<br /><br />So, the algorithm Kaufmann-Stassen for determine the Hamiltonian circuits is of order O(n^x) where x = log2 (7) + 1.<br /><br />Bibliography:<br /><br />1.http://en.wikipedia.org/wiki/Strassen_algorithm">http://en.wikipedia.org/wiki/Strassen_algorithm<br /><br />2. www.asecib.ase.ro/Mitrut%20Dorin/Curs/bazeCO/doc/33Grafuri.doc<br /><br />3.http://mathforum.org/library/drmath/view/56018.html<br /><br />The hamiltonian cycles on a graph can be determined by combining the two algorithms:<br />Yu-Chen - Latin matrix and the Strassen product of matrices. In this case the algorithm will be faster than the classic method using the DF visiting method.<br /><br />This algorithm can be used for the robots that produce PCBs; instead of using only one "hand" the robot can use more "hands" and can begin for multiple corners.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5876483784503663523-2923056044938296395?l=bocut-graphs-appl.blogspot.com' alt='' /></div>BOCUT Adrian Sebastianhttp://www.blogger.com/profile/11925094541682745312noreply@blogger.com0