寻找 Sophie
4.83/5 (28投票s)
寻找 Sophie 谜题的解决方案
引言
在本文中，我们将讨论软件难题“寻找索菲”的解决方案。该难题是著名的 NP-hard“旅行推销员”问题的一个变体。
不幸的是，许多工作面试要求软件工程师解决困难的编程难题。这些难题并不能测试抽象思维、理解、沟通技巧、推理、学习、规划和解决问题能力。简而言之，它们不能测试任何定义智力的东西。
幸运的是，微软不再是软件行业的领跑者，大多数公司也不再模仿微软，不再问“四人过桥”之类的难题。公平地说，谷歌、脸书和苹果已经取代了微软成为软件行业的领导者。因此，现在每家公司都想成为下一个谷歌或脸书，结果是他们问的问题和谷歌、脸书、苹果问的一样——算法难题。
如果没有基本（甚至不那么基本）的算法知识，几乎不可能解决这些难题。“寻找索菲”的解决方案基于图论算法，所以在我们深入细节之前，我们必须回顾其中一些算法。
背景
首先，一些有用的术语
顶点是图中的圆圈，边是连接顶点的线。大O表示法用于量化每个算法的运行时间。图也可以方便地用一个二维矩阵来描述，如果两个顶点之间有边连接，则矩阵中包含1，否则包含0。加权图的每条边都有一个数字。对于加权图，1可以替换为边的非零权重。树是图的一个子集——有向图。对于树，顶点被称为节点。每个节点可以有零个或多个子节点（可以从父节点导航到的节点）。
| 简要描述 |
|
|||
| 深度优先搜索（DFS） | 主要用于遍历树，它通过尽可能深入直到达到没有子节点的节点来实现。然后它回溯。非递归实现使用堆栈来跟踪遍历的节点。 | O(V + E) | ||
| 广度优先搜索（BFS） | 与DFS不同，我们首先探索所有分支（子节点），然后才回溯。 | O(V + E) | ||
| 迪杰斯特拉算法 | 用于在非负加权图中查找一对顶点之间的最短路径。队列常用于实现该算法。 | O(V^2) （基本实现） |
||
| 弗洛伊德-沃歇尔算法 |
|
|
||
| 普里姆算法 | 用于在加权无向图中寻找最小生成树（连接所有顶点且总权重最小的树）。 | O(V^2) （基本实现） |
谜题
现在我们终于可以来探索这个谜题了。
辛苦编码一天后，你喜欢回家和心爱的人一起放松。由于最近感情生活不太顺利，那个心爱的人只好是你的猫，索菲。不幸的是，你到家后发现自己花了大量时间试图找到她。作为一个完美主义者，不能让任何不尽人意的事情成为你日常生活的一部分，你决定设计出最有效的方法来寻找索菲。
对你来说幸运的是，索菲是一个习惯性动物。你知道她所有的藏身之处，以及她藏在每个地方的概率。你还知道从一个藏身之处走到另一个藏身之处需要多长时间。编写一个程序来确定在你公寓里找到索菲所需的最小预期时间。简单地访问一个地点来检查索菲是否藏在那里就足够了；不需要花时间在某个地点寻找她。当你进入公寓时，索菲就藏起来了，并且在找到她之前不会离开那个藏身之处。
你的程序必须将输入文件的名称作为命令行参数。
注意：您不必阅读输入和输出规范（除非您真的想）。
输入规范
输入文件以一个数字 `m` 开头，后跟一个换行符。`m` 是索菲可以藏身在你公寓的地点数量。这行后面跟着 `m` 行，每行包含一个地点的形式信息（括号是为了清晰）
<location name> <probability>
其中 probability 是 Sophie 藏身于所示位置的概率。所有概率之和始终为 `1`。这些行的内容用空格分隔。名称只包含字母数字字符和下划线 (`_`)，并且不会有重复的名称。所有输入都保证格式正确。你的起点是第一个列出的位置，实际上检查 Sophie 是否在那里不花费你任何时间。
文件继续以一个数字 `c` 开头，后跟一个换行符。`c` 是不同位置之间存在的连接数量。这行后面跟着 `c` 行，每行形式如下：
<location name> <location name> <seconds>
其中第一个条目是位置名称，第二个条目是你在这两个位置之间行走所需的时间（秒）。同样，这些行是空格分隔的。请注意，位置是无序的；你可以双向行走，所需时间相同。输入文件中不会包含重复的对，并且所有位置名称都将与文件中前面描述的一个位置匹配。
输出规范
你的输出必须由一个数字后跟一个换行符组成，打印到标准输出。该数字是找到索菲所需的最短预期时间（以秒为单位），四舍五入到最近的百分位。确保打印的数字小数点后恰好有两位（即使它们是零）。如果无法保证能找到索菲，则打印“`-1.00`”后跟一个换行符。
示例
这看起来确实是一个图问题，但如果没有一个好的例子，几乎不可能解决这样的问题。
在我们的例子中，顶点A是公寓的入口（猫的第一个可能的藏身之处）。猫藏在那里的概率是0.2。这个人从A走到B（另一个藏身之处）需要2秒，猫藏在那里的概率是0.3。
根据定义，期望在离散情况下是 x1*p1 + x2*p2 + x3*p3 + …，其中 x 是具有概率 p 的值。例如，如果我们去位置 C，途中经过位置 D，找到 Sophie 的期望值是猫在位置 D 的概率乘以到达位置 D 所需的时间，加上猫在位置 C 的概率乘以到达位置 C 所需的时间 –> 0.4 * 5 + (5+9)*0.1 = 3.4。
我们必须访问所有顶点才能找到期望值。在我们的例子中，有6条可能的路径。
ABCD, ABDC, ADCB, ADBC, ACBD, ACDB
从数学上讲，我们想将3个（BCD）不同的对象重新排列成一个序列。有3*2*1种方法可以做到这一点，在离散数学中，这叫做n阶乘（3! = 3*2*1 = 6）。现在可能看起来ADCB比ABDC（通过A）是更好的选择，因为从B到D我们必须回到A，但这是不正确的。对于ADCB，我们有5*0.4 + 0.1*14 + 20*0.3 = 9.4，而对于ABDC（通过A），我们有2*0.3 + 9*0.4 + 18 *0.1 = 6。将所有6条路径表示为一棵树更容易。
如果我们计算所有六条路径，我们会发现 ABDC（通过 A）给出最佳预期值。因此，我们用于解决此示例的算法执行以下操作：
- 找到所有排列（ABCD、ABDC、ADCB、ADBC、ACBD 和 ACDB）。
- 对于每个排列，找到路径上每对顶点之间的最短路径（对于 ABCD，找到 AB、BC 和 CD 之间的最短路径）
- 对于每个排列，使用最短路径计算预期值。
- 选择最小期望值
这是一个很好的解决方案，但它有一个问题。它的时间复杂度至少是 O(N!)。因此，解决20个节点的问题是不现实的（20! = 2432902008176640000）。所以我们真的需要找到一些优化。通过查看树，我们可以看到我们可以轻松地忽略至少一些路径而无需计算整个路径。所以如果我们从左边开始，计算 ABCD 然后 ABDC，我们知道当前最小期望值是 6，并且没有必要计算 ACDB，因为 ACD 已经加起来达到 6.1。虽然对于 4 个节点，优化是最小的，但对于 20 个节点，这种简单的优化将帮助我们忽略整个分支，将解决方案从 O(N!) 转换为 O(N^3)。当然，最坏情况仍然是 O(N!)，但让我们抱最好的希望。
解决方案
一旦我们理解了这个例子，解决方案就显而易见了。对于N个藏身之处，我们构建一棵有(N-1)!条路径的树（每个排列都是一条路径）。对于每条路径，我们计算路径上每两个顶点之间最短的（按期望值计算）路径并将其相加。这样我们就计算出了每条路径的期望值，现在我们所要做的就是找到最小值。是的，如上所述，我们必须添加一些优化以实现比O(N!)更好的平均运行时间。
实现
`void Graph::read_graph(char* file)` 从输入文件读取图到内存中。它创建了两个数据结构：一个权重矩阵（`double** Weight`）和一个包含概率的节点向量。该矩阵将用于计算最短路径，而节点将用于创建所有期望的排列。
那么我们应该选择什么算法来计算顶点之间的最短路径呢？我们当然可以使用 Dijkstra 算法，但其基本实现的时间复杂度为 O(V^2)，并且我们必须多次运行它（最坏情况是 N!，没有任何缓存）。Floyd–Warshall 算法是一个更好的选择，因为它在最坏情况下的时间复杂度为 O(V^3)，并且计算所有顶点对之间的最短路径。这种算法最好的地方是它很容易实现。
算法的输入是一个 NxN 矩阵，其中权重作为值。在我们的例子中，权重始终为正，因此我们可以将 `-1` 作为“未连接”。对于我们的例子，矩阵将是这样的：
该算法修改输入矩阵，以便最终其值是最短路径。
因此，根据矩阵，D和B之间的最短路径是7。不要惊讶于A和A之间的最短路径是4而不是0，因为我们必须先访问B才能回到A。
这是代码
void Graph::run_floyd()
{
for (int k = 0; k < NodeCount; ++k)
{
for (int i = 0; i < NodeCount; ++i)
{
for (int j = 0; j < NodeCount; ++j)
{
double sum = Weight[i][k] + Weight[k][j];
bool inf = ((Weight[i][k] == -1) || (Weight[k][j] == -1));
if (!inf)
{
if (Weight[i][j] == -1)
{
Weight[i][j] = sum;
}
else if (sum < Weight[i][j])
{
Weight[i][j] = sum;
}
}
}
}
}
}
这就是它的工作原理。两个内循环遍历矩阵。第三个循环 (k) 依赖于 `path[i][j] = min ( path[i][j], path[i][k]+path[k][j] )` 这一事实。对于任意两个顶点，如果我们通过第三个顶点 (k) 能得到更好的解吗？如果可以，我们只需更新矩阵。请注意，对于这个问题，矩阵将始终是对称的，因为图是无向的。
接下来我们需要做的就是创建所有排列（路径）并计算每个排列的预期时间（通过一些优化来跳过不现实的排列）。我们在名为 `permutate` 的函数中完成此操作。
不幸的是，这个函数是递归的，但它背后的思想很简单。我们将所有节点（猫躲藏的地方）添加到一个向量（数组）中。数组中的每个节点都有一个标志，表示该节点是否属于当前排列。我们将循环遍历数组，选择第一个未被使用的节点，计算其期望值，并将值递归地传递给该函数。通过这种方式，我们生成了一棵类似于示例中绘制的树，而无需消耗任何额外的空间。我们的优化还将帮助我们避免生成大于当前最小期望时间的分支。
double permutate(double probability, double expectation, double time, Node* currNode)
{
if (m_Nodes.size() < 2)
{
if (m_Nodes.size() == 0)
{
return - 1;
}
else
{
return 0;
}
}
if (!currNode)
{
currNode = m_Nodes[0];
probability = 1 - currNode->getProbability();
expectation = 0;
}
else
{
probability -= currNode->getProbability();
expectation += time * currNode->getProbability();
}
if (m_CurrentMin >= 0)
{
if (expectation + probability * time >= m_CurrentMin)
{
return m_CurrentMin;
}
}
bool allInUse = true;
for(unsigned int i=1; i < m_Nodes.size(); ++i)
{
Node* nextNode = m_Nodes[i];
if (nextNode->isInUse())
{
continue;
}
allInUse = false;
nextNode->setInUse(true);
permutate(probability, expectation, time +
Weight[currNode->getID()][nextNode->getID()], nextNode);
nextNode->setInUse(false);
}
if (allInUse) // end recursion condition)
{
m_CurrentMin = expectation;
}
return m_CurrentMin;
}
结论
这就是解决方案。这个问题不难，但需要大量的思考和耐心。没有多少公司能将这样的难题作为招聘流程的一部分，但Facebook是个例外——它拥有近十亿用户，IPO也不远了。现在，你是否想参与到这个招聘流程中，完全取决于你。是的，许多小型（和不那么小型）公司会试图通过在面试流程中加入类似的问题来模仿Facebook的成功。他们可能在“成功”部分会失败，但肯定会成功淘汰99%的优秀软件工程师。))
如果你没有生活（或工作）并想在硅谷工作，这个博客提供了一套典型技术面试问题。