minimum weighted path length
Given a list of weights, , the minimum weighted path length is the minimum of the weighted path length of all extended binary trees that have external nodes with weights taken from . There may be multiple possible trees that give this minimum path length, and quite often finding this tree is more important than determining the path length.
Let . The minimum weighted path length is . A tree that gives this weighted path length is shown below.
Constructing a tree of minimum weighted path length for a given set of weights has several applications, particularly dealing with optimization problems. A simple and elegant algorithm for constructing such a tree is Huffman’s algorithm. Such a tree can give the most optimal algorithm for merging sorted sequences (optimal merge). It can also provide a means of compressing data (Huffman coding), as well as lead to optimal searches.
|Title||minimum weighted path length|
|Date of creation||2013-03-22 12:32:12|
|Last modified on||2013-03-22 12:32:12|
|Last modified by||mathwizard (128)|