2014-04-03 10:59

# 用于2D阵列的PHP组合作为Christofides算法解决方案的一部分

I am creating Christofides algorithm for the Traveling Salesman Problem. In part of the algorithm I need to find nodes of a graph that are of odd degree and then calculate the lowest weight. This can be done by the Blossom algorithm, but I am choosing to do it a different way by finding the sum of the possible combinations that you have from a 2D array because I am struggling with the blossom algorithm and do not understand it.

I have 2D array which stores the weights between vertices of odd degree in a graph. For example:

``````\$array = array(
0=> array(0, 2, 20,4),
1=> array(2,0,7,8),
2=> array(20,2,0,12),
3=> array(4,8,12,0)
)
``````

so between 0 and 1 is of weight 2, if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used. I then need to sum the weights of array[0][1] and array[2][3].

I am struggling with creating an algorithm that returns the combination of possible vertex pairs. For example in the array above the possible pairs are [(0,1)(2,3)],[(0,2)(1,3)],[(0,3)(1,2)]

(0,0),(1,1),(2,2),(3,3) cannot be used as there is no edge weight between them. Also, the reverse of them is not needed([(1,0)(2,3)]).

With these pairs I can then calculate the sum of the weights and choose the smallest.

Any help would be much appreciated.

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答

#### 2条回答

• dpmp9359 7年前

You can implement the requirements you lay out pretty quickly using php's array_* functions (which I'll do below), but I would be remiss to not call out that the presented solution limits you to an array of just 4 vertices specifically because of this statement:

if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used.

If you have to interact with 5 vertices, the "remaining weight" aspect increases in complexity since you have more than just a left over unused pair. You'll have to define the desired behavior in the case of 5+ vertices to get more assistance if you are not able to modify the code provided below which solves your case of 4.

``````<?php

\$array = array(
0=> array(0, 2, 20,4),
1=> array(2,0,7,8),
2=> array(20,2,0,12),
3=> array(4,8,12,0)
);

// Use the keys as the list of vertices.
\$vertices = array_keys(\$array);

// Filter out nodes without weights (preserves array keys, which are used as index-relations to other nodes)
\$array = array_map('array_filter', \$array);

// Create a list of all valid pairs
\$fullPairs = array_reduce(array_map(function(\$vert1, \$otherVerts) use (\$vertices) {
// For each first vertice, create pair combinations using weighted edge and remaining vertices
return array_map(function(\$vert2) use (\$vert1, \$vertices) {
// Because reverse combinations are not desired, we sort the pairings to easily identify dupes
\$vert = array(\$vert1, \$vert2);
sort(\$vert);
\$vertPair = array(\$vert, array_values(array_diff(\$vertices, \$vert)));
usort(\$vertPair, function(\$v1, \$v2) { return reset(\$v1) - reset(\$v2); });
return \$vertPair;
}, array_keys(\$otherVerts));
}, \$vertices, \$array), 'array_merge', array());

// Unique the list using a string representation of the pairs
\$uniqueIndexes = array_unique(array_map('json_encode', \$fullPairs));

// Match up the indexes of the unique list against the full pair list to get the pairing structure
\$uniquePairs = array_intersect_key(\$fullPairs, \$uniqueIndexes);

// Print the pairings for verification
print_r(array_map('json_encode', \$uniquePairs));

// Array
// (
//    [0] => [[0,1],[2,3]]
//    [1] => [[0,2],[1,3]]
//    [2] => [[0,3],[1,2]]
// )
``````
点赞 评论 复制链接分享
• dounuo9921 7年前

You can use some for-loops when you just need a few combinations.

点赞 评论 复制链接分享