iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
Software Development

圖論與演算法之間的相互應用系列 第 29

近似最短路徑 (9)

11.9 賦距空間與 L1 嵌入的 Bourgain 定理

圖上的距離也滿足賦距空間(metric space)的定義:非負距離、對稱性、遞移律、三角不等式。
如果我們將圖上的點對應到 k 維的向量空間,那麼只要 k 足夠小,就可以很有效率地計算近似距離。

k 維向量空間的 L1距離是這樣定義的:把每一個維度數字相差的絕對值累加起來,就是距離。
今天來說說一個把任意賦距空間投射到 O(log^2 n) 維度的 L1距離之向量空間,且距離的誤差不超過原先的 O(log n) 倍的 Bourgain 定理(證明略):

對於所有 i=1, 2, …, log n 以及 j = 1, 2, …, 1000 log n;我們以 2^{-i} 的機率(這個機率只與 i 有關、與 j 無關) 均勻取樣圖上的點集合 A_ij。接著,對於圖上每一個點 x,我們定義 k=1000 * log^2 n 維度的向量:第 (i, j) 維度的數值就是 x 到 A_ij 之間的點集合任一點的最短距離 dist(x, A_ij)。

這個方法建構出來的向量,要表達它也需要 O(log^3 n)-bits,誤差在計算距離且除以 log n 之後也為 O(log n),不過它不只適用於任何圖,也適用於任何 n 筆資料的賦距空間,相當巧妙。

除了 L1 距離,Bourgain 的定理也適用於任何的 Lp-距離 (只有誤差要稍微調整一下,但仍為 O(log n))。

參考資料:
https://lucatrevisan.github.io/teaching/expanders2016/lecture10.pdf


上一篇
近似最短路徑 (8)
下一篇
第 k 短路徑問題 (1)
系列文
圖論與演算法之間的相互應用30

1 則留言

0
juck30808
iT邦新手 3 級 ‧ 2021-10-14 12:34:43

恭喜即將邁入完賽階段~

卡卡恩 iT邦新手 5 級 ‧ 2021-10-14 13:28:12 檢舉

/images/emoticon/emoticon37.gif/images/emoticon/emoticon41.gif

我要留言

立即登入留言