在 Java 中实现 BFS 以找到从数字 X 到数字 Z 的最快方法

Question

我对非 BFS 方式非常满意。

所以假设我可以做的操作是

x - 1
x / 3 (if x%3 == 0)
x / 5 (if x%5 == 0)

而且我想通过这些操作找到数字 Z 的最快方法。

遗憾的是我不知道如何创建这个队列，有什么想法吗？

例子

x = 19;
y = 4;

BFS "level" 0 = 19 
BFS "level" 1 = 18 (x-1)
BFS "level" 2 = 17(18 - 1),
                6(18 / 3)
BFS "level" 3 = 16(17 - 1), 
                5(6 - 1), 
                2(6 / 3) - do not include, since 2 < y
BFS "level" 4 = ..., 4(5 - 1) ,.. 

Number y found in "level" 4

或

这样可以吗？

while array doesn't contain Y
 for int x: array
  if x%3 == 0
   add x/3 to array
  if x%5 == 0
   add x/5 to array
  add x-1 to array
  delete x from array
  level++

Answer 1

我会尝试构建一棵树（在你的情况下是三元树）。树的每个节点都应包含数字和为获得该数字而执行的操作。节点的叶子是可能的数字，例如，如果当前节点为 15，则叶子为 (<14, -1>, <5, /3>, <3, /5>)，如果为 14，则只有 (<13, -1> ). 你可以构建这棵树直到到达 Z，而不是尝试在树中找到到 Z 的最短路径，应该有一些算法。

Answer 2

也许是这样的？

static class Trace {
    public int currentValue;
    public LinkedList<Integer> path;

    public Trace(int val) { currentValue = val; path = new LinkedList<Integer>(); }
}

static void addToQueue(int value, Trace currentTrace, LinkedList<Trace> queue) {
    Trace nt = new Trace(value);
    nt.path = (LinkedList<Integer>)currentTrace.path.clone();
    nt.path.addLast(value);
    queue.addLast(nt);
}

static LinkedList<Integer> findPath(int from, int to) throws Exception {
    // Safety check
    if (from < to) throw new Exception("from < to");
    LinkedList<Trace> q = new LinkedList<Trace>();

    // Initialize queue with FROM value
    Trace t = new Trace(from);
    t.path.addLast(from);
    q.addLast(t);

    // Repeat till we have an answer
    while (!q.isEmpty()) {
        Trace e = q.getFirst();
        q.removeFirst();
        int cv = e.currentValue;

        // Check if we have a solution 
        if (cv == to) return e.path;


        // Handle steps of -1, /3 and /5
        if (cv-1 >= to)
            addToQueue(cv-1, e, q);

        if (cv%3 == 0 && cv/3 >= to)
            addToQueue(cv/3, e, q);

        if (cv%5 == 0 && cv/5 >= to)
            addToQueue(cv/5, e, q);
    }

    // This will never execute because of existence of linear path
    // of length(levels) FROM - TO
    throw new Exception("no path");
}

这个函数有两种方式return。

一种是当 FROM 小于 TO 时，但这只是一个安全检查。

此 returns 的另一种方式是当前检查的值等于 TO 时。

这个解决方案基于 BFS 总是在一致树上找到最短路径的事实。但是我们不是构建整棵树，而是动态创建树的各个部分。您可以想象一下，您只是在给定时间查看树的一部分并处理它的节点。

你也可以换个角度看这个问题

"How can I reach X value from Z value using +1 *3 and *5 operations"

并且代码最简单，也许编译器可以优化它。我将跳过注释，因为它们与上面代码中的注释类似。

static void addToQueue2(int value, Trace currentTrace, LinkedList<Trace> queue) {
    Trace nt = new Trace(value);
    nt.path = (LinkedList<Integer>)currentTrace.path.clone();
    nt.path.addFirst(value);
    queue.addLast(nt);
}

static LinkedList<Integer> findPath2(int from, int to) throws Exception {
    if (from < to) throw new Exception("from < to");
    LinkedList<Trace> q = new LinkedList<Trace>();
    Trace t = new Trace(to);
    t.path.addFirst(to);
    q.addLast(t);

    while (!q.isEmpty()) {
        Trace e = q.getFirst();
        q.removeFirst();
        int cv = e.currentValue;
        if (cv == from) return e.path;
        if (cv > from) continue;

        addToQueue2(cv+1, e, q);
        addToQueue2(cv*3, e, q);
        addToQueue2(cv*5, e, q);
    }
    throw new Exception("no path");
}

似乎有一种方法可以更快地完成它，但这不是 BFS，我没有证据支持这个代码（它缺乏跟踪和错误检查，但这很容易实现):

static int findPath3(long from, long to) {
    int len = 0;
    while (from != to) {
        if (from % 5 == 0 && from / 5 >= to) {
            from /= 5;
        } else if (from % 3 == 0 && from / 3 >= to) {
            from /= 3;
        } else {
            from--;
        }
        len++;
    }
    return len;
}

在 Java 中实现 BFS 以找到从数字 X 到数字 Z 的最快方法

Implementing BFS in Java to find fastest way from number X to number Z

java

algorithm

search

breadth-first-search