Thread View: fido.ger.informatik
2 messages
2 total messages
Started by Joachim W�rner
Wed, 23 May 2001 00:17
Domino-Problem
Author: Joachim W�rner
Date: Wed, 23 May 2001 00:17
Date: Wed, 23 May 2001 00:17
26 lines
1946 bytes
1946 bytes
Hallo Fachkollegen! Ich habe ein Problem, das ich der Einfachheit halber als Domino-Problem bezeichnen w�rde. Jedesfalls l��t es sich so sehr leicht beschreiben. Es sollen verschiedene Teile kosteng�nstig angeordnet werden. Die Anordnung kann man mit dem Domino-Spiel vergleichen, das sicher jeder kennt. Das Ziel ist es, aus verschiedenen Domino-Steinen m�glichst lange Ketten zu legen. Jedesmal, wenn zwei Dominosteine zusammengelegt werden k�nnen, ist dies ein Kosten-Vorteil. Es sollen maximal viele Kosten-Vorteile gefunden werden. Wie l�st man das mit m�glichst geringer Laufzeit? Brutforce, also einfach alles durchprobieren, w�re einfach, hat aber exponentielle Laufzeit und scheidet daher aus. Ich danke f�r jeden Tip (auch Literatur oder www). Wenn jemand eine gute L�sung wei�, dann bin ich auch gerne bereit, daf�r zu zahlen. Gru�, Joachim W�rner
Re: Domino-Problem
Author: Georg Wilm
Date: Fri, 31 Aug 2001 19:24
Date: Fri, 31 Aug 2001 19:24
57 lines
2595 bytes
2595 bytes
"Joachim Wörner" wrote: > > Hallo Fachkollegen! > > Ich habe ein Problem, das ich der Einfachheit halber als Domino-Problem > bezeichnen würde. > Jedesfalls läßt es sich so sehr leicht beschreiben. > > Es sollen verschiedene Teile kostengünstig angeordnet werden. > Die Anordnung kann man mit dem Domino-Spiel vergleichen, das sicher jeder > kennt. > > Das Ziel ist es, aus verschiedenen Domino-Steinen möglichst lange Ketten zu > legen. > Jedesmal, wenn zwei Dominosteine zusammengelegt werden können, ist dies ein > Kosten-Vorteil. > > Es sollen maximal viele Kosten-Vorteile gefunden werden. > > Wie löst man das mit möglichst geringer Laufzeit? > Brutforce, also einfach alles durchprobieren, wäre einfach, hat aber > exponentielle Laufzeit und scheidet daher aus. > > Ich danke für jeden Tip (auch Literatur oder www). > Wenn jemand eine gute Lösung weiß, dann bin ich auch gerne bereit, dafür zu > zahlen. > > Gruß, Joachim Wörner hi joachim, versteh noch nicht ganz, was du vorhast. also die anzahl an Paaren in einer liste finden dürfte doch nicht so schwer sein, oder suchst du auch n-Tupel "kostengünstiger" "Dominosteine". und was meinst du mit möglichst langen ketten. wie lautet das abbruchkriterium einer kette. steht das in irgendeiner beziehung zu den "kostengünstigen Dominosteinen"? ein paar ausführlichere erläuterungen wären nicht schlecht, deine bisherigen angeben können sehr unterschiedlich interpretiert werden. mfg georg
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads