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

Question

我对非 BFS 方式非常满意。

假设我可以执行的操作是

1. x - 1
2. x/3(如果 x%3 == 0)
3. x/5(如果 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

也许是这样的？

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");
}

此函数有两种返回方式。

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

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

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

你也可以从另一个角度看这个问题。

“如何使用 +1 *3 和 *5 运算从 Z 值得出 X 值”

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

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;
}