排列数字对，使相邻对的成员相等 [英] Arrange pairs of numbers so that members of adjacent pairs are equal

问题描述

我想安排以下物品，形成最长的链，从12-8开始，并以数字开头到结尾。

I would like to arrange the following items, forming the longest chain possible starting with 12-8 and matching the numbers end to end.

我的物品是7- 4，11-8，11-11，1-0，4-2，7-5，10-8，7-3，10-5，7-2，9-8，12-8，0-0， 11-10

My items are 7-4, 11-8, 11-11, 1-0, 4-2, 7-5, 10-8, 7-3, 10-5, 7-2, 9-8, 12-8, 0-0, 11-10

最长的链条是12-8、8-11、11-11、11-10、10-5、5-7、7-4 ，4-2、2-7、7-3

The longest possible chain is 12-8, 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2, 2-7, 7-3

我尝试遍历项目数组并获取与我要查找的数字匹配的第一个值，但是它不会导致最长的链。我的方法让我知道：12-8、8-11、11-11、11-10、10-8、8-9

I tried iterating over the array of items and taking the first value that matches the number I'm looking for but it doesn't result in the longest chain. My method gets me: 12-8, 8-11, 11-11, 11-10, 10-8, 8-9

如何编写适当的排序

推荐答案

我已经从图论的角度研究了这个问题，它给出了一些关于问题，并提供一些可用于有效解决问题的试探法。

I've looked at the problem in a graph-theoretic perspective, which gives some insights about the problem, and provides some heuristics that may be used to solve the problem efficiently.

首先，构造一个图形，使您得到的每个项目都对应于图形的边缘。例如，如果您输入的内容为：1-2、2-3；您使用以下节点构造图：1，2，3;和边缘（1、2），（2、3）。

First, construct a graph such that every item you are given corresponds to an edge of the graph. For example, if your input given as: 1-2, 2-3; you construct a graph with nodes: 1, 2, 3; and edges (1, 2), (2, 3).

此后，您可以看到您的问题等同于找到最长的路径，即最长的路径不包含一条以上的边。不幸的是，这个问题被称为NP难题，如本问题。因此，我们不能希望找到一个解决该问题的多项式算法。

Thereafter, you can see that your problem is identical to finding the longest trail, i.e., the longest path that does not contain any edge more than one. Unfortunately, this problem is known to be NP-hard, as discussed in this question. So, we cannot hope to find a polynomial algorithm to solve this problem.

但是，该问题实际上与欧拉路径。但是，在Eularian路径中，您会遍历所有边缘。它有一个非常简单的解决方案：

However, this problem is actually very similar to the problem of Eularian Path. However, in an Eularian path you traverse all edges. And it has a very simple solution:

当且仅当零个
或两个顶点时，无向图才具有欧拉路径具有奇数度，并且如果其所有具有
非零度数的顶点都属于单个连接的分量。

An undirected graph has an Eulerian path if and only if exactly zero or two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component.

要解决您的问题，请使用包含要开始的项目的图形的已连接组件。您可能无法到达此连接组件中没有的项目。因此，您可以忘记该图的所有其余边缘。

So in order to solve your problem, you take the connected component of the graph that contains the item you want to start with. You cannot possibly reach the items that are not in this connected component. Therefore, you can forget about all of the remaining edges of the graph.

然后，您只需计算每个节点的度数，然后检查该图是否具有欧拉路径根据前面的定义。如果有，那么您很幸运。因为您的链条不可能超过此路径。

Then, you simply count the degrees of each node, and check if that graph has an Eulerian path by the preceding definition. If it has, then you're lucky. Because you can't possibly have a chain longer than this path.

您可以通过 Fleury算法。

但是，如果此组件没有Eualirian路径，那么您至少知道有不存在此组件边缘大小或更多的链。

However, if this component does not have an Eualirian path, then you at least know that there does not exist a chain of the size of the edges of this component or more.

握手引理告诉我们：

每个无向图的偶数个顶点的奇数次

Every undirected graph has an even number of vertices with odd degree.

如果不存在欧拉路径，那么我们知道我们有 2k 个奇数节点度，其中 k> 1 。因此，我们需要删除最小数量的边线，使 k = 1 。但是，您需要考虑到，当删除某些边缘时，其余边缘可能不会连接。

If there does not exists an Eulerian path, then we know that we have 2k nodes with odd degrees where k > 1. So we need to remove minimum number of edges edges so that we have k = 1. However, you need to take into account that when you remove some of the edges, remaining edges may not be connected.

因此，我想到的最好的启发式方法是：找到边缘，使其两个顶点都具有奇数度，并且将其移除不会将连接的组件撕裂。如果我们找到这样的 k-1 个顶点，那么当我们删除它们时，我们将仍然具有连接的分量，并且只有2个顶点具有奇数度。因此，通过使用Fleury算法找到一条欧拉路径，我们可以轻松找到最长的链。

So the best heuristic that comes to my mind is to find edges such that both of its vertices have odd degrees, and removing it doesn't tear the connected component apart. If we can find such k - 1 vertices, then when we remove them we will stil have a connected component and we will have only 2 vertices with odd degrees. Therefore we can find the longest chain easily, again by finding an Eulerian path using Fleury's algorithm.

这篇关于排列数字对，使相邻对的成员相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！