用于 2D 数组的 PHP 对组合作为 Christofides 算法解决方案的一部分 - PHP combination of pairs for a 2D array as part of the solution for Christofides algorithm

我正在为旅行推销员问题创建Christofides算法。在算法的一部分中，我需要找到奇数度的图节点，然后计算最低权重。这可以通过 Blossom 算法来完成，但我选择以不同的方式通过从 2D 数组中找到您拥有的可能组合的总和来做到这一点，因为我正在为 Blossom 算法而苦苦挣扎并且不理解它。

我有 2D 数组，它将奇数度顶点之间的权重存储在图形中。例如：

$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）]）。

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

任何帮助将不胜感激。

您可以使用 php 的 array_* 函数（我将在下面完成）快速实现您布置的需求，但我不能不指出所提出的解决方案将您限制为仅包含 4 个顶点的数组，特别是因为以下语句：

如果我选择顶点 0 和 1
，则在顶点 2 和 3 之间留下权重，因为顶点 0 和 1 已被使用。

如果您必须与 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]]
// )

当您只需要几个组合时，可以使用一些 for 循环。