1樓：wick
啟發式演算法是什麼？
啟發式演算法是基於人類的經驗和直觀感覺，對一些演算法的優化。比如說A*演算法。
考慮乙個問題：把n個總元素個數為m的資料結構合併起來（假設是線性的）。
每次合併複雜度最壞O(m)，總複雜度O(nm)？
顯然無法接受。
每次把個數少的合併到個數多的？
複雜度O(min(m1,m2)),好像還是沒啥用.
但注意到，每次合併後個數為合併前少的部分的個數的兩倍以上，每個元素最多合併logm次，複雜度O(mlogm)。
我們也可以啟發式合併更加高階的資料結構，如heap，set，splay等，複雜度O(mlog2m)
跑的very fast。
關於複雜度證明：
對於每個節點，它被計算的次數就是它到根節點路徑上的輕邊（連到輕兒子的邊）數
我們只需算出輕邊有幾條
由於每從乙個深度為d的節點沿一條輕邊走到深度（d-1）的節點，子樹大小就至少*2 （這是因為有乙個重兒子》=當前子樹）
所以最多只有logn條輕邊！
故複雜度為O（nlogn）！
例題1：
[HNOI2009] 夢幻布丁 - 洛谷
這題可以用平衡樹維護每種顏色的所有位置，合併時用啟發式合併，
判斷一下有沒有i和i-1,i+1變成同色來更新當前ans。
但是還有更好的做法。
我們只用維護每個點的顏色，在啟發式合併時看一下i-1,i+1的顏色即可。
當x合併到y裡，這是沒問題的。
但如果y合併到x裡，這和將顏色x改為顏色y是相反的。怎麼辦呢？
我們可以直接把這個操作改為把顏色y改為顏色x，只要把後面操作出現的x,y替換一下，這就是等價的。
#include
#include
using
std::
swap
;const
intN
=100010,A
=1000100
;intn,
m,i,
a[N],
dy[A],
ans;
intt[A
],s[A
],next[N
];void
merge
(int&x
,int&y
)}for(i=
t[x];
i;i=
next[i
])a[i
]=y;
t[x]
=0;s
[y]+=
s[x];
s[x]
=0;}
intmain
()ans=1
;for(i
=2;i
<=n;
++i)if
(a[i
]!=a[
i-1])
++ans
;for(i
=1;i
<=1000000;++
i)dy[
i]=i
;while(m
--)}}
例題2：
每次把其他兒子合併到重兒子,再複製到父親即可
#include
#define ll long long
using
namespace
std;
const
intM
=5000+5
,S=5000
;intn,
q;intw[M
],v[M
];intsz[
M],son[M];
vector
M];lldp[M
][M];void
dfs(
intx
,intfa)
}void
add(
intx
,intfa,
llf)}
void
DFS(
intx
,intfa)
memcpy(dp
[x],dp
[son[x
]],sizeof(dp
[x]));
for(
inti=0
;i size ();i++) for( inti=S ;i>=w[ x];i-- )dp[x ][i]= max(dp[ x][i], dp[x][ i-w[ x]]+v [x]);} intmain ()for (inti= 1;i<=n; i++)scanf ("%d%d",& v[i], &w[i ]);dfs(1 ,0);DFS(1 ,0);scanf ("%d",& q);intx,s ;while(q --)return0;} 繁華木馬 最近也發愁，因為啟發式演算法，進化演算法受自身引數影響太大了。我發現改動某些引數可以使A演算法優於B，但是我可以繼續更改B使他優於A，很玄學，只能去文獻中看看別人怎麼比較的，回頭找到了回來回答 公孫金童 相同算例，相同設定 系統，cpu，優化方法，程式語言 相同執行時間 截止時間 多次執行... 諾城Jiwei 簡單來說，偏好是結論 比如我喜歡蘋果多過橘子 而Heuristic 啟發法 是得到這種結論的一種思維過程。當然Heuristic不是唯一的一種思維過程 Heuristic 啟發法 可以被簡單理解成是一種簡單快速處理資訊的方法。這種方法在很多環境下又快又好用，但在一些特定的環境裡會 出... 鳳九 理論上任何乙個優化問題，都會有合適的啟發式演算法來解決。只不過解決得好壞那是另一說。如果啟發式演算法並不令人滿意，那麼可以考慮更複雜的方案，比如深度學習。但是目前深度學習自己有很多問題，比如一是太笨重，二是資料飢餓，三是黑盒特性。第乙個問題就是就是模型太複雜，引數太多，使用可能不便。不過一旦訓...啟發式演算法如何比較效果？
行為經濟學裡的啟發式概念和偏好概念是什麼關係？
用啟發式演算法能求解的問題，用深度強化學習求解是大材小用嗎？