Article View: maus.sci.informatik
Article #5Re: S: exotischen Algorithmus...
From: Lars Eggert
Date: Mon, 26 Sep 1994 09:40
Date: Mon, 26 Sep 1994 09:40
30 lines
2969 bytes
2969 bytes
In article <fulscher.15.000302F3@dial.eunet.ch>, fulscher@dial.eunet.ch (Jan Fuelscher) writes:
> In article <361a67$547@news.rz.uni-duesseldorf.de> oschaed@caticsuf.csufresno.edu (Oliver Schaedlich) writes:
> > Ich bin auf der Suche nach einem sehr exotischen Algorithmus:
> >
> > Er soll eine Menge Polygone (moeglichst auch nich konvexe) so auf
> >einer Flaeche verteilen, dasz sie sich nicht ueberschneiden, jedoch
> >moeglichst eng zusammenliegen, so dasz moeglichtst wenig Verschnitt
> >enststeht bzw. moechlichst viel Platz bleibt.
> >
>
> Das ist, soweit ich weiss, theoretisch nicht loesbar. Es gibt Ansaetze,
> das Problem mittels Expertensystemen anzugehen; doch das funktioniert
> auch nur fuer sehr spezielle Untermengen dieser Angelegenheit.
> Das Problem gleicht dem, den besten Zug einer Menge von moeglichen
> Zuegen in einem Spiel auszuwaehlen => Suchverfahren.
>
Loesbar ist das schon, aber nicht mit polynomiellen Zeitaufwand. Ist denn
nach einer optimalen Loesung gefragt, oder ist ein gewisser Fehler zu
tolerieren? Wenn ja, koenntest Du eine Heuristik entwickeln oder mit
probabilistischen Verfahren arbeiten. Erzaehl doch mal was genaueres ueber
die Aufgabenstellung.
--
Lars Eggert eggert@{isa|rbg}.informatik.th-darmstadt.de
Four... three... two... one... Bing! We have meatloaf!
-- Homer watches dinner cook in the microwave,
"One Fish, Two Fish, Blowfish, Blue Fish"
Technical Details
Message-ID:
<3664v3$c9j@rs18.hrz.th-darmstadt.de>Path:
arc1-ca.pugleaf.net!bga.com!news.sprintlink.net!howland.reston.ans.net!swiss.ans.net!news.dfn.de!zeus.rbi.informatik.uni-frankfurt.de!terra.wiwi.uni-frankfurt.de!news.th-darmstadt.de!isa.informatik.th-darmstadt.de!eggertReferences:
<361a67$547@news.rz.uni-duesseldorf.de> <fulscher.15.000302F3@dial.eunet.ch>Show Full Headers
Complete Article Headers
X-Google-Language: GERMAN,ASCII-7-bit X-Google-Thread: 102c5b,a8fec9e4b29b3ba8 X-Google-Attributes: gid102c5b,public X-Google-Thread: 10693a,a8fec9e4b29b3ba8 X-Google-Attributes: gid10693a,public X-Google-Thread: 1123d7,a8fec9e4b29b3ba8 X-Google-Attributes: gid1123d7,public X-Google-Thread: 144b12,a8fec9e4b29b3ba8 X-Google-Attributes: gid144b12,public X-Google-Thread: 10c73c,a8fec9e4b29b3ba8 X-Google-Attributes: gid10c73c,public X-Google-Thread: 10abd9,a8fec9e4b29b3ba8 X-Google-Attributes: gid10abd9,public X-Google-Thread: f4da7,a8fec9e4b29b3ba8 X-Google-Attributes: gidf4da7,public X-Google-Thread: 10f372,a8fec9e4b29b3ba8 X-Google-Attributes: gid10f372,public X-Google-ArrivalTime: 1994-09-26 02:45:53 PST Path: arc1-ca.pugleaf.net!bga.com!news.sprintlink.net!howland.reston.ans.net!swiss.ans.net!news.dfn.de!zeus.rbi.informatik.uni-frankfurt.de!terra.wiwi.uni-frankfurt.de!news.th-darmstadt.de!isa.informatik.th-darmstadt.de!eggert From: eggert@isa.informatik.th-darmstadt.de (Lars Eggert) Newsgroups: maus.sci.informatik,maus.lang.c,fido.ger.informatik,fido.ger.c_plusplus,de.comp.lang.misc,zer.z-netz.sprachen.algorithmen,de.comp.lang.c,de.comp.lang.c++ Subject: Re: S: exotischen Algorithmus... Date: 26 Sep 1994 09:40:51 GMT Organization: Technische Hochschule Darmstadt Lines: 31 Distribution: world Message-ID: <3664v3$c9j@rs18.hrz.th-darmstadt.de> References: <361a67$547@news.rz.uni-duesseldorf.de> <fulscher.15.000302F3@dial.eunet.ch> NNTP-Posting-Host: sun43.isa.informatik.th-darmstadt.de