gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:42:04 25 4
gpt4 key购买 nike

我对非 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++

最佳答案

也许是这样的?

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

关于java - 在 Java 中实现 BFS 以找到从数字 X 到数字 Z 的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33188558/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com