Voyageur de commerce

Links: notebook, html, PDF, python, slides, GitHub

Illustration du voyageur de commerce.

Instructions :

• éxecuter les deux premières lignes

• cliquer un peu partout pour ajouter des points

• exécuter l’avant-dernière cellule pour voir le plus chemin obtenu avec un algorithme très simple

• la dernière cellule vous donne les coordonnées des points

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.