|
|
|
|
minimum weighted path length
|
(Definition)
|
|
|
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.
|
"minimum weighted path length" is owned by mathwizard. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: Huffman coding, sequences, Huffman's algorithm, algorithm, simple, applications, path length, trees, multiple, external nodes, extended binary trees, weighted path length, weights
There are 3 references to this entry.
This is version 3 of minimum weighted path length, born on 2002-03-08, modified 2004-01-22.
Object id is 2779, canonical name is MinimumWeightedPathLength.
Accessed 6045 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
