search

rika77 / google-step-tsp

0 stars 0 forks source link

Chatting(any comments are welcome !) #2

Open rika77 opened 6 years ago

rika77 commented 6 years ago

I removed a.out and added "a.out" to .gitignore https://github.com/rika77/google-step-tsp/commit/32c4711da671a8de03411a0729cf7e1cc9f8564b#commitcomment-29464444

hayatoito commented 6 years ago

ないす。

rika77 commented 6 years ago

at first, I made all-search program using "next_permutation". This can solve the problem only when N=5 and N=8. (it may be solved when N=16, but it takes too long time)

https://github.com/rika77/google-step-tsp/blob/master/rika/all_search.cpp

rika77 commented 6 years ago

next, I implemented "Nearest Neighbor Method". This can solve all problems, but the trip length is long. The outputs are all the same with sample/greedy...

https://github.com/rika77/google-step-tsp/blob/master/rika/nearest_neighbor.cpp

jachline28 commented 6 years ago

Thank you rika for the code. I'm sorry that I'm busy with my research projects these days so I haven't started writing the codes. I will start from Tuesday and probably can finish by Wednesday. Also, I'm thinking of implementing minimum spanning tree if I can :)

rika77 commented 6 years ago

Thanks, Jackie.

I implemented "Nearest Insertion Method", "2-opt" and "3-opt". 3-opt is the best, but still far from "the best score in the last year"

I'm looking for your code of minimum spanning tree! :)

rika77 commented 6 years ago

Sorry for Jackie. Cause I have a time, I tried to implement Minimum Spanning Tree, but still it doesn't work. Need Debug. https://github.com/rika77/google-step-tsp/blob/master/rika/mst.cpp

jachline28 commented 6 years ago

Don't say sorry, I'm the one that didn't successfully implement MST QQ... I'm still trying, but it's kind of really hard :-/