-1

我正在尝试解决在我的国家的一所大学的考试中提出的问题。它给了我一个包含在第一行 3 数字的文件作为输入：

  • 第一个(n)代表人数
  • 第二个（m）代表人与人之间的友谊数
  • 第三个（k）是序列的大小（但序列不必和这个数字一样大，可以更大）

    • ...在第二行，关系（m 对形式为 (a, b) 的数字表示 a 是 b 的朋友，b 是 a 的朋友）。

    任务是尽可能有效地找到人们彼此成为朋友的最大长度（至少是 k 个人）的序列。如果没有这样的序列，将打印“NO”。

    他们的例子：

    数据.txt：

    5 5 3
1 2 5 1 3 2 4 5 1 4

    输出：

    1 4 5

    数据.txt：

    5 5 4
1 2 5 1 3 2 4 5 1 4

    输出：

    No

    数据.txt：

    11 18 3 
1 8 4 7 7 10 11 10 2 1 2 3 8 9 8 3 9 3 9 2 5 6 5 11 1 4 10 6 7 6 2 8 11 7 11 6

    输出.txt：

    2 3 6 7 8 9 10 11

    我的方法

    在这种情况下，友谊可以用无向图表示（至少对我来说，这似乎是最合乎逻辑的数据结构），其中顶点代表人，边代表友谊。要成为序列的一部分，顶点的度数必须大于或等于 k ​​- 1。

    这就是我停下来的地方。目前我所能做的就是消除度数至少为 k - 1 的节点：

    #include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

std::ifstream f{ "data.txt" };

constexpr size_t LIMIT = 101;

// graph[i][j]: i is friend with j
// short to avoid vector<bool> specialization
std::vector<std::vector<short>> graph(LIMIT, std::vector<short>(LIMIT, 0));
std::vector<int> validNodes;

int numOfNodes, numOfRelationships, sequenceSize;

void Read()
{
    f >> numOfNodes >> numOfRelationships >> sequenceSize;

    int a;
    int b;

    for(int i = 1; i <= numOfRelationships; ++i) {
        f >> a >> b;

        graph[a][b] = graph[b][a] = 1;
    }
}

int Degree(int node)
{
    int result = 0;

    for(int i = 1; i <= numOfNodes; ++i) {
        if(i != node && graph[node][i] == 1) {
            ++result;
        }
    } 

    return result;
}

void KeepValidNodes()
{
    for(int i = 1; i <= numOfNodes; ++i) {
        if(Degree(i) < sequenceSize - 1) {
            // Don't add the node to validNodes vector
            // "Remove it from the graph" aka it's not friend with anyone
            // all nodes that were friends with it now have a lower degree, remove them from the validNodes vector if that's the case
            for(int j = 1; j <= numOfNodes; ++j) {
                auto findPos = std::find(validNodes.begin(), validNodes.end(), j);

                if(findPos != validNodes.end() && Degree(j) - 1 < sequenceSize - 1) {
                    *findPos = -1;
                }

                graph[i][j] = graph[j][i] = 0;
            } 
        }
        else {
            validNodes.push_back(i);
        }
    } 
}

void PrintSequence()
{
    bool empty = true;

    for(const int& node : validNodes) {
        if(node != -1) {
            empty = false;
            std::cout << node << std::endl;
        }
    }

    if(empty) {
        std::cout << "No" << std::endl;
    }
}

int main()
{
    Read();
    KeepValidNodes();
    PrintSequence();
}

    这仅适用于他们的前 2 个示例。我能想到的唯一可能的解决方案是生成所有可能的节点组合，看看哪个满足要求。正如他们所说，我怎样才能有效地解决这个问题？

    编辑：

    我不一定要寻找完整的工作代码，但我什至不知道如何解决这个问题。

    4

    1 回答 1

    3

    您的问题是要找到一个大小为 k 或更小的集团。我不知道是否有任何算法能够做到这一点，但肯定有算法能够找到最大大小的集团。一旦在图形中找到最大大小的团（我们称之为 n 团），找到大小 <= n 的团就可以减少从 n 团中提取顶点的子集。

    对于一般情况，没有多项式时间算法，因为这个问题是 NP 完全的，所以不要指望会得到很棒的结果。这个答案包含一个简短的算法列表，这些算法将比蛮力算法更快地解决这个问题。如果您想了解更多信息，还应该查看Karp 关于问题可简化性的论文（即使您不将此概念应用于该问题，它也值得一读，因为 NP 完全问题的许多解决方案都依赖于简化）。

    于 2018-06-20T18:38:07.537 回答