平行,旅行推销员算法分支机构&绑定 - 通过C和MPI
我对这个代码有问题,不是我写的。这是带有分支机构和约束的旅行推销员算法。问题在于,当我插入20x20矩阵(如此20节)时,该程序需要很长时间。我可以改变什么?我希望在不到5秒钟的时间内取得结果……这大约需要2分钟。
从网络( http://wyattgorman.com/?p=25 ),它被解释了该程序必须做的事情:
“节点0是主人,不做任何工作,节点1是第一个工人,因此它的分支从城市0开始,然后进入城市1。节点2将城市0带到城市2等。如果您有20个节点,并且邻接矩阵大于20×20,例如30×30,节点20将将城市0带到城市20。然后,城市0再次分配到Node 1和Node 1和City 0到City 22 IS分配给节点2。发现低成本路线的报告都是由每个节点维护其正在开发的分支机构的最佳成本(即从城市0到城市X)。一旦完成了整个分支,它将向主人报告最佳的成本。然后,主人将最佳成本与自己最佳的运营成本进行比较,并跟踪最佳的获胜成本,获胜的道路和获胜节点。然后将主的最佳成本发送到节点以改善未来的边界。”
这是代码:
// Soluzione TSP con Branch and Bound
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define NODES 20
int m_row=NODES, m_column=NODES, zed=30, matrix[NODES][NODES], visited[NODES], best_path[NODES];
int best_cost=9999999, size=NODES;
void dfs(int city, int visited_in[], int path_in[], int path_i_in, int cost_in) {
if (cost_in < best_cost) {
int *visited=calloc(sizeof(int),size+1);
int *path=calloc(sizeof(int),size+1);
int path_i=path_i_in, cost=cost_in, i;
for (i=0; i<size; i++) {
visited[i]=visited_in[i];
path[i]=path_in[i];
}
visited[city]=1;
path[path_i]=city;
path_i++;
int leaf=0;
for(i=0; i<size; i++) {
if(visited[i]==0) {
leaf++;
dfs(i, visited, path, path_i, cost+matrix[city][i]);
}
}
if (leaf == 0) {
cost+=matrix[city][0];
path[path_i]=0;
path_i++;
if(cost < best_cost) {
//printf(“Found new best cost: %i\n”, cost);
best_cost=cost;
for(i=0; i<size; i++)
best_path[i]=path[i];
}
}
free(visited);
free(path);
}
}
int main(int argc, char* argv[]) {
int rank, p, source, dest;
int tag=0;
MPI_Status status;
MPI_Init(0, NULL);
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
srand( time(NULL) );
if (rank == 0) {
int i, j;
for(i=0; i<m_row; i++) // i < 20
for(j=0; j<m_column; j++) //j < 20
matrix[i][j]=0;
for ( i=0; i<m_row; i++ ) {
for( j=0; j<i; j++ ) {
if (i != j) {
int temp=(rand()%zed)+1;
matrix[i][j]=temp;
matrix[j][i]=temp;
}
}
}
// Manda la matrice generata a tutti i processi
for(i=1; i<p; i++) // p è il numero dei processi
MPI_Send(&matrix[0][0], size*size, MPI_LONG, i, 0, MPI_COMM_WORLD);
printf("Matrix, %lix%li, Max Int: %li\n", m_row, m_column, zed);
for(i=0; i<m_row; i++) {
for(j=0; j<m_column; j++)
printf("%li\t", matrix[i][j]);
printf("\n");
fflush(NULL);
}
printf("\n");
int winner;
int node_array[p-1];
int node_array_i=0;
for(i=0; i<p-1; i++)
node_array[i]=i+1;
for(i=1; i<size; i++) { // size = 20
int temp_best_cost, node;
node=node_array[node_array_i]; // va a prendere node_array[0] perchè node_array_i = 0;
if (node_array_i < p-2)
node_array_i++;
else
node_array_i=0;
int *temp_best_path=calloc(sizeof(int),size+1);
MPI_Recv(&temp_best_cost, 1, MPI_INT, node, 0, MPI_COMM_WORLD, &status); // node è il rank del processo sorgente
MPI_Recv(&temp_best_path[0], size+1, MPI_INT, node, 0, MPI_COMM_WORLD, &status);
if(temp_best_cost < best_cost) { // Confronto tra il costo ricevuto e l'ottimo corrente
winner=node;
best_cost=temp_best_cost;
for(j=0; j<size+1; j++)
best_path[j]=temp_best_path[j];
}
MPI_Send(&best_cost, 1, MPI_INT, node, 0, MPI_COMM_WORLD);
}
printf("Best Path Found by node %i:\n", winner);
printf("%i", best_path[0]);
for(i=1; i<size+1; i++)
printf(" –> %i",best_path[i]);
printf("\nBest Cost Found: %i\n", best_cost);
}
else {
MPI_Recv(&(matrix[0][0]), m_row*m_column, MPI_LONG, 0, 0, MPI_COMM_WORLD, &status);
int i;
for(i=rank; i<size; i+=(p-1)) {
int *visited=calloc(sizeof(int), size+1);
int *path=calloc(sizeof(int), size+1);
int cost=matrix[0][i], path_i=1; // imposta cost al peso dell'arco tra 0 e il valore di rank
// ad esempio (se rank = 1) cost = il peso dell'arco tra il nodo 0 e il nodo 1
path[0]=0;
visited[0]=1;
dfs(i, visited, path, path_i, cost);
MPI_Send(&best_cost, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
MPI_Send(&best_path[0], size+1, MPI_INT, 0, 0, MPI_COMM_WORLD);
MPI_Recv(&best_cost, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
free(visited);
free(path);
}
}
MPI_Finalize();
return 0;
}
I have a problem with this code, not written by me. This is the traveling salesman algorithm with branch and bound. The problem is that when I insert a 20x20 Matrix (so 20 knots), the program takes a long time. What could I change? I would like a result in less than 5 seconds… this takes about 2 minutes.
From the web(http://wyattgorman.com/?p=25), it is explained what this program must do:
“Node 0 is the master and doesn’t do any work, node 1 is the first worker, so it gets the branch that starts at city 0 and goes to city 1. Node 2 takes city 0 to city 2 and so on. If you have 20 nodes and the adjacency matrix is greater than 20 × 20, say 30 × 30, node 20 will get city 0 to city 20. Then city 0 to city 21 is again assigned to node 1 and city 0 to city 22 is assigned to node 2. The reporting of the low cost routes found is carried out by each node maintaining its best cost for the branch it is working on (ie from city 0 to city X). Once it has gone through the entire branch, it reports the best cost to the master. The master then compares the best cost with his own best operating cost and keeps track of the best winning cost, the winning path and the winning node. Then send the best cost of the master to the node to improve the future boundary.”
This is The code:
// Soluzione TSP con Branch and Bound
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define NODES 20
int m_row=NODES, m_column=NODES, zed=30, matrix[NODES][NODES], visited[NODES], best_path[NODES];
int best_cost=9999999, size=NODES;
void dfs(int city, int visited_in[], int path_in[], int path_i_in, int cost_in) {
if (cost_in < best_cost) {
int *visited=calloc(sizeof(int),size+1);
int *path=calloc(sizeof(int),size+1);
int path_i=path_i_in, cost=cost_in, i;
for (i=0; i<size; i++) {
visited[i]=visited_in[i];
path[i]=path_in[i];
}
visited[city]=1;
path[path_i]=city;
path_i++;
int leaf=0;
for(i=0; i<size; i++) {
if(visited[i]==0) {
leaf++;
dfs(i, visited, path, path_i, cost+matrix[city][i]);
}
}
if (leaf == 0) {
cost+=matrix[city][0];
path[path_i]=0;
path_i++;
if(cost < best_cost) {
//printf(“Found new best cost: %i\n”, cost);
best_cost=cost;
for(i=0; i<size; i++)
best_path[i]=path[i];
}
}
free(visited);
free(path);
}
}
int main(int argc, char* argv[]) {
int rank, p, source, dest;
int tag=0;
MPI_Status status;
MPI_Init(0, NULL);
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
srand( time(NULL) );
if (rank == 0) {
int i, j;
for(i=0; i<m_row; i++) // i < 20
for(j=0; j<m_column; j++) //j < 20
matrix[i][j]=0;
for ( i=0; i<m_row; i++ ) {
for( j=0; j<i; j++ ) {
if (i != j) {
int temp=(rand()%zed)+1;
matrix[i][j]=temp;
matrix[j][i]=temp;
}
}
}
// Manda la matrice generata a tutti i processi
for(i=1; i<p; i++) // p è il numero dei processi
MPI_Send(&matrix[0][0], size*size, MPI_LONG, i, 0, MPI_COMM_WORLD);
printf("Matrix, %lix%li, Max Int: %li\n", m_row, m_column, zed);
for(i=0; i<m_row; i++) {
for(j=0; j<m_column; j++)
printf("%li\t", matrix[i][j]);
printf("\n");
fflush(NULL);
}
printf("\n");
int winner;
int node_array[p-1];
int node_array_i=0;
for(i=0; i<p-1; i++)
node_array[i]=i+1;
for(i=1; i<size; i++) { // size = 20
int temp_best_cost, node;
node=node_array[node_array_i]; // va a prendere node_array[0] perchè node_array_i = 0;
if (node_array_i < p-2)
node_array_i++;
else
node_array_i=0;
int *temp_best_path=calloc(sizeof(int),size+1);
MPI_Recv(&temp_best_cost, 1, MPI_INT, node, 0, MPI_COMM_WORLD, &status); // node è il rank del processo sorgente
MPI_Recv(&temp_best_path[0], size+1, MPI_INT, node, 0, MPI_COMM_WORLD, &status);
if(temp_best_cost < best_cost) { // Confronto tra il costo ricevuto e l'ottimo corrente
winner=node;
best_cost=temp_best_cost;
for(j=0; j<size+1; j++)
best_path[j]=temp_best_path[j];
}
MPI_Send(&best_cost, 1, MPI_INT, node, 0, MPI_COMM_WORLD);
}
printf("Best Path Found by node %i:\n", winner);
printf("%i", best_path[0]);
for(i=1; i<size+1; i++)
printf(" –> %i",best_path[i]);
printf("\nBest Cost Found: %i\n", best_cost);
}
else {
MPI_Recv(&(matrix[0][0]), m_row*m_column, MPI_LONG, 0, 0, MPI_COMM_WORLD, &status);
int i;
for(i=rank; i<size; i+=(p-1)) {
int *visited=calloc(sizeof(int), size+1);
int *path=calloc(sizeof(int), size+1);
int cost=matrix[0][i], path_i=1; // imposta cost al peso dell'arco tra 0 e il valore di rank
// ad esempio (se rank = 1) cost = il peso dell'arco tra il nodo 0 e il nodo 1
path[0]=0;
visited[0]=1;
dfs(i, visited, path, path_i, cost);
MPI_Send(&best_cost, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
MPI_Send(&best_path[0], size+1, MPI_INT, 0, 0, MPI_COMM_WORLD);
MPI_Recv(&best_cost, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
free(visited);
free(path);
}
}
MPI_Finalize();
return 0;
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论