----------------------------------- ilya.gazman Sun Oct 13, 2013 11:59 am Found exact solution for TSP ----------------------------------- Hi, My name is Ilya Gazman. I found an exact solution for Traveling salesmen problem. Currently the best implementation according to in the attached file you can find java code that implements it). N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... N Now lets solve this efficient algorithm with N from 7 to 100, and compare it to the previous results(result of N = 9 with N =8, result of N = 24 with N = 23). I found out that for big numbers of N the comparison result is 2. Then I did the same with the traditional dynamic programing algorithm efficiency. Here is the list of what I got: [code] 7 2.55769 2.72222 2.98397 8 2.40601 2.61224 2.74973 9 2.31562 2.53125 2.60507 10 2.2582 2.46913 2.50912 11 2.21972 2.42 2.44169 12 2.19258 2.38016 2.39191 13 2.17251 2.34722 2.35356 14 2.15701 2.31952 2.32293 15 2.14456 2.29591 2.29774 16 2.13424 2.27555 2.27652 17 2.12548 2.25781 2.25832 18 2.1179 2.24221 2.24248 19 2.11124 2.22839 2.22853 20 2.10533 2.21606 2.21614 21 2.10003 2.205 2.20503 22 2.09525 2.19501 2.19503 23 2.09091 2.18595 2.18596 24 2.08696 2.17769 2.17769 25 2.08333 2.17013 2.17014 26 2.08 2.1632 2.1632 27 2.07692 2.1568 2.1568 28 2.07407 2.15089 2.15089 29 2.07142 2.1454 2.1454 30 2.06896 2.1403 2.1403 31 2.06666 2.13555 2.13555 32 2.06451 2.13111 2.13111 33 2.0625 2.12695 2.12695 34 2.0606 2.12304 2.12304 35 2.05882 2.11937 2.11937 36 2.05714 2.11591 2.11591 37 2.05555 2.11265 2.11265 38 2.05405 2.10956 2.10956 39 2.05263 2.10664 2.10664 40 2.05128 2.10387 2.10387 41 2.05 2.10125 2.10125 42 2.04878 2.09875 2.09875 43 2.04761 2.09637 2.09637 44 2.04651 2.0941 2.0941 45 2.04545 2.09194 2.09194 46 2.04444 2.08987 2.08987 47 2.04347 2.0879 2.0879 48 2.04255 2.08601 2.08601 49 2.04166 2.0842 2.0842 50 2.04081 2.08246 2.08246 51 2.04 2.0808 2.0808 52 2.03921 2.0792 2.0792 53 2.03846 2.07766 2.07766 54 2.03773 2.07618 2.07618 55 2.03703 2.07475 2.07475 56 2.03636 2.07338 2.07338 57 2.03571 2.07206 2.07206 58 2.03508 2.07079 2.07079 59 2.03448 2.06956 2.06956 60 2.03389 2.06837 2.06837 61 2.03333 2.06722 2.06722 62 2.03278 2.06611 2.06611 63 2.03225 2.06503 2.06503 64 2.03174 2.06399 2.06399 65 2.03125 2.06298 2.06298 66 2.03076 2.06201 2.06201 67 2.0303 2.06106 2.06106 68 2.02985 2.06014 2.06014 69 2.02941 2.05925 2.05925 70 2.02898 2.05839 2.05839 71 2.02857 2.05755 2.05755 72 2.02816 2.05673 2.05673 73 2.02777 2.05594 2.05594 74 2.02739 2.05516 2.05516 75 2.02702 2.05441 2.05441 76 2.02666 2.05368 2.05368 77 2.02631 2.05297 2.05297 78 2.02597 2.05228 2.05228 79 2.02564 2.05161 2.05161 80 2.02531 2.05095 2.05095 81 2.025 2.05031 2.05031 82 2.02469 2.04968 2.04968 83 2.02439 2.04907 2.04907 84 2.02409 2.04848 2.04848 85 2.0238 2.0479 2.0479 86 2.02352 2.04733 2.04733 87 2.02325 2.04678 2.04678 88 2.02298 2.04624 2.04624 89 2.02272 2.04571 2.04571 90 2.02247 2.04519 2.04519 91 2.02222 2.04469 2.04469 92 2.02197 2.04419 2.04419 93 2.02173 2.04371 2.04371 94 2.0215 2.04324 2.04324 95 2.02127 2.04277 2.04277 96 2.02105 2.04232 2.04232 97 2.02083 2.04188 2.04188 98 2.02061 2.04144 2.04144 99 2.0204 2.04102 2.04102 100 2.0202 2.0406 2.0406 [/code] Column 1 is N, column 2 is my algorithm efficiency compare, column 3 is dynamic programming algorithm compare and column 4 is my algorithm efficiency multiply N compare. See how column 3 and 4 are almost the same. This is how I found it. Please verify my work, take a look at the code, tell me if you agree or not with me. If not please show me where my algorithm or my math is not working by exact sample. ----------------------------------- Tony Sun Oct 13, 2013 1:07 pm RE:Found exact solution for TSP ----------------------------------- According to that wikipedia page, the current best exact algorithm is Concorde TSP Solver, although it doesn't cite algorithm's runtime complexity. Held?Karp algorithm is just an example of "One of the earliest applications of dynamic programming" to this domain.