散列圖以查找重複項（包括旋轉和反射版本）

Question

我正在製作一個遊戲，涉及通過圖表求解路徑。根據圖的大小，這可能需要一點時間，所以我想緩存我的結果。

這是我尋找一種算法來散列圖來找到重複。

這對於圖的確切副本很簡單，我只是使用相對於頂角的節點位置。對於旋轉或甚至反射圖形來說，它變得相當複雜一些。我懷疑這不是一個新問題，但我不確定它的術語是什麼？

我的具體情況是在一個網格上，所以一個節點（如果有的話）將總是連接到它的四個鄰居，北，南，東和西。在我當前的實現中，每個節點都存儲一個相鄰節點的數組。

對進一步閱讀或甚至完整算法的建議非常感謝。

我目前的散列實現始於第一個發現它取決於我如何遍歷賽場圖表節點，然後注意到所有的節點相對於它的位置。基本圖將有可能會像哈希：0:1,0:2,1:2,1:3,-1:1,

Answer 1

基於Twitter的談話，讓我改的問題（我希望我這樣做是正確）：

如何比較圖（平面，在網格上），在90度旋轉和反射下被視爲不變。如果使用散列，獎勵點數。

我沒有一個完整的答案，但有幾個想法，可能會有所幫助：

鴻溝問題成獨立解決的子問題。這將使

1. 如何圖表比較給定不變的條件
2. 如何把它們轉化成規範的基礎
3. 如何湊這個規範的基礎上受到權衡（速度，大小，碰撞，.. ）

你可以嘗試在單步驟中解決1和2。一個天真的幾何方法可能如下：

對於旋轉不變性，您可以嘗試計算每個方向的邊緣並旋轉圖形，使主要方向始終指向右側。如果沒有主方向，則可以將該圖形看作其頂點的點雲，並使用特徵向量和原始成分分析（PCA）來獲取主方向並相應地旋轉它。

我沒有反射問題的智能解決方案。我的蠻力方式就是一直創建反射圖。假設你有圖g和反射圖r(g)。如果你想知道是否需要回答h == g || h == r(g)。

現在進入散列： 對於散列，您可能必須權衡速度，大小和衝突。如果你只是使用一串邊緣，你的速度和體積都很高，碰撞也很低。如果你只是接受這個字符串並且使用一些通用的字符串散列器，你會得到不同的結果。

如果您使用較短的散列，並且發生更頻繁的衝突，那麼比較不匹配的圖表可以獲得相當小的成本。匹配圖的成本稍高一些，因爲您必須進行全面比較以確定它們是否匹配。

希望這是某種感覺......

最好，西蒙

更新：在旋轉問題的另一種思路，如果邊緣沒有給出明確的贏家：計算的質心頂點並查看它落在邊界框中心的哪一側。相應旋轉。

Answer 2

我建議你這樣做：

• 做一個函數產生任何圖形的哈希，位置無關。聽起來你已經有了這個。

• 當首先生成了圖形的尋路方案，由散列爲該圖形緩存它...

• ...則還產生圖形的7種其他形式的獨特（旋轉90度;旋轉270度;翻轉X;翻轉Y;翻轉X & Y;沿着一個對角線翻轉;沿着另一對角線翻轉）。你當然可以使用簡單的矢量/矩陣變換來生成這些。對於這7個轉換圖中的每一個，您還可以生成該圖的散列，並緩存相同的尋路解決方案（您首先應用相同的轉換，以便解決方案適當地映射到新的圖形配置）。

• 你完成了。稍後，您的代碼將查找圖形的尋路解決方案，即使它是您找到較早解決方案的圖形的替代（旋轉，翻轉）形式，緩存也已包含正確的解決方案。

我今天早上花了一些時間思考這個問題，我認爲這可能是最優化的解決方案。但我會分享我也在考慮的解決方案的其他過度分析版本...

我在考慮一個事實，即您真正需要的是一個函數，它將採用圖G，並返回G（我將稱之爲G'）的「規範版本」，以及將G轉換爲G'所需的變換矩陣。 （看起來你需要變換，所以你可以將它應用到尋路數據並獲得G的正確路徑，因爲你只需要存儲G'的尋路數據。）當然，你可以查找尋路數據對於G'，將變換矩陣應用於它，並找到尋路解決方案。

問題是，我不認爲有任何明確的和高性能的方式來確定G的「規範版本」，因爲這意味着您必須識別G的所有8個變體，並始終選擇與G'相同的一個變體，基於一些標準。我認爲我可以通過查看圖的每個軸來做一些巧妙的事情，計算沿該軸每一行/列的點數，然後旋轉/翻轉以將軸的更不平衡的一半始終置於頂端或 - 左...換句話說，如果你通過「d」，「q」，「b」，「d」，「p」等形狀，你總是會回到「p」形狀（其中不平衡朝向左上角）。這將有一個很好的屬性，它應該能夠識別圖形沿給定軸對稱時的位置，並且不需要區分該軸上的翻轉版本，因爲它們是相同的。

所以基本上我只是逐行/逐列地計算點數，計算形狀的每一半的點數，然後旋轉/翻轉直到左上角的計數更高。 （請注意，計數對於不同的形狀有時是相同的，因爲所有的功能都是將形狀轉換成所有不同可能排列中的單個規範版本。）

Where對於我來說，決定哪個軸是標準案例中的哪一個軸 - 基本上是處理是否沿着對角軸進行反轉的情況。再一次，對於關於對角軸對稱的形狀，該功能應該認識到這一點，而不是在乎;對於任何其他情況，它應該有一個標準，用於說「具有屬性[???]的形狀的軸在規範版本中是形狀的x軸，而另一個軸是y軸」。如果沒有這種標準，您無法區分兩個關於對角軸翻轉的圖形（例如「p」與「σ」/ sigma）。我試圖使用的標準再次是「不平衡」，但結果卻越來越難以確定，至少是我接近它的方式。 （也許我應該只是將我用於X/Y軸的技術應用到對角軸上？我沒有想過如何工作。）如果您想要採用這樣的解決方案，您可能需要以解決我未能解決的問題，或者放棄擔心將對角軸翻轉的版本視爲等同。

雖然我試圖專注於計算簡單和的解決方案，但我意識到，即使這種求和最終會在運行時在尋路代碼中執行（特別是在大圖上）有些昂貴需要儘可能保持高性能，這是您問題的真正意義）。換句話說，我意識到我們可能都在推翻它。在初始緩存方面略微受到打擊，然後基於該圖的位置獨立散列進行閃電般的查找，這似乎也是一個非常簡單的解決方案。