Nearest Neighbor

因為目前系站掛了，我只好在這邊碎碎念…

尋找最接近一點的演算法叫做 1NN ，這個問題普遍稱為 Nearest Neighbor Search 1、 Proximity Search 或 Closest Point Search……

咦？「1NN 演算法是用來解決旅行推銷員問題的」？這不是傳說中的 NP-Complete Problem 嗎？ XD

看起來好像會很難實作呢……

—

解決 NNS 問題主要有三種方法：

  1. Linear search：最笨的方法，就是一個一個試。複雜度為 O(n2)。2
  2. Space partitioning：空間中的 Binary Search ，此類型演算法中最簡單的是 kd-tree 3，複雜度大概是 O(n log n)，這個可以參考看看。
  3. Locality sensitive hashing：看不懂它想幹嘛… XD

  1. 其實 NNS 跟我的研究沒有關係，實作這些演算法也不會讓我的研究更有價值…… 只是現在無聊沒事找事作吧！ ↩

  2. 我最近實在太常用斜體和清單了，一直打 HTML 好麻煩，等等有空來裝 Markdown 輔助編輯……
    結果發現 Markdown 還附贈註腳功能，這真是太適合我了。 ↩

  3. 目前看 Wikipedia 的了解，不知道對不對：
    首先要將點切成一個平衡二元樹，所以這將會是一個 很 大 棵 的樹，接下來找最鄰近點時就神奇了，只要沿著樹枝，往祖先的方向尋找，其中一個祖先就是和它最近的點。 ↩

這篇文章讓你覺得...

新奇
0%
溫馨
0%
誇張
0%
難過
0%
實用
0%
高興
0%
無聊
0%
生氣
0%

5 Comments

    • Author

      Joel Lee

    • Date

      August 1, 2007

    • Time

      10:44 pm

    剛才研究了兩小時的 kd-tree 卻沒有一點進展，卡在建立二元樹的地方，這裡需要能夠依照某個欄位排序二維陣列的函式，這個函式我寫不出來 orz

    • Author

      Joel Lee

    • Date

      August 2, 2007

    • Time

      3:38 am

    找到了 Jagged array 的作法，相當的簡單，而且也因此我開始懷疑 Rectangular array 是不是不可能做出我要的效果啊…… （或者說就得 implements 很多 Interface 硬幹自訂出來）

    • Author

      Joel Lee

    • Date

      August 2, 2007

    • Time

      1:19 pm

    改用 Jagged array ，然後成功寫出了 kd-tree……

    接下來我發現我好像不能用 kd-tree……

    kd-tree 可以用來玩 MST ，但是對 K-means 來說似乎沒有用。

    天啊～！！

    • Author

      Joel Lee

    • Date

      August 2, 2007

    • Time

      1:28 pm

    查了一下 Google 發現還是有人用 kd-tree 改進 K-means 的，我感覺好多了… 明天再來看看他們是怎麼應用的……

    • Author

      Joel Lee

    • Date

      August 14, 2007

    • Time

      10:17 am

    An Optical Solution For The Traveling Salesman Problem

    剛好有人提出了新方法來解決旅行推銷員問題，但是… 應該用不到 XD

1 Pingback

  1. 2008-02-28T05:40:26+080020070801 ～epätoivo ¶ 伽藍洞 on February 28, 2008 – 5:40 am
Leave your thoughts
  • You can use some HTML in your comment.
  • Your comment may not display immediately due to spam filtering. Please wait for moderation.