RIEŠENIE ÚLOHY VRCHOLOVÉHO POKRYTIA S RÔZNYMI CENAMI VRCHOLOV
Klíčová slova:
maximálna cena, minimálna cena, najvyšší stupeň, najnižší stupeň, vrcholové pokrytie, susedný vrchol, špecifická cena, zbytočný vrcholAbstrakt
Tento článok predkladá algoritmus heuristického riešenia úlohy vrcholového pokrytia s rôznymi cenami vrcholov. Tento algoritmus pozostáva z dvoch algoritmov. Prvý algoritmus prehľadáva vrcholy od maximálneho stupňa zostupne a cenu vybraného vrcholu porovnáva so súčtom cien susedných vrcholov. Ak je cena vybraného vrcholu menšia nanajvýš rovná súčtu cien susedných vrcholov, potom tento vrchol vložíme do hľadanej minimálnej množiny vrcholov. V opačnom prípade vkladáme do minimálnej množiny susedné vrcholy. Druhý algoritmus je založený na vylučovaní zbytočných vrcholov z minimálnej množiny vrcholov, ktorú sme získali po prvom algoritme.
Stažení
Reference
GARREY, M.R., JOHNSON, D. Computers and Intractability. A Guide to the Theory of
NP-completes. W.H.Freeman and Co., San Francisco, 1979, pp. 337.
MEDVIĎ, V. Minimalizácia rozmiestňovania kontrolných bodov v komunikačných
sieťach. Zborník 9. medzinárodnej ved. konf., Vysoká škola dopravy a spojov, Strojnícka
fakulta, Žilina 1993.
MEDVIĎ, V. Zovšeobecnená zasiahnutá množina, Acta mathematika 6, Faculty of
Natural sciences, Const. Public., Nitra 2004, 243 – 248 pp.
MEDVIĎ, V. Transcom 2005, 6-th European Conference of Young Research and Science
Workers in Transport and Telecommunications, Žilina 2005, 95 – 98 pp.
Stahování
Publikováno
Jak citovat
Číslo
Sekce
Licence
Copyright (c) 2020 Vladimír Medviď
Tato práce je licencována pod Mezinárodní licencí Creative Commons Attribution 4.0 .
