Fróðskaparrit - 01.01.1999, Blaðsíða 258

262
NEWS AND PROGRESS 1998
sured using the rectilinear (or Lj) distance.
This thesis is about algorithms for solv-
ing Euclidean and rectilinear Steiner tree
problems. New exact and heuristic algo-
rithms for these problems are evaluated by
performing extensive computational exper-
iments. The thesis covers a full range of al-
gorithms for the Euclidean problem: Fast
greedy heuristics with an O (n log n) worst-
case running time behaviour; powerful lo-
cal search algorithms that provide near-op-
timal solutions quickly; and efficient, exact
algorithms that solve problem instances
with more than 2,000 terminals to optimal-
ity. The new heuristics provide better solu-
tions faster than any other heuristic pro-
posed in the literature and the new, exact al-
gorithm solves problem instances that are
of an order of magnitude greater than those
previously solved.
The efficiency of the proposed algo-
rithms stems from a structural property of
optimal solutions to these two problems.
The optimal Steiner tree breaks into so-
called full Steiner trees (FSTs) in which all
terminals are leaves. These FSTs are typi-
cally very small (seldom spanning more
than six terminals) and have many well-es-
tablished properties that may be exploited
efficiently by using geometric structures.
The thesis is a collection of six research
papers. Five of these are on the Euclidean
and rectilinear Steiner tree problems, while
the last one presents a tabu search algorithm
for another geometric-plane problem, the
travelling salesman problem. The thesis
begins with a short introduction to algo-
rithms for planar Steiner tree problems.
Henda ritgerð er um algoritmur til at
loysa euklidiska og rektlinjaða Steiner pro-
blemið. Serstakliga eru eksaktar og heurist-
iskar algoritmur eftirmettar við at gera um-
fatandi royndir á teldu. Ritgerðin fevnir um
øll sløg av algoritmum - serliga hvat tí
euklidiska probleminum viðvíkur:
Skjótar algoritmur við 0(n log n) koyri-
tíð, góðar lokalar leitialgoritmur, sum finna
loysnir av høgari góðsku, og effektivar eks-
aktar algoritmur, sum kunnu finna optimal-
ar loysnir til problem við meira enn 2000
terminalum. Teir nýggju heuristikkarnir
finna betri loysnir skjótari enn allir aðrir
kendir heuristikkar, og tann nýggja eksakta
algoritman kann loysa problem, ið eru
meira enn 10 ferðir størri enn tey, ið áður
eru vorðin loyst.
Effektiviteturin af algoritmunum kemst
fyrst og fremst av, at optimalu loysnimar
hava ein serligan stmkturellan eginleika.
Tað optimala Steinertræið kann býtast
sundur í minni sonevnd full Steinertrø
(FST), har allir terminalar eru bløð í træn-
um. Hesi FST em vanliga sera smá (fevna
sjáldan um meira enn seks terminalar), og
hava nógvar vælkendar geometriskar egin-
leikar, ið kunnu brúkast á ein effektivan
hátt við at nýta geometriskar strukturar og
algoritmur.
Ritgerðin er eitt savn av seks vísindalig-
um geinum. Fimm av hesum em um eu-
klidiska og rektlinjaða Steiner problemið,
meðan tann síðsta er um eina tabuleitingar-
algoritmu til eitt annað geometriskt pro-
blem, nevnt tann ferðandi seljararin. Inn-
gangurin í ritgerðini er ein innførsla til
Steiner problemið í planinum.