Illustration du voyageur de commerce.
Instructions :
L'algorithme en question est très simple : on permute deux points au hasard jusqu'à ce que cela n'améliore plus. Il est très mauvais quand il y a beaucoup de points et le résultat change quasiment à chaque fois qu'on le relance.
import code_beatrix
from code_beatrix.ipythonhelper import display_canvas_point
%load_ext code_beatrix
import code_beatrix.automation.notebook_const_helper as const
points = const.voyageur_de_commerce_points()
display_canvas_point("tspchart", var_name="points")
[]
%pylab inline
Populating the interactive namespace from numpy and matplotlib
from code_beatrix.algorithm import voyageur_commerce_simple, plot_circuit
points = voyageur_commerce_simple(points)
plot_circuit(points, figsize=(12,6))
<matplotlib.axes._subplots.AxesSubplot at 0x8d78278>
points
[(173.06666564941406, -108.68331909179688), (192.06666564941406, -174.68331909179688), (173.06666564941406, -207.68331909179688), (184.06666564941406, -224.68331909179688), (288.066650390625, -169.68331909179688), (338.066650390625, -100.68331909179688), (459.066650390625, -85.68331909179688), (573.066650390625, -93.68331909179688), (642.066650390625, -122.68331909179688), (639.066650390625, -166.68331909179688), (598.066650390625, -168.68331909179688), (460.066650390625, -160.68331909179688), (365.066650390625, -159.68331909179688), (324.066650390625, -243.68331909179688), (470.066650390625, -236.68331909179688), (610.066650390625, -255.68331909179688), (630.066650390625, -308.6833190917969), (601.066650390625, -326.6833190917969), (534.066650390625, -333.6833190917969), (377.066650390625, -319.6833190917969), (286.066650390625, -312.6833190917969), (229.06666564941406, -311.6833190917969), (184.06666564941406, -332.683349609375), (142.06666564941406, -352.683349609375), (78.06666564941406, -355.683349609375), (60.06666564941406, -311.683349609375), (60.06666564941406, -228.68333435058594), (63.06666564941406, -144.68333435058594), (60.06666564941406, -109.68333435058594)]
Pour vous inspirer, vous pouvez regarder code de la fonction voyageur_commerce_simple.