Sökning: id:"swepub:oai:DiVA.org:ltu-24344" >
On the problem of c...
On the problem of computing zookeeper routes
-
- Jonsson, Håkan (författare)
- Luleå tekniska universitet,Datavetenskap
-
- Sundberg, Sofia (författare)
- Luleå tekniska universitet,EISLAB
-
(creator_code:org_t)
- Luleå : Luleå tekniska universitet, 2004
- Engelska 22 s.
-
Serie: Forskningsrapport / Luleå tekniska universitet, 1402-1528 ; 2004:10
- Relaterad länk:
-
https://ltu.diva-por... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- The Zookeeper's Problem is a shortest-path problem that, given a simple polygon (a zoo) containing a set of disjoint convex polygons (cages) attached to the boundary of the zoo, asks for a shortest route (closed path) in the zoo that intersects the boundaries of all cages without entering their interiors. The literature contains several algorithms for variants of this problem some of which compute exact and some approximate solutions. However, no implementations have been reported. Moreover, concerns have also been raised about the numerical properties of the algorithms that compute exact solutions. In this paper we present a study of two algorithms for the Zookeeper's Problem. One of them compute exact solutions and the other provably good approximations. We give observations about the algorithms and the solutions they compute. We also present an experimental study based on an implementation of the algorithms in Java.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Annan elektroteknik och elektronik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Other Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)
Nyckelord
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
- Industriell elektronik
- Industrial Electronics
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)