Optymalna triangulacja ośmiokąta foremnego
: 26 lis 2009, o 15:20
Zadanie ze słynnej książki "Wprowadzenie do algorytmów" T.H. Cormen
Dotyczy programowania dynamicznego.
Wyznacz optymalną triangulację ośmiokąta foremnego o boku długości jednostkowej.
Użyj następującej funkcji wagi:
\(\displaystyle{ w(\Delta v_{i} v_{j} v_{k} = |v_{i} v_{j}| + |v_{j} v_{k} + |v_{k} v_{i}|)}\), gdzie \(\displaystyle{ |v_{i} v_{j}|}\) jest odległością euklidesową między wierzchołkami \(\displaystyle{ v_{i}, v_{j}}\)
Dotyczy programowania dynamicznego.
Wyznacz optymalną triangulację ośmiokąta foremnego o boku długości jednostkowej.
Użyj następującej funkcji wagi:
\(\displaystyle{ w(\Delta v_{i} v_{j} v_{k} = |v_{i} v_{j}| + |v_{j} v_{k} + |v_{k} v_{i}|)}\), gdzie \(\displaystyle{ |v_{i} v_{j}|}\) jest odległością euklidesową między wierzchołkami \(\displaystyle{ v_{i}, v_{j}}\)