[Talk-de] LKW-Routing (TV-Bericht)

[Philipp Matthias Hahn]

Moin!

On Sun, Dec 07, 2008 at 02:57:46PM +0100, Guenther Meyer wrote:
> > Was ist Dein Problem damit, außer dass es Dir es um das Prinzip geht,
> > dass wenn es hinterher im Router schief läuft, Du sagen kannst "dann war
> > es aber unvollständig gemapt".
> >
> ich hab kein problem.
> ich versuche nur, die dinge moeglichst EINFACH und PLATZSPAREND abzubilden, 
> und trotzdem ausreichend.

Dann mach es doch bitte dem Router einfacher und schreib die
Einschränkungen an die Straße.

Den Router interessieren hauptsächlich nur die Kanten, die Knoten sind
nur für die Berechnung der Entfernung und später beim Anzeigen
interessant. Für die Gewichtung der Kante mit der Entfernung muß man
sich zwar auch alle Knoten angucken und die Entfernungen daziwschen
aufsummieren, aber für sonstige Beschränkungen kommst du algorithmisch
in teufels Küche:
    +===========+
    |           |
A===B           C===D
|   |           |   |
|   +-----------+   |
|                   |
+-------------------+

Wenn du bei den Knoten A,B,C und D die gleiche Beschränkung einträgst,
für welche Wege gelten die dann:
	A=B?
	B=C?
	B-C?
	C=D?
	A-D?
Und bevor jemand auf die Idee kommt, kurze Wegstücke zwischen solchen
Kreuzungen und dem Beginn/Ende der Beschränkung einzubauen, soltte er
überlegen, was passiert, wenn man eine neue Straße einträgt, die einen
beschränkten Bereich mit dem Rest der Welt verbindet: (Stichwort
Flood-Fill bei Malprogrammen)

BYtE
Philipp
-- 
  / /  (_)__  __ ____  __ Philipp Hahn
 / /__/ / _ \/ // /\ \/ /
/____/_/_//_/\_,_/ /_/\_\ pmhahn at titan.lahn.de