At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer 0 will be satisfied with drinks 0, 1, 3, or 6.
在一个受欢迎的酒吧，每个顾客都有一套自己喜欢的饮料，并且会很乐意接受其中的任何饮料。 例如，在以下情况下，客户0将与饮料满足0, 1, 3,或6 。
preferences = { 0: [0, 1, 3, 6], 1: [1, 4, 7], 2: [2, 4, 7, 5], 3: [3, 2, 5], 4: [5, 8] }A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.
在该酒吧工作的一个懒惰的酒保正试图通过限制必须记住的饮料配方来减少精力。 给定字典输入(例如上述输入)，返回最少的饮料以满足所有客户的需求。
For the input above, the answer would be 2, as drinks 1 and 5 will satisfy everyone.
对于上面的输入，答案将是2 ，因为饮料1和5将使所有人满意。
We often encounter interview questions where no efficient polynomial time algorithm exists. While it’s important to be able to code an exponential/super-polynomial time solution, it is equally important to argue why no polynomial time solution exists.
我们经常遇到没有有效的多项式时间算法的面试问题。 尽管能够对指数/超多项式时间解进行编码很重要，但争论为什么不存在多项式时间解也同样重要。
The exciting theory of NP-completeness is extremely useful to prove exactly that! You are not expected to make rigorous use of the theory during the interview. But we are still going to devote this section to develop a proof — it’s fun and you might get in good grace of the interviewer if you argue on these lines 🙂
令人兴奋的NP完全性理论对于证明这一点非常有用！ 面试过程中，您不会严格使用该理论。 但是，我们仍将致力于这一部分来开发证明—这很有趣，如果您在这些方面争论不休，您可能会得到面试官的良好恩典🙂
We are going to use Polynomial-Time Reduction along with NP-completeness to prove that no efficient polynomial algorithm exists for the Lazy Bartender Problem. Here is how it works
我们将使用多项式时间约简和NP完备性来证明对于懒人调酒师问题不存在有效的多项式算法。 下面是它的工作原理
Start with an instance of known NP-complete problem. There are quite a few. Picking up the right problem for reduction is more of an art than science!
从一个已知的NP完全问题的实例开始。 有很多 。 提出减少问题的正确方法更多的是艺术而不是科学！
Develop a polynomial time algorithm to convert that instance to an instance of the Lazy Bartender Problem. Again, there is no standard recipe for this, you need to use your insight/imagination to do this. 开发多项式时间算法，以将该实例转换为懒人调酒师问题的实例。 同样，没有标准的配方，您需要运用自己的见识/想象力来做到这一点。 Argue that — 争论- Every instance of the known NP-complete problem can be converted to a different instance of the Lazy Bartender problem. 已知NP完全问题的每个实例都可以转换为惰性调酒师问题的不同实例。If we could solve the Lazy Bartender problem, we could also solve the NP-complete problem by first converting it to Lazy Bartender. But that’s impossible! (unless P=NP). By definition, no efficient algorithm exists for any NP-complete problem. Hence, by contradiction, we have proved that even the Lazy Bartender belongs to the NP-complete class, and can not be solved efficiently.
如果我们可以解决Lazy Bartender问题，也可以通过先将其转换为Lazy Bartender来解决NP-complete问题。 但这是不可能的！ (除非P = NP )。 根据定义，没有有效的算法可解决任何NP完全问题。 因此，通过矛盾，我们证明了即使是懒人调酒师也属于NP完全类，并且不能有效地解决。
We are going to use the Vertex Cover problem as the known NP-complete problem for the reduction. Here is how the problem is defined
我们将使用“ 顶点覆盖”问题作为减少的已知NP完全问题。 这是问题的定义方式
You are given a graph G(V, E) with vertex-set V, and edge set E. Find the smallest subset S of the vertices so that every edge in E has at least one end-point in S.
您将得到的曲线图 G(V, E) 具有顶点集 V 和边缘集 E 。 找出最小的子集 S 顶点，使每个边缘 E 在至少一个终点 S 。
Here is an instance of the Vertex Cover problem:
这是“顶点覆盖”问题的一个实例：
1 /|\ / | \ a/ |b \c / | \ 2 3 4 /\ d/ \e / \ 5 6The graph has 6 vertices V = {1, 2, 3, 4, 5, 6}, and 5 edges E = {a, b, c, d, e}. The goal is to find the smallest subset S of V which 'covers' all the edges in E. Of course, the solution in this case is S = {1, 3}. Because every edge in E is either connected to the vertex 1 or 3.
该图具有6个顶点V = {1, 2, 3, 4, 5, 6}和5条边E = {a, b, c, d, e} 。 目标是找到“覆盖” E所有边的V的最小子集S 当然，这种情况下的解是S = {1, 3} 。 因为E每个边都连接到顶点1或3 。
The Vertex Cover problem is NP-complete — no efficient polynomial time algorithm exists to solve it. Here is how we can ‘reduce’ this problem to a seemingly unrelated Lazy Bartender:
顶点覆盖问题是NP完全的-没有有效的多项式时间算法可以解决该问题。 我们可以通过以下方法将这个问题“减少”到看似无关的懒惰调酒师：
Take any arbitrary instance of the Vertex Cover problem, represented by the graph G(V, E).
取顶点覆盖问题的任意实例，由图形G(V, E) 。
Create a new drink for every vertex v in V.
创建每个顶点一个新的饮料v在V 。
Create a customer for every edge e in E.
为E每个边e创建一个客户。
Let e be an edge in the graph connection vertices x and y. Then the customer corresponding to e prefers drinks corresponding to x and y, nothing else! Thus, every customer prefers exactly two drinks!
令e为图连接顶点x和y 。 然后，对应于e的顾客更喜欢对应于x和y饮料，除此之外！ 因此，每个客户都偏爱两种饮料！
The instance of Vertex Cover in the diagram above can be reduced to the following preferences map in the Lazy Bartender
上图中的“ Vertex Cover”实例可以简化为“懒人调酒师”中的以下preferences映射
preferences = { a: {1, 2} b: {1, 3} c: {1, 4} d: {3, 5} e: {3, 6} }The reduction can be achieved using a polynomial time algorithm (by simply iterating over the vertices once). If we could efficiently solve the Lazy Bartender problem, we could also efficiently solve the NP-complete Vertex cover problem! (Which is impossible, unless, again, P=NP). Hence, no polynomial time algorithm exists for the Lazy Bartender.
可以使用多项式时间算法(通过简单地对顶点迭代一次)来实现减少。 如果我们可以有效地解决Lazy Bartender问题，那么我们也可以有效地解决NP完全顶点覆盖问题！ (这是不可能的，除非再次是P = NP)。 因此，对于懒人调酒师不存在多项式时间算法。
Now that we know that no efficient algorithm exists, we have to resort to trying all possible subsets of drinks. Since there are 2 Csubsets of C drinks, the complexity of the algorithm is at least . Here is one recursive implementation for trying all subsets of C.
既然我们知道不存在有效的算法，我们就不得不尝试尝试所有可能的饮料子集。 由于C饮料有2个C子集，因此算法的复杂度至少为。 这是一种尝试C所有子集的递归实现。
// Let's develop a class, and use some of its private variables to store the state during recursive calls. class LazyBartender { public: explicit LazyBartender(std::unordered_map<int, std::vector<int>> preferences) { for (const auto& kv : preferences) { const int customer = kv.first; for (const int drink : kv.second) { if (drinks_to_customers.find(drink) == drinks.end()) { drinks_to_customers[drink] = {customer}; } else { drinks_to_customers[drink].push_back(customer); } } all_customers.push_back(customer); } for (const auto& kv : drinks_to_customers) { all_drinks.push_back(kv.first); } } std::vector<int> best_drinks() { return best_drinks_recursive(0, {}); } private: std::vector<int> best_drinks_recursive(int drink_index, std::vector<int> curr_best_drinks) { // Base case 1: If we have already covered all the customers, no need to // look further. Return the drink-set we have found so far. if (covered_customers.size() == all_customers.size()) { return curr_best_drinks; } // Base case 2: If we have exhausted all the drinks, return. if (drink_index == all_drinks.size()) { if (covered_customers.size() == all_customers.size()) { return curr_best_drinks; } else { return all_drinks; } } // Recursive case 1: exclude current drink index from the set. std::vector<int> index_excluded = best_drinks_recursive(drink_index+1, curr_best_drinks); // Recursive case 2: include the current drink index. curr_best_drink.push_back(all_drinks[drink_index]); std::vector<int> curr_customers = drink_to_customers[drink_index]; for (const int c : curr_customers) { if (covered_customers.find(c) == covered_customers.end()) { covered_customers = 1; } else { covered_customers++; } } std::vector<int> index_included = best_drinks_recursive(drink_index+1, curr_best_drink); curr_best_drink.pop_back(); for (const int c : curr_customers) { covered_customers--; } // Return the best of the two recursive cases if (index_included.size() < index_excluded.size()) { return index_included; } else { return index_excluded; } } std::vector<int> all_drinks; // This is an inverted map constructed from the preferences. // The keys are drink ids, and values are the customers who prefer them. // The map is useful for iterating over all subsets of drinks. std::unordered_map<int, std::vector<int>> drinks_to_customers; // Stores all customers covered by the current set of drinks std::unordered_map<int, int> covered_customers; // The set of all customers, used to check whether the current subset // of drinks covers all of them. std::vector<int> all_customers; };What’s the complexity of the above algorithm? The complexity of a recursive function like best_drinks_recursive can itself be calculated recursively. Let C be the number of drinks, and N be the number of customers. Let T(n) denote the time complexity of best_drink_recursive function on n drinks. How does T(n) depend on T(n-1)? During each call to best_drinks_recursive on n drinks, we call best_drink_recursive on n-1 drink twice! Once with first drink included, and other without the first drink. Moreover, in every call, we potentially iterate over all the customers, N, updating/copying a few arrays/maps etc. As a result,
以上算法的复杂度是多少？ 像best_drinks_recursive这样的递归函数的复杂度本身可以递归计算。 令C为饮料数量， N为顾客数量。 令T(n)表示n饮料的best_drink_recursive函数的时间复杂度。 T(n)如何取决于T(n-1) ？ 在每次调用n饮料的best_drinks_recursive期间，我们两次调用n-1饮料的best_drink_recursive ！ 一次包含第一杯饮料，其他则没有第一杯。 此外，在每次通话中，我们都可能遍历所有客户N ，从而更新/复制一些数组/映射等。结果，
T(n) = 2T(n-1) + O(N)Assuming , and solving the above equation gives us
假设并求解上述方程式，我们得到
T(C) = O(2^c)Here are a few interesting test cases:
以下是一些有趣的测试用例：
Empty preferences dictionary 空首选项字典 Single drink 单饮 ‘popular’ drink: A single drink preferred by all customers “大众”饮品：所有客户都喜欢的一种饮品 A random dictionary like the one in the problem statement 像问题陈述中的字典一样的随机字典 GTEST("Empty Preferences") { LazyBartender l({}); EXPECT_TRUE(l.best_drinks().empty()); } GTEST("Single Drink") { LazyBartender l({1: {1}, 2: {1}, 3: {1}}); EXPECT_THAT(l.best_drinks(), ElementsAre(1)); } GTEST("Popular Drink") { LazyBartender l({1: {5, 1}, 2: {5, 2}, 3: {5, 3}, 4: {5, 4}}); EXPECT_THAT(l.best_drinks(), ElementsAre(5)); } GTEST("Complex Preferences") { LazyBartender l({ 0: {0, 1, 3, 6}, 1: {1, 4, 7}, 2: {2, 4, 7, 5}, 3: {3, 2, 5}, 4: {5, 8}}); EXPECT_THAT(l.best_drinks(), ElementsAre(1, 5)); }Originally published at https://cppcodingzen.com on September 7, 2020.
最初于 2020年9月7日 发布在 https://cppcodingzen.com 上。
翻译自: https://medium.com/swlh/the-lazy-bartender-4c9af7e333a8
相关资源：酒保：酒保-PostgreSQL备份和恢复管理器-源码