minimum weighted path length

Given a list of weights, $W:=\\left\\{w_{1},w_{2},\\dots,w_{n}\\right\\}$ , theminimum weighted path length is the minimum of the weighted path length of all extended binary trees that have $n$ external nodes with weights taken from $W$ . 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.

Example

Let $W:=\\left\\{1,2,3,3,4\\right\\}$ . The minimum weighted path length is $29$ . A tree that gives this weighted path length is shown below.

Applications

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 $n$ sorted sequences (optimal merge). It can also provide a means of compressing data (Huffman coding), as well as lead to optimal searches.

单词	MinimumWeightedPathLength
释义	minimum weighted path length Given a list of weights, $W:=\\left\\{w_{1},w_{2},\\dots,w_{n}\\right\\}$ , theminimum weighted path length is the minimum of the weighted path length of all extended binary trees that have $n$ external nodes with weights taken from $W$ . 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. Example Let $W:=\\left\\{1,2,3,3,4\\right\\}$ . The minimum weighted path length is $29$ . A tree that gives this weighted path length is shown below. Applications 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 $n$ sorted sequences (optimal merge). It can also provide a means of compressing data (Huffman coding), as well as lead to optimal searches.
随便看	measurable space Measure measure Measurement MeasureOnABooleanAlgebra measure on a Boolean algebra Measurepreserving measure-preserving MeasureZero measure zero MeasureZeroInmathbbRn measure zero in ℝ^n MedialQuasigroup medial quasigroup MedialTriangle medial triangle Median median MedianOfADistribution median of a distribution MedianOfTrapezoid median of trapezoid Meet meet MeetContinuous