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廣度優先搜索？
- 4. 廣度優先搜索實現
- 5. 實現A * - 搜索作爲廣度優先搜索/深度優先搜索
- 6. 深度優先搜索 - Java類實現
- 7. 廣度優先搜索二叉搜索樹JavaScript實現
- 8. 廣度優先搜索
- 9. 廣度優先搜索java.lang.NullPointerException
- 10. 在tcl中實現廣度優先搜索
- 11. 在C++中使用CLRS實現廣度優先搜索STL
- 12. 在Python中的廣度優先搜索實現
- 13. 廣度優先搜索和深度優先搜索
- 14. 深度優先搜索和廣度優先搜索瞭解
- 15. 將廣度優先搜索轉換爲深度優先使用Java搜索
- 16. 廣度優先搜索算法方程
- 17. 優先深度優先搜索廣度優先搜索或反之亦然
- 18. 如何實現廣度優先遍歷？
- 19. F＃中的廣度優先搜索（BFS）
- 20. 廣度優先搜索查詢在MYSQL
- 21. 深度或廣度優先搜索？
- 22. 深度優先搜索算法實現
- 23. 多維二維數組廣度優先搜索Java
- 24. Java - 深度優先搜索
- 25. java深度優先搜索
- 26. 廣度優先或深度優先搜索
- 27. 廣度優先與深度優先搜索的輸入/輸出
- 28. 廣度優先搜索/深度優先搜索還是定向圖？
- 29. 功能廣度優先搜索
- 30. BFS代碼（廣度優先搜索）
對不起，請問是什麼問題？如何阻止其他線程？ – Luis
因此，每個線程都將沿着不同的路徑走下去？那是你要的嗎？ –
每個線程都會取一個節點，看看它是否是目標節點，如果不是，他會添加到同一隊列中的4個子節點。 這是我的解決方案。如果有更好的方法，請隨時分享。謝謝 – Kassem