MPI を使用して、メトリック TSP 問題を解決しようとしているプログラムを並列処理しています。P 個のプロセッサーと N 個の都市を渡す必要があります。
各スレッドはマスターに作業を依頼し、チャンクを受け取ります。チャンクは、チェックする必要がある順列の範囲であり、その中で最小のものを計算します。事前に悪いルートを剪定することでこれを最適化しています。
合計（N-1）あります！計算するルート。各ワーカーは、チェックする必要がある最初のルートと最後のルートを表す番号を持つチャンクを取得します。さらに、マスターは既知の最新の最良の結果を彼に送信するため、残りの下限を使用して、事前に悪いルートを簡単に作成できます。
ワーカーが global よりも優れた結果を見つけるたびに、ワーカーはそれを他のすべてのワーカーとマスターに非同期で送信します。
より良い解決策を探しているわけではありません。どのチャンクサイズが最適かを判断しようとしているだけです。
これまでに見つけた最適なチャンク サイズは (n!)/(n/2)! です。、しかし、それほど良い結果は得られません。
ここでどのチャンクサイズが最適かを理解するのを手伝ってください。計算量と通信量のバランスをとろうとしています ありがとう