限制對某個字段的併發訪問

因此，在我正在編寫的程序中，我使用雙向寬度優先搜索來搜索圖形。我通過在1個線程中運行1個寬度的第一個搜索並在另一個線程中運行。現在，搜索被稱爲找到了最佳解決方案，當它從其他搜索的元素被擊中，或者當目標被找到時（它從來沒有真正發生過，但僅僅是因爲某種原因。）。限制對某個字段的併發訪問

我遇到的問題是我需要將這個最佳解決方案保存到一個字段中，因爲我需要繼續查找所有解決方案，但是字段值越來越混亂，因爲兩個線程都在同時（我認爲）。

有沒有辦法阻止誰最後到達線程的訪問？我試過使用一個AtomicReference和它的compareAndSet方法，但沒有做到這一點。值仍然會搞砸....

btw我使用java，併爲我使用Callable對象的線程。

來源

2012-09-11 Ethan

在您的設計中是否存在固有的缺陷？假設兩個搜索都在第5級的第一個元素上，並且他們找到了對方。您可以考慮最短路徑爲10.但是如果第二個圖中的第一個搜索WAS中的第五級第二個元素訪問了節點，那麼可能有9長度的解決方案。 –

@Mark我追蹤每次搜索訪問過哪些節點，並在添加之前檢查相反的集合成員資格。基本上，當集合中出現交叉點時，就說找到了解決方案。我應該讓我的執行更清晰 – Ethan

好吧，我想我在我的「答案」中修正了這個例子。我真的很感興趣，你如何在這種情況下得到正確的答案。也許我誤解了你的方法。 –

看起來像是有可能的Livelock或Race condition由於線程的隨機順序而發生。我建議採取不同的方法。（否則某些時候你會遇到NP-Complete）。

我遇到的問題是，我需要保存這個最優解到現場。 ，因爲我需要繼續找到所有解決方案，但是由於兩個線程同時碰到它（我認爲），字段值越來越混亂。

有一種方法可以大大增加您目前的技術。你不應該看每個解決方案，採取Greedy Approach和使用Paralleled versionDijkstra's Shortest Path Algorithm。

最短路徑（或你的情況最優解）

Dijkstra算法是一個圖搜索算法，解決了單源最短路徑問題與非負邊沿路徑成本曲線，產生最短路徑樹。該算法通常用於路由和其他圖算法中的子例程。

線性實現

原始算法圖1（Source）

Parallel PDF Algorithm Linear http://iforce.co.nz/i/w4b43s1r.34o.png

Java實現可以發現Here，和Here

我認爲這些實現是基於BSP樹（但你應該明白我的意思）

並行實現

並行算法如圖2所示。（Source）

有其他方式的算法recursion，加快如果你想優雅。

Parallel PDF Algorithm Atomic http://iforce.co.nz/i/15ndcts5.p3a.png

另一個想法，如果你仍然有問題，可能是使用不同的併發數據結構像Map Reduce或Hadoop而不是使用Threads通過Binary Tree進行搜索，以解決您的搜索。

來源

2012-09-11 00:58:11 Killrawr

以及事情是...我需要找到每個解決方案。這是項目規範的一部分....我想我可以找到所有的解決方案（不需要太長的時間），然後根據長度進行排序以獲得最短的解決方案，但是看到如何獲得一些額外的功勞任意分配，我想在一秒之內彈出最佳解決方案（如果我只是在找到解決方案時立即返回，那麼可以使用我現有的方法實現）。但是，這看起來像是偉大的思想！感謝您的輸入，我一定會讀過它！ – Ethan

讀入[Traveling Sales Man Problem]（http://en.wikipedia.org/wiki/Travelling_salesman_problem）是計算機科學中的一個問題，它是'NP-Hard'（這意味着人們還沒有在多項式時間內求解它），看每一個解決方案的問題是，當你在每個搜索中有''googlemap''的頂點範圍有200萬個可能的解決方案時會發生什麼。理論上你的應用程序應該擴展。最真誠的問候 – Killrawr

我的數據集小得多，而且我知道它不會長到實際上不可能實現的大小。 – Ethan

注：不是一個答案，只是檢查算法

貴的算法實際上產生的最短路徑的有效性？考慮這個圖表：

1A - 2A - 3A - 4A - 5A 
    \   / 
    -- 2B -------

並假設完美的交織（線程每次以完全相同的速率訪問節點）。線程X開始於1A和線程Y開始於5A。順序應該是這樣的：

X visits 1A +{2A, 2B} 
Y visits 5A +{4A} 
X visits 2A +{3A} 
Y visits 4A +{3A, 2B} 
X visits 2B +{4A} 
Y visits 3A +{2A} 
X visits 3A (overlap; shortest path is computed to be 4)

但我們從檢查的最短路徑是3知道：1A - 2B - 4A - 5A。

你的方法如何防止這種情況？無論您採用哪種方法檢查重複項目，我總會在2B之前看到3A重疊。在決定最佳路徑長度之前，你是否總是完成「級別」？

來源

2012-09-11 01:00:04

限制對某個字段的併發訪問

回答

相關問題