.. _voyageurdecommercerst: ==================== Voyageur de commerce ==================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`PDF `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/algorithmes/voyageur_de_commerce.ipynb|*` 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. .. code:: ipython3 import code_beatrix from code_beatrix.ipythonhelper import display_canvas_point %load_ext code_beatrix .. code:: ipython3 import code_beatrix.automation.notebook_const_helper as const points = const.voyageur_de_commerce_points() .. code:: ipython3 display_canvas_point("tspchart", var_name="points") .. raw:: html
.. parsed-literal:: [] .. code:: ipython3 %pylab inline .. parsed-literal:: Populating the interactive namespace from numpy and matplotlib .. code:: ipython3 from code_beatrix.algorithm import voyageur_commerce_simple, plot_circuit points = voyageur_commerce_simple(points) plot_circuit(points, figsize=(12,6)) .. parsed-literal:: .. image:: voyageur_de_commerce_6_1.png .. code:: ipython3 points .. parsed-literal:: [(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 `__.