Build@Mercari 2020 Week4 - Travelling Salesman PRoblem Challenges.
This is forked from https://github.com/hayatoito/google-step-tsp-2016.
2-optによる近傍探索を行い実装しました。challenge5においては、近傍探索を100や50回繰り返したところKeyboardInterruptになってしまったため、1回としています。
-
問題 巡回セールスマン問題 を解くアルゴリズムを考えてください。
-
課題
このrepositoryを自分のgithubにforkして使ってください。 N = 5 から N = 2048までの7つの課題があります。
Challenge | N (= the number of cities) | Input file | Output (Solution) file |
---|---|---|---|
Challenge 0 | 5 | input_0.csv | solution_yours_0.csv |
Challenge 1 | 8 | input_1.csv | solution_yours_1.csv |
Challenge 2 | 16 | input_2.csv | solution_yours_2.csv |
Challenge 3 | 64 | input_3.csv | solution_yours_3.csv |
Challenge 4 | 128 | input_4.csv | solution_yours_4.csv |
Challenge 5 | 512 | input_5.csv | solution_yours_5.csv |
Challenge 6 | 2048 | input_6.csv | solution_yours_6.csv |
inputとoutputの形式については 3. Data Format Specification を見てください。
- 巡回セールスマン問題をとくアルゴリズムを考えて実装してください。
solution_yours_{0-6}.csv
をあなたのアルゴリズムでといた結果で上書きしてください。- あなたの解法のpath lengthをscoreboardに書いてください
What matters in this optional task is your program's speed (execution time). The path length does not matter as long as it meets the condition. Your task is:
- Given
input_6.csv
, write a program which outputs a path shorter than47,000
Input your program's execution time in the scoreboard. Faster (smaller) is better.
You can measure the execution time by time
command.
$ time yourprogram input_6.csv solution_yours_6.csv
2.96s user 0.07s system 97% cpu 3.116 total
In this case, your score is 3.116
(s).
The demo page of the visualizer is: https://mercari-build.github.io/week4-tsp/visualizer/.
The assignment includes a helper Web page, visualizer/index.html
, which
visualizes your solutions. You need to run a HTTP server on your local machine
to access the visualizer. Any HTTP server is okay. If you are not sure how to
run a web server, use the following command to run the HTTP server included in
the assignment. Make sure that you are in the top directory of the assignment
before running the command.
./nocache_server.py # For Python 3
./nocache_server.py2.py # If you don’t want to install Python3
Then, open a browser and navigate to the http://localhost:8000/visualizer/. Note that visualizer was only tested by Google Chrome. Using the visualizer is up-to you. You don’t have to use the visualizer to finish the assignment. The visualizer is provided for the purpose of helping you understand the problem.
- Data Format Specification
The input consists of N + 1
lines. The first line is always x,y
. It is followed by N
lines, each line represents an i-th city’s location, point xi,yi
where xi
, yi
is a floating point number.
x,y
x_0,y_0
x_1,y_1
…
x_N-1,y_N-1
Output has N + 1
lines. The first line should be “index”. It is followed by N
lines, each line is the index of city, which represents the visitation order.
index
v_0
v_1
v_2
…
v_N-1
Input Example:
x,y
214.98279057984195,762.6903632435094
1222.0393903625825,229.56212316547953
792.6961393471055,404.5419583098643
1042.5487563564207,709.8510160219619
150.17533883877582,25.512728869805677
Output (Solution) Example:
index
0
2
3
1
4
These formats are requirements for the visualizer, which can take only properly formatted CSV files as input.
- What’s included in the assignment
To help you understand the problem, there are some sample scripts / resources in the assignment, including, but not limited to:
solver_random.py
- Sample stupid solver. You never lose to this stupid one.solution_random_{0-6}.csv
- Sample solutions by solver_random.py.solver_greedy.py
- Sample solver using the greedy algorithm. You should beat this definitely.solution_greedy_{0-6}.csv
- Sample solutions by solver_greedy.py.solution_sa_{0-6}.csv
- Yet another sample solutions. I expect all of you will beat this one too. The solver itself is not included intentionally.solution_wakanapo_{0-6}.csv
- Sample solutions I solved when I was joined Google STEP 2016.solution_yours_{0-6}.csv
- You should overwrite these files with your solution.solution_verifier.py
- Try to validate your solution and print the path length.input_generator.py
- Python script which was used to create input files,input_{0-6}.csv
visualizer/
- The directory for visualizer.
- Acknowledgments
この課題は私がgoogle step 2016に参加したときにやったものです。問題のわかりやすさ、visualizerによるアルゴリズムのみやすさ、楽しさなどにおいてこれを上回る課題はないと思ったので、Build@Mercariでも採用することにしました。