dounabi6295
dounabi6295
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 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 dounuo9921 7年前

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

    点赞 评论 复制链接分享