c++ - 倒水 : Graph Implementation Problem - Shortest Path/Dijkstra's (? )

Question

编辑:重新发布；尝试了更多问题并重新发布。在这一点上我真的迷路了。

今天要解决这个小图问题，想知道是否有人对此有任何可能的解决方案/见解。

给定两个容器，其中一个可以容纳 a 升水，另一个可以容纳 b 升水，确定在其中一个容器中准确获得目标升水所需的步骤数，如果不能，则为 -1完成。

一开始两个容器都是空的。以下操作计为“步骤”:

• 清空容器 er
• 装满一个容器
• 将水从一个容器倒到另一个容器中，不要溢出，直到其中一个容器装满或倒空

为了帮助您入门，我们为您提供了一个 Node 和一个 Graph 类。您的工作是实现函数 Graph createGraph(int capacity_a, int capacity_b)，它构建一个包含给定两个容器容量的所有可能容器状态的图，以及 int findSolution(Graph g, int target)，它执行图遍历并返回最小步数。

您可以根据需要修改结构，或者在不使用提供的结构的情况下构建自己的解决方案。我们只会测试您的 int waterPouring(int a, int b, int target) 函数。

提示:哪种算法可以保证达到目标所需的最少步数？

我最初的猜测是 Dijkstra 对 findSolution() 的猜测，并试图翻译一些伪代码，但没有成功。我(认为)我正确地实现了 createGraph。不确定去哪里/是否有更好的方法来做到这一点。这是代码:

谢谢!

浇水.cpp:

 #include <unordered_map>
 #include <queue>
 #include <vector>

 using namespace std;

 #define EMPTY 0

 class Node {
     public:
         int a;
         int b;
         vector<Node *> neighbors;
         Node () : a(EMPTY), b(EMPTY), neighbors() {}
         Node (const int &a_, const int &b_) : a(a_), b(b_), neighbors() {}
             Node (const int &a_, const int &b_, const vector<Node *> &neighbors_) : a(a_), b(b_), neighbors(neighbors_) {}
    Node (const Node &tmpNode) : a(tmpNode.a), b(tmpNode.b), neighbors() {}
    bool operator==(const Node & b_node)
    {
        return a == b_node.a && b == b_node.b;
    }
    Node &operator=(const Node & b_node) {
        // WARNING: This operator does not copy the vector
        a = b_node.a;
        b = b_node.b;
        return *this;
    }
 };

  struct Graph {
     vector<Node *> nodes;
 };


 Graph createGraph(int capacity_a, int capacity_b) {
    // TODO
    Graph g;
    Node * capacityNode = new Node(capacity_a, capacity_b);
    for (int i = 0; i < g.nodes.size(); i++) {
        g.nodes.push_back(capacityNode);
    }
    return g;
}

 int findSolution(Graph g, int target) {
     // TODO: returns minimum number of steps to reach target liters of 
 water (or -1)
     for (int& node : g) {
      // not sure
     }
     return -1;
 }

 int waterPouring(int a, int b, int target) {
     // Call createGraph
     // Call findSolution
     Graph stateMachineGraph = createGraph(a, b);
     int steps = findSolution(stateMachineGraph, target);
     for (Node *graphNode : stateMachineGraph.nodes)
    {
            delete graphNode;
    }
return steps;
}

Answer 1

如果您可以接受不使用图表的解决方案(前提是任务描述允许)，您可以执行以下操作:

假设您有两个容器，容量为 a 和 b，最后您需要得到 c 升。

假设您有两个容量为 a 和 b 的容器，您最终需要得到 c 升。

首先观察，您被允许执行的每个操作都会移动 x * a + y * b 升水。例如。如果您将水从第二个完整的容器中倒到第一个容器中，您将倾倒 1 * b - 1 * a。你可以继续说服自己这是真的。这给了我们以下等式:

x * a + y * b = c

这是一个丢番图方程，如果 gcd(a, b) 除 c(参见 Bézout's identity)，它有一个解。您可以使用 extended Euclidean algorithm 解决它.如果 c 小于 max(a, b)，则 x 或 y 小于零。假设 x > 0。然后你需要装满 a-container x 次，将水从它倒进 b-container 清空它 y次。

示例:a = 9、b = 5、c = 6。我们有

-1 * 9 + 3 * 5 = 6

所以，我们需要

0 5 // Full the second (1)
5 0 // Pour to the first
5 5 // Full the second (2)
9 1 // Pour to the first
0 1 // Empty the first (-1)
1 0 // Pour to the first
1 5 // Full the second (3)
6 0 // Pour to the first

但是如果你真的想用graph，那么

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>

struct Node { int a, b; };

class Graph {
public:
    std::vector<std::pair<Node, std::vector<int>>> nodes;

    static Graph Create(int a, int b) {
        auto index = [a,b](int i, int j) {
            return i * (b + 1) + j;
        };

        Graph g;
        for (int i = 0; i <= a; ++i) {
            for (int j = 0; j <= b; ++j) {
                std::vector<int> adj;
                if (i < a) adj.push_back(index(a, j));
                if (i > 0) adj.push_back(index(0, j));
                if (j < b) adj.push_back(index(i, b));
                if (j > 0) adj.push_back(index(i, 0));
                int da = std::min(a - i, j);
                int db = std::min(b - j, i);
                adj.push_back(index(i + da, j - da));
                adj.push_back(index(i - db, j + db));
                std::sort(adj.begin(), adj.end());
                adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
                g.nodes.push_back({ { i,j }, adj });
            }
        }
        return g;
    }

    // Breadth-first search
    std::pair<int, std::vector<int>> Shortest(int target) const {
        std::vector<bool> visited(nodes.size(), 0);
        std::vector<int> dist(nodes.size(), std::numeric_limits<int>::max());
        std::vector<int> prev(nodes.size(), -1);
        std::queue<int> q;
        int cur_dist = 0;
        q.push(0); visited[0] = true; dist[0] = 0;
        while (q.size() > 0) {
            int index = q.front(); q.pop();
            for (auto i : nodes[index].second) {
                if (nodes[i].first.a == target || nodes[i].first.b == target) {
                    int j = index;
                    std::vector<int> path = { i, index };
                    while (prev[j] != -1) {
                        path.push_back(j = prev[j]);
                    }                    
                    return { dist[index] + 1, path };
                }
                if (!visited[i]) {
                    q.push(i); visited[i] = true; dist[i] = dist[index] + 1; prev[i] = index;
                }
            }
        }
        return { -1, {} };
    }
};

int main()
{
    const auto g = Graph::Create(9, 5);
    const auto p = g.Shortest(6);
    for (int i = (int)p.second.size() - 1; i >= 0; --i) {
        std::cout << g.nodes[p.second[i]].first.a << " " << g.nodes[p.second[i]].first.b << std::endl;
    }
    std::cout << std::endl << p.first << std::endl;
    return 0;
}

输出是一样的:

0 0
0 5
5 0
5 5
9 1
0 1
1 0
1 5
6 0

8