text: 力導向圖形繪製演算法是以美觀的方式繪製圖形的一類演算法。它們的目的是將一個圖的節點定位在二維或二維三維空間中，這樣所有的邊或多或少都是等長的，交叉的邊越少越好。方法是根據邊和節點的相對位置在邊和節點的集合中分配力，然後利用這些力模擬邊和節點的運動。雖然圖形繪製可能是一個難題，但作為物理模擬的力導向演算法通常不需要關於平面性等圖論的特殊知識。力.力導向圖繪製演算法把把力賦給圖形繪製的節點集合與邊的集合。通常，基於胡克定律的類似彈簧的吸引力用於相互吸引的圖形中邊的端點，同時使用基於庫侖定律的帶電粒子的排斥力來分隔所有節點對。在該力系統的平衡狀態下，邊的長度往往是一致的。可以使用不基於彈簧和粒子的物理行為的函式來定義邊引力和頂點斥力；例如，一些力導向系統使用吸引力是對數而不是線性的彈簧。一個替代模型為每對節點考慮一個類似彈簧的力formula_1，其中每個彈簧的理想長度formula_2與節點"i"和"j"之間的圖論距離成正比，無需使用單獨的排斥力。極小化節點之間的歐幾里德距離和理想距離之間的差異相當於一個度量多維標度問題。力導向圖可以涉及機械彈簧和電荷斥力以外的力。可以使用類似於重力的力將頂點拉向繪圖空間的固定點；這可用於將斷開連線的圖的不同連通分量拉到一起，否則這些圖會由於斥力而彼此分開，並把具有更大連通分量的節點繪製到圖中更中心的位置。它還可能影響單個元件內的頂點間距。類似的，磁場也可用於有向圖。排斥力可以放在邊緣和節點上，以避免在最終繪圖中重疊或近似於重疊。在諸如圓弧或樣條曲線之類的邊為曲線的圖形中，也可以在這些曲線的控制點上施加力，例如提高它們的角解析度。方法.一旦定義了圖的節點和邊上的力，就可以模擬在這些源下整個圖的行為，就好像它是一個物理系統一樣。在這樣的模擬中，力被施加到節點上，將它們拉得更近或推得更遠。如此反覆迭代，直到系統達到機械平衡狀態；即，從當前迭代到下一次迭代，它們的相對位置不再改變。該平衡中節點的位置用於生成圖形的繪製。對於由理想長度與圖論距離成正比的彈簧定義的力，提供了一種表現非常好的和數學上優雅的方法來極小化這些差異，從而找到對於圖形來說一個好的佈局。也可以採用更直接地搜尋能量極小值的機制，而不是物理模擬或與物理模擬結合使用。這種機制是一般方法的例子，包括模擬退火和遺傳演算法。優點.以下是力導向演算法最重要的優點：缺點.力導向演算法的主要缺點包括：歷史.力導向方法繪製圖形可追溯到Tutte (1963)：多面體圖形可以在平面上繪製的所有面凸出透過固定的平面的外表面的嵌入圖表的入頂點凸位置，在每條邊上放置一個類似彈簧的吸引力，讓系統達到平衡。由於在這種情況下力的簡單性質，系統不會陷入區域性最小值，而是收斂到唯一的全域性最優配置。由於這項工作，具有凸面的平面圖的嵌入有時稱為Tutte嵌入。1984年Eades提出了邊表示引力，所有節點對之間為斥力的模型。此外這方面的先鋒工作還有1991年Fruchterman Reingold。在頂點對之間只使用彈簧力，理想彈簧力等於頂點間的圖論距離的模型，是Kamada Kawai在1989年提出的。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 力導向圖
metadata: https://zh.wikipedia.org/wiki?curid=7603611