二维数组的 PHP 组合对作为 Christofides 算法解决方案的一部分

Question

我正在为旅行商问题创建 Christofides 算法。在部分算法中，我需要找到奇数度的图节点，然后计算最低权重。这可以通过 Blossom 算法来完成，但我选择通过从二维数组中找到可能组合的总和来以不同的方式来完成，因为我正在努力使用 blossom 算法并且不理解它。

我有一个二维数组，它存储图中奇数度顶点之间的权重。例如:

$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)
                   )

所以 0 和 1 之间的权重为 2，如果我选择顶点 0 和 1，那么我将剩下顶点 2 和 3 之间的权重，因为顶点 0 和 1 已经被使用。然后我需要对数组[0][1] 和数组[2][3] 的权重求和。

我正在努力创建一个返回可能顶点对组合的算法。例如，在上面的数组中，可能的对是 [(0,1)(2,3)],[(0,2)(1,3)],[(0,3)(1,2)]

(0,0),(1,1),(2,2),(3,3) 不能使用，因为它们之间没有边权重。此外，不需要它们的反面([(1,0)(2,3)])。

有了这些对，我就可以计算权重之和并选择最小的。

如有任何帮助，我们将不胜感激。

Answer 1

您可以使用 php 的 array_* 函数(我将在下面执行此操作)非常快速地实现您提出的要求，但我不能不指出所提供的解决方案将您限制为仅包含 4 个顶点的数组因为这个声明:

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.

如果您必须与 5 个顶点进行交互，“剩余权重”方面的复杂性会增加，因为您不仅仅是剩下未使用的对。如果您无法修改下面提供的代码来解决 4 个顶点的情况，则必须在 5 个以上顶点的情况下定义所需的行为以获得更多帮助。

<?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]]
// )