跳舞鏈接的複雜性

Question

我正在寫一個數獨解算器，並考慮實現它的算法。我知道回溯具有O（n^m）的時間複雜度，其中n是每個正方形和m是空白的空格的數量。但我無法精確分析跳舞鏈接。有人可以解釋它是什麼嗎？

Answer 1

跳舞鏈接（算法X）設計我的唐納德Knuth也更壞的情況下O（N^N^2）還挺。它實際上比這少得多。

當我編寫兩個數獨求解器時，我發現了這個問題，其中一個求解器沒有跳舞鏈接。

如果您引入了前瞻性檢查（在您嘗試繼續進行深度優先搜索（在搜索世界中也稱爲修剪），請確保該數字是有效的播放，那麼您可以節省算法以免浪費時間。如果這是你做的唯一改進，那麼你仍然可能遇到最糟糕的情況（即第一個數字是最大數字）。

跳舞鏈接，如果你想這樣想，跳舞鏈接是一個轉發檢查 - 優先級隊列 - 深度優先搜索。真正的速度來自覆蓋網格這就是說，您不需要重新計算剩餘的可能性（如果您正確實施），這將是更耗時的過程你的數獨求解器，也可以設置算法t o選擇（點，行，列或框）留下的可能性最小，以減少分支大小。

這裏有幾個鏈接，真的幫了我讓我的求解器：

https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html

這個問題的大O的複雜性仍然是O（N * N * N），因爲我們仍然從一個點到另一個點並嘗試n個值。只是碰巧Ω（x）其中x是兩個實現的空白空間數量，但跳舞鏈接每步的計算時間要少得多。

這看起來像跳舞鏈接只是一個DFS實現，因爲它是。 4乘4的最壞情況將是4 * 3 * 2 * 3 * 2 * 2 * 2 * 2 * 2這是由於該列的啓發式我們選擇覆蓋網格的列數最少防止大規模分支。