「筆記」一些“基礎”算法

一些“基礎”算法

給定n個元素，問這n個元素組成的每一個集合的所有子集。

最外層就是\(O(2^n)\)枚舉所有集合。如果要按普通方法枚舉子集，應該将\(S1\)從\(S\)開始每次減一，再判斷合法性。然而由于&\(S\)的結果隻減不增，\(S1\)可以通過\(-1\)然後&\(S\)來直接到達最近合法狀态。

複雜度不會證，但是知道是\(O(3^n)\)

更詳細的講解

由于萬惡的老師沒有講基本的搜尋，于是我這裡也跳過啦 XD

如果搜尋樹的深度不确定，那麼可以使用疊代加深搜尋（\(iterative\ deepening\)）

枚舉\(maxd\)表示最深枚舉深度

假設目前深度為\(g(n)\)，樂觀估計至少要\(h(n)\)層才能到達葉結點，那麼\(g(n)+h(n)>maxd\)時，應該剪枝，這就是\(IDA*\)(基于疊代加深的\(A*\)算法。)

傳送門

給出一個分數，要求求出最少的x分之1的形式，如果個數相同，要求最小的數字最大。

考慮搜尋，因為層數不定，是以使用疊代加深搜尋

細節問題需要注意

我們如果把“目前狀态樂觀估計還要\(h(n)\)層才能到達終點”這個\(idea\)用到\(bfs\)上，會不會有好效果？這就是\(A*\)

例如在\(dijkstra\)算法中，我們每次取的是\(d(v)\)最小的點。如果我們加上\(A*\)的思想，就可以每次取\(d(v)+h(v)\)最小的點。(例如說這裡的\(h(v)\)可以是連接配接\(v\)的最小的邊)

我們可以把正常\(bfs\)用的隊列改成優先隊列，每次選\(g(n)+h(n)\)最小的點來更新。

一個地圖，有障礙不能走，要求所有小寫字母到達自己對應的大寫字母

這題可以用\(bfs\)來寫，也可以加入\(A*\)，每個狀态的\(H(n)\)可以估計為每個小寫字母到大寫字母的最短路之和。

代碼先鴿着

hdu2234

雙向搜尋又名折半搜尋。當搜尋的複雜度在指數級的時候，我們可以通過将指數折半的方法降低搜尋複雜度。

具體做法是從初态和終态出發各搜尋一半狀态，産生兩顆深度減半的搜尋樹，兩顆樹交彙在一起形成最終答案，将\(O(n^k)\)降低到\(O(n^{k/2}+n^{k/2+1})\)的複雜度。

給定的各有n個整數的數列\(A\)，\(B\)，\(C\)，\(D\)，從每個數列中取一個數使得四個數加起來等于\(0\)，問這樣的方案數。

\(n^4\)的枚舉肯定會逾時，是以我們先\(n^2\)處理\(A[i] + B[i]\)的值，并把它加到\(sum\)數組中，然後對\(sum\)數組進行排序，然後尋找每一組\((-C[i] - D[j])\)在\(sum\)出現了多少次，把這些次數都加起來，相加後的結果即是答案

話說根本用不到搜尋的hhhh

轉載不必聯系作者，但請聲明出處