我已经用常规方式完成了广度优先搜索。现在我正尝试用多线程的方式来实现它。我有一个队列，它在线程之间共享。当从队列中移除一个节点（FIFO队列）时，我使用了 synchronize(LockObject)。我想要做的是，当一个线程找到解决方案时，所有其他线程会立即停止。
回答：
我已经成功地实现了它。我所做的是，我获取了第一层的所有节点，假设有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 类 (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="";}Threads 类 (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: 4Enter the Title and Value for item 1: one 1Enter the Title and Value for item 2: five 5Enter the Title and Value for item 3: ten 10Enter the Title and Value for item 4: twenty 20Enter the Amount of Money: 150Number of Threads (Muste be less than the number of items): 2