java中如何实现多线程广度优先搜索？

Question

我已经以正常方式完成了广度优先搜索。现在我正在尝试以多线程的方式做到这一点。我有一个在线程之间共享的队列。当我从队列（FIFI队列）中删除节点时，我使用synchronize(LockObject)，所以我想做的是。当我的线程找到解决方案时，所有其他线程将立即停止。

Answer 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