3
我以正常的方式完成了广度优先搜索。 现在我试图用多线程的方式来做到这一点。 我有一个线程之间共享的队列。 我使用同步（锁定对象）时，我从队列（FIFI队列） 删除节点，所以我想要做的是。 当我的线程发现一个解决方案时，所有其他线程将立即停止。如何在java中实现多线程广度优先搜索？
A
回答
1
我已经成功实现了它。 我所做的就是让第一层中的所有节点，比方说4个节点。 然后我有2个线程。每个节点需要2个节点并生成子节点。每当博德找到解决方案时，他必须报告他找到解决方案的级别并限制搜索级别，以便其他线程不超过级别。 只有报告方法应该同步。
我没有在对硬币的代码更改问题： 这是我的代码，供其他人使用 - 不完美，但确实工作:) -
主类（CoinsProblemBFS.java）
package coinsproblembfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
*
* @author Kassem M. Bagher
*/
public class CoinsProblemBFS
{
private static List<Item> MoneyList = new ArrayList<Item>();
private static Queue<Item> q = new LinkedList<Item>();
private static LinkedList<Item> tmpQ;
public static Object lockLevelLimitation = new Object();
public static int searchLevelLimit = 1000;
public static Item lastFoundNode = null;
private static int numberOfThreads = 2;
private static void InitializeQueu(Item Root)
{
for (int x = 0; x < MoneyList.size(); x++)
{
Item t = new Item();
t.value = MoneyList.get(x).value;
t.Totalvalue = MoneyList.get(x).Totalvalue;
t.Title = MoneyList.get(x).Title;
t.parent = Root;
t.level = 1;
q.add(t);
}
}
private static int[] calculateQueueLimit(int numberOfItems, int numberOfThreads)
{
int total = 0;
int[] queueLimit = new int[numberOfThreads];
for (int x = 0; x < numberOfItems; x++)
{
if (total < numberOfItems)
{
queueLimit[x % numberOfThreads] += 1;
total++;
}
else
{
break;
}
}
return queueLimit;
}
private static void initializeMoneyList(int numberOfItems, Item Root)
{
for (int x = 0; x < numberOfItems; x++)
{
Scanner input = new Scanner(System.in);
Item t = new Item();
System.out.print("Enter the Title and Value for item " + (x + 1) + ": ");
String tmp = input.nextLine();
t.Title = tmp.split(" ")[0];
t.value = Double.parseDouble(tmp.split(" ")[1]);
t.Totalvalue = t.value;
t.parent = Root;
MoneyList.add(t);
}
}
private static void printPath(Item item)
{
System.out.println("\nSolution Found in Thread:" + item.winnerThreadName + "\nExecution Time: " + item.searchTime + " ms, " + (item.searchTime/1000) + " s");
while (item != null)
{
for (Item listItem : MoneyList)
{
if (listItem.Title.equals(item.Title))
{
listItem.counter++;
}
}
item = item.parent;
}
for (Item listItem : MoneyList)
{
System.out.println(listItem.Title + " x " + listItem.counter);
}
}
public static void main(String[] args) throws InterruptedException
{
Item Root = new Item();
Root.Title = "Root Node";
Scanner input = new Scanner(System.in);
System.out.print("Number of Items: ");
int numberOfItems = input.nextInt();
input.nextLine();
initializeMoneyList(numberOfItems, Root);
System.out.print("Enter the Amount of Money: ");
double searchValue = input.nextDouble();
int searchLimit = (int) Math.ceil((searchValue/MoneyList.get(MoneyList.size() - 1).value));
System.out.print("Number of Threads (Muste be less than the number of items): ");
numberOfThreads = input.nextInt();
if (numberOfThreads > numberOfItems)
{
System.exit(1);
}
InitializeQueu(Root);
int[] queueLimit = calculateQueueLimit(numberOfItems, numberOfThreads);
List<Thread> threadList = new ArrayList<Thread>();
for (int x = 0; x < numberOfThreads; x++)
{
tmpQ = new LinkedList<Item>();
for (int y = 0; y < queueLimit[x]; y++)
{
tmpQ.add(q.remove());
}
BFS tmpThreadObject = new BFS(MoneyList, searchValue, tmpQ);
Thread t = new Thread(tmpThreadObject);
t.setName((x + 1) + "");
threadList.add(t);
}
for (Thread t : threadList)
{
t.start();
}
boolean finish = false;
while (!finish)
{
Thread.sleep(250);
for (Thread t : threadList)
{
if (t.isAlive())
{
finish = false;
break;
}
else
{
finish = true;
}
}
}
printPath(lastFoundNode);
}
}
项类（Item.java）
package coinsproblembfs;
/**
*
* @author Kassem
*/
public class Item
{
String Title = "";
double value = 0;
int level = 0;
double Totalvalue = 0;
int counter = 0;
Item parent = null;
long searchTime = 0;
String winnerThreadName="";
}
线程类（BFS。JAVA）
package coinsproblembfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
*
* @author Kassem M. Bagher
*/
public class BFS implements Runnable
{
private LinkedList<Item> q;
private List<Item> MoneyList;
private double searchValue = 0;
private long start = 0, end = 0;
public BFS(List<Item> monyList, double searchValue, LinkedList<Item> queue)
{
q = new LinkedList<Item>();
MoneyList = new ArrayList<Item>();
this.searchValue = searchValue;
for (int x = 0; x < queue.size(); x++)
{
q.addLast(queue.get(x));
}
for (int x = 0; x < monyList.size(); x++)
{
MoneyList.add(monyList.get(x));
}
}
private synchronized void printPath(Item item)
{
while (item != null)
{
for (Item listItem : MoneyList)
{
if (listItem.Title.equals(item.Title))
{
listItem.counter++;
}
}
item = item.parent;
}
for (Item listItem : MoneyList)
{
System.out.println(listItem.Title + " x " + listItem.counter);
}
}
private void addChildren(Item node, LinkedList<Item> q, boolean initialized)
{
for (int x = 0; x < MoneyList.size(); x++)
{
Item t = new Item();
t.value = MoneyList.get(x).value;
if (initialized)
{
t.Totalvalue = 0;
t.level = 0;
}
else
{
t.parent = node;
t.Totalvalue = MoneyList.get(x).Totalvalue;
if (t.parent == null)
{
t.level = 0;
}
else
{
t.level = t.parent.level + 1;
}
}
t.Title = MoneyList.get(x).Title;
q.addLast(t);
}
}
@Override
public void run()
{
start = System.currentTimeMillis();
try
{
while (!q.isEmpty())
{
Item node = null;
node = (Item) q.removeFirst();
node.Totalvalue = node.value + node.parent.Totalvalue;
if (node.level < CoinsProblemBFS.searchLevelLimit)
{
if (node.Totalvalue == searchValue)
{
synchronized (CoinsProblemBFS.lockLevelLimitation)
{
CoinsProblemBFS.searchLevelLimit = node.level;
CoinsProblemBFS.lastFoundNode = node;
end = System.currentTimeMillis();
CoinsProblemBFS.lastFoundNode.searchTime = (end - start);
CoinsProblemBFS.lastFoundNode.winnerThreadName=Thread.currentThread().getName();
}
}
else
{
if (node.level + 1 < CoinsProblemBFS.searchLevelLimit)
{
addChildren(node, q, false);
}
}
}
}
} catch (Exception e)
{
e.printStackTrace();
}
}
}
样品输入：
Number of Items: 4
Enter the Title and Value for item 1: one 1
Enter the Title and Value for item 2: five 5
Enter the Title and Value for item 3: ten 10
Enter the Title and Value for item 4: twenty 20
Enter the Amount of Money: 150
Number of Threads (Muste be less than the number of items): 2
2
我假设你正在为你的BFS遍历一棵树。
创建一个线程池。 为节点中的每个未发掘的子节点检索线程池中的线程（可能使用Semaphore）。将子节点标记为“已探索”并以BFS方式探索节点的子节点。当您找到解决方案或完成了所有节点的探索后，请释放信号量。
^我从来没有这样做过，所以我可能错过了一些东西。
+0
实际上我正在构建树并在同一时间检查。 – Kassem
+0
实际上，我正在建设树，我试图解决硬币问题，这是找到给定数量的钱的最佳组合。最好的组合意味着更少的硬币但更多的价值 – Kassem
+0
我这样做的方式：从队列中的根节点开始，我带这个节点并展开它（展开意味着增加4个孩子，每个孩子代表一个硬币类型;例如：1分，5分10分，20分）之后，我把队列中的第一个节点，并检查它的总价值是我正在寻找（如21美分），如果不是，那么我将添加4个孩子到这个节点，并将其添加到队列中（通过添加孩子到节点我的意思是我创建类型硬币的对象 - 我创建 - 并在该对象内是一个变量的类型硬币也代表了母币）。 – Kassem
2
假设你想要迭代地做这件事（参见底部为什么可能有更好的封闭解决方案），这对于执行多线程并不是一个大问题。问题是如果你不依赖于以前的结果，那么多线程是非常好的，但是在这里你需要最小数量的硬币。
正如您所指出的那样，广度优先解决方案可以保证一旦您达到期望的数量，在单个线程环境中，您将不会有更少硬币的解决方案。但是，在多线程环境中，一旦您开始计算解决方案，就无法保证它会在其他解决方案之前完成。让我们设想一下21的值：它可以是20c硬币和1c或4c硬币和1c;如果两者都同时计算，则不能保证第一个（也是正确的）解决方案会先完成。在实践中，这种情况不太可能发生，但是当你使用多线程时，你希望解决方案能够在理论上工作，因为多线程总是在演示中失败，无论它们是否应该在宇宙的死亡之前不会失败。
现在您有两种可能的解决方案：一种是在每个级别的开始处引入阻塞点;直到上一级完成后才能开始该级别。另一种是一旦你达到解决方案继续进行所有的计算比当前结果更低的水平（这意味着你不能清除其他）。可能所有需要的同步都是通过单线程来获得更好的性能，但让我们继续。
对于第一种解决方案，自然形式是反复增加等级。您可以使用由happymeal提供的解决方案和Semaphore。另一种方法是使用java提供的新类。
CoinSet getCoinSet(int desiredAmount) throws InterruptedException {
// Use whatever number of threads you prefer or another member of Executors.
final ExecutorService executor = Executors.newFixedThreadPool(10);
ResultContainer container = new ResultContainer();
container.getNext().add(new Producer(desiredAmount, new CoinSet(), container));
while (container.getResult() == null) {
executor.invokeAll(container.setNext(new Vector<Producer>()));
}
return container.getResult();
}
public class Producer implements Callable<CoinSet> {
private final int desiredAmount;
private final CoinSet data;
private final ResultContainer container;
public Producer(int desiredAmount, CoinSet data, ResultContainer container) {
this.desiredAmount = desiredAmount;
this.data = data;
this.container = container;
}
public CoinSet call() {
if (data.getSum() == desiredAmount) {
container.setResult(data);
return data;
} else {
Collection<CoinSet> nextSets = data.addCoins();
for (CoinSet nextSet : nextSets) {
container.getNext().add(new Producer(desiredAmount, nextSet, container));
}
return null;
}
}
}
// Probably it is better to split this class, but you then need to pass too many parameters
// The only really needed part is to create a wrapper around getNext, since invokeAll is
// undefined if you modify the list of tasks.
public class ResultContainer {
// I use Vector because it is synchronized.
private Vector<Producer> next = new Vector<Producer>();
private CoinSet result = null;
// Note I return the existing value.
public Vector<Producer> setNext(Vector<Producer> newValue) {
Vector<Producer> current = next;
next = newValue;
return current;
}
public Vector<Producer> getNext() {
return next;
}
public synchronized void setResult(CoinSet newValue) {
result = newValue;
}
public synchronized CoinSet getResult() {
return result;
}
}
这仍然存在执行现有任务的问题;然而，解决这个问题很简单;将线程执行程序传递给每个Producer（或容器）。然后，当您找到结果时，请调用executor.shutdownNow。正在执行的线程不会中断，但每个线程中的操作都很简单，因此它可以快速完成;尚未启动的可运行程序无法启动。
第二个选项意味着您必须让所有当前任务完成，除非您跟踪您在每个级别运行了多少任务。尽管如此，你不再需要跟踪关卡的水平，而且你也不需要while循环。相反，你只需要调用
executor.submit(new Producer(new CoinSet(), desiredAmount, container)).get();
，然后调用方法是非常相似的（假设你已经在制作执行人）：
public CoinSet call() {
if (container.getResult() != null && data.getCount() < container.getResult().getCount()) {
if (data.getSum() == desiredAmount)) {
container.setResult(data);
return data;
} else {
Collection<CoinSet> nextSets = data.addCoins();
for (CoinSet nextSet : nextSets) {
executor.submit(new Producer(desiredAmount, nextSet, container));
}
return null;
}
}
}
，你也必须修改container.setResult，因为你不能依赖的，如果和设置尚未设置一些其他线程值之间（线程真烦，不是吗？）
public synchronized void setResult(CoinSet newValue) {
if (newValue.getCount() < result.getCount()) {
result = newValue;
}
}
在以前所有的答案，CoinSet.getSum（）的返回s是集合中硬币的总和，CoinSet.getCount（）返回硬币的数量，并且CoinSet.addCoins（）返回CoinSet集合，其中每个元素是当前CoinSet加上每个可能不同值的一个硬币
注意：对于值为1,5,10和20的硬币的问题，最简单的解决方法是取金额并将其除以最大的硬币。然后取其中的模数，并使用下一个最大值，依此类推。这是你将需要的最低金额。当下列属性为真时，此规则适用（AFAICT）：如果对于所有连续的硬币值对（即在这种情况下，1-5，5-10，10-20），您可以达到下层元素的任何整数倍与使用更大的元素和无论什么硬币都是必需的较少数量的硬币对。你只需要证明它对这两个元素的最小公倍数（在它重复自己之后）
2
我收集你对快乐鲜啤酒的评论，你试图找到如何达到特定数量的钱通过添加1c，5c，10c和20c的硬币。
由于每个硬币面值分越下越大硬币的面额，这可以在一定的时间来解决如下：
int[] coinCount(int amount) {
int[] coinValue = {20, 10, 5, 1};
int[] coinCount = new int[coinValue.length];
for (int i = 0; i < coinValue.length; i++) {
coinCount[i] = amount/coinValue[i];
amount -= coinCount[i] * coinValue[i];
}
return coinCount;
}
拿回家的消息：尝试诉诸多线程之前来优化你的算法，因为算法改进可以产生更大的改进。
+1
完全同意正确的解决方案不是去多线程，而是优化它（我甚至在我的笔记中）。但是这看起来更像是一本教科书练习。事实上，如果你在没有优化的情况下首先进入广度，那么当你达到8个硬币时，你可以有4^8（2^16，aprox 32E3）解决方案，每个int 4个字节的内存为256KB。 – Luis
相关问题
- 1. 如何实现广度优先搜索？
- 2. 深度优先搜索 - Java类实现
- 3. 广度优先搜索java.lang.NullPointerException
- 4. LISP - 广度优先搜索
- 5. 在tcl中实现广度优先搜索
- 6. 在C++中使用CLRS实现广度优先搜索STL
- 7. 在Python中的广度优先搜索实现
- 8. 广度优先搜索和深度优先搜索
- 9. 广度优先搜索算法方程
- 10. 如何实现广度优先遍历？
- 11. F＃中的广度优先搜索（BFS）
- 12. java深度优先搜索
- 13. 广度优先与深度优先搜索的输入/输出
- 14. 广度优先或深度优先搜索
- 15. 最短路径 - 广度优先搜索
- 16. 广度优先搜索：骑士覆盖
- 17. 广度优先搜索练习 - AI
- 18. 广度优先搜索不起作用
- 19. 广度优先搜索错误输出
- 20. 广度优先搜索 - 错误结果
- 21. 广度优先搜索使用Javascript
- 22. 如何在java中的二叉树上实现深度优先搜索（DFS）？
- 23. 在python中优化广度优先搜索
- 24. 广度优先搜索完整图的复杂度是多少？
- 25. 广度优先算法的实现
- 26. 深度优先搜索在Java
- 27. java中的深度优先搜索
- 28. 如何通过对象树实现深度优先搜索？
- 29. 如何知道我在使用BFS（广度优先搜索）的搜索级别？
- 30. Java树结构和广度优先搜索
对不起，请问是什么问题？如何阻止其他线程？ – Luis
因此，每个线程都将沿着不同的路径走下去？那是你要的吗？ –
每个线程都会取一个节点，看看它是否是目标节点，如果不是，他会添加到同一队列中的4个子节点。 这是我的解决方案。如果有更好的方法，请随时分享。谢谢 – Kassem