我正在使用 MPI 来解析一个试图解决 Metric TSP 问题的程序。我有P个处理器，N个城市要通过。
每个线程都向 master 请求工作，接收一个块——这是一个他应该检查并计算其中最小值的排列范围。我通过提前修剪不良路线来优化这一点。
共有 (N-1) 个！计算路径。每个工人都会得到一个带有数字的块，该数字代表他必须检查的第一条路线，也是最后一条路线。此外，大师向他发送已知的最近最好的结果，因此可以在其遗骸上预先设定一些下限，从而轻松应对糟糕的路线。
每次工作人员找到比全局更好的结果时，他都会异步将其发送给所有其他工作人员和主服务器。
我不是在寻找更好的解决方案——我只是想确定哪个块大小是最好的。
到目前为止，我发现的最佳块大小是 (n!)/(n/2)！，但它并没有产生那么好的结果。
请帮助我了解哪个块大小是最好的。我正在尝试在计算量和通信量之间取得平衡，谢谢