TSPのユークリッドインスタンスのグラフィックを作成

Question

現在、トラベリングセールスマン問題を中心に研究を進めています。より正確には、EUC_2Dエッジウェイトタイプを使用してサンプルデータを扱っています。次のように：

1 11003.611100 42102.500000 
2 11108.611100 42373.888900 
3 11133.333300 42885.833300 

ツアーオーダーを作成することができます。たとえば、2-3-1。

私は、与えられた問題のポイントセットを表す単純なグラフィックを作成してから、上にツアーを持つポイントセットを作成したいと考えています。誰もがこれを達成するためにどのようなソフトウェアを見なければならないのか、これを達成するための簡単な方法をお勧めしますか？私は赤ちゃんX.（それは私自身のウィンドウシステムです）をお勧めするつもりは

おかげ

Answer 1

ちょうどあなたの通常の科学的なプロット・ツールがどのように動作するかについて簡単にデモを与えることを（私が正しくあなたのタスクを理解仮定）：

プロット専用コードのpython & matplotlibを使用して：

import matplotlib.pyplot as plt 

fig, ax = plt.subplots(2, sharex=True, sharey=True)   # Prepare 2 plots 
ax[0].set_title('Raw nodes') 
ax[1].set_title('Optimized tour') 
ax[0].scatter(positions[:, 0], positions[:, 1])    # plot A 
ax[1].scatter(positions[:, 0], positions[:, 1])    # plot B 
start_node = 0 
distance = 0. 
for i in range(N): 
    start_pos = positions[start_node] 
    next_node = np.argmax(x_sol[start_node]) # needed because of MIP-approach used for TSP 
    end_pos = positions[next_node] 
    ax[1].annotate("", 
      xy=start_pos, xycoords='data', 
      xytext=end_pos, textcoords='data', 
      arrowprops=dict(arrowstyle="->", 
          connectionstyle="arc3")) 
    distance += np.linalg.norm(end_pos - start_pos) 
    start_node = next_node 

textstr = "N nodes: %d\nTotal length: %.3f" % (N, distance) 
props = dict(boxstyle='round', facecolor='wheat', alpha=0.5) 
ax[1].text(0.05, 0.95, textstr, transform=ax[1].transAxes, fontsize=14, # Textbox 
     verticalalignment='top', bbox=props) 

plt.tight_layout() 
plt.show() 

出力：

このコードは、次のfのデータに基づいています

[[ 4.17022005e-01 7.20324493e-01] 
[ 1.14374817e-04 3.02332573e-01] 
[ 1.46755891e-01 9.23385948e-02] 
[ 1.86260211e-01 3.45560727e-01] 
[ 3.96767474e-01 5.38816734e-01]] 

ノードxが我々の溶液ツアー中yが続いているときのように、~1マーキング我々のMIP-溶液である2次元アレイx_sol：ORM：状(n_points, n_dimension)の

2Dアレイpositions ：

[[ 0.00000000e+00 1.00000000e+00 -3.01195977e-11 2.00760084e-11 
    2.41495095e-11] 
[ -2.32741108e-11 1.00000000e+00 1.00000000e+00 5.31351363e-12 
    -6.12644932e-12] 
[ 1.18655962e-11 6.52816609e-12 0.00000000e+00 1.00000000e+00 
    1.42473796e-11] 
[ -4.19937042e-12 3.40039727e-11 2.47921345e-12 0.00000000e+00 
    1.00000000e+00] 
[ 1.00000000e+00 -2.65096995e-11 3.55630808e-12 7.24755899e-12 
    1.00000000e+00]] 

大きな例：MIP-gap = 5%;意味：溶液は、最適よりも、せいぜい5％より悪くなることが保証された（1は、いくつかの交差が起こっている権利で次善の部分を見ることができる）：

偽物を含む完全なコードは、TSP-データと解決可能なhere。

Answer 2

。

LinuxやMS Windowsで動作するWindowsシステムで、この種の問題を正確に解決できるように設計されています。いくつかのシンプルなグラフィックスでプログラムを素早く試作します。

赤ちゃんXはrgbaサーフェスを公開します。次に、独自のルーチン、Baby Xの基本ルーチン（線とポリゴン）、またはBaby Xグラフィックスコンテキスト（ベジエベースの完全な2Dグラフィックス）を使用してバッファに描画します。セットアップが非常に迅速です。あなたは、明らかに、ピクセル空間にグラフを拡大し、都市のプロットシンボルを描き、それらの間に線を描いてツアーを表現する必要があります。

https://github.com/MalcolmMcLean/babyx

しかし、いくつかのグラフィックス・システムは、そこにあります。ハードウェアpltformで実行されるものを選択するだけです。