Symulowane wyżarzanie w maksymalizacji wagi liści drzewa rozpinającego

• Autorzy: Czaderna P. , Wala K.

Warianty tytułu

EN

Simulated annealing in maximization of the leafs weight of spanning tree

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono model kombinatoryczny problemu maksymalizacji wagi liści drzewa rozpinającego grafu zwykłego. Szczegółowo omówiono trzy procedury generowania drzew sąsiednich do bazowego, które, w procesie poprawy drzewa, są eksploatowane przez klasyczny algorytm symulowanego wyżarzania.

EN

In the paper the combinatorial model of the weighted maximum leaf tree problem of ordinary graph is presented. We give a detailed description of three procedures of the neighboring trees generation to the basis one which are exploited during the course of tree improving process realized by the classical simulated annealing algorithm.

Słowa kluczowe

PL

wyżarzanie symulowane; model kombinatoryczny; problem MLSTP

EN

simulated annealing; combinatorial model; MLSTP

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 45--50
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Czaderna P.

autor

Wala K.

• Katedra Automatyki Akademii Górniczo-Hutniczej, 30-059 Kraków, Al. Mickiewicza 30, tel. [phone],

Bibliografia

• 1. Ahuja R.K., Orlin J.B., Sharma D: Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem. Working Paper, University of Florida, 2001. Submitted for publication.
• 2. Czaderna P.: Algorytmy przybliżone optymalizacji sieci komputerowej modelowanej jako problem MLSTP, dyplomowa praca magisterska (promotor: K. Wala). Wydział EAIiE Akademii Górniczo-Hutniczej, Kraków 2006.
• 3. Fernandes L.M., Gouveia L.: Minimal spanning trees with a constraint on the number of leaves. European J. of Operational Research, Vol.104, 1998, p. 250-261,.
• 4. Loryś K., Zwoźniak G.: Approximation algorithms for Maximum-leaf Spanning Tree for cubic graphs. Mohring R. and Raman R. (Eds), ESA 2002, LNCS2461, Springer-Verlag 2002, p. 686-698.
• 5. Lu H., Ravi R.: The power of local optimization: Approximation algorithms for Maximum-leaf Spanning Tree. Proc. of the Thirtieth Annual Allerton Conf. on Communication, Control and Computing, 1992, p. 533-542.
• 6. Lu FL, Ravi R.: A near-linear-time approximation algorithms for Maximum-leaf Spanning Tree. Journal of Algorithms, Vol. 29, No 1, 1995, p. 132-141.