Zwei Verkäufer - einer besucht immer den nächsten Nachbarn, der andere den am weitesten entfernten

Question

Zwei Verkäufer - einer besucht immer den nächsten Nachbarn, der andere den am weitesten entfernten

8

Betrachten Sie diese Frage in Bezug auf die Graphentheorie: Sei G ein kompletter (jeder Knoten ist mit allen anderen Knoten verbunden) nicht gerichteter Graph der Größe N x N . Zwei "Verkäufer" reisen auf diese Weise: Der erste besucht immer den nächsten nicht besuchten Eckpunkt, der zweite den weitesten, bis beide alle Eckpunkte besucht haben. Wir müssen eine Matrix von Entfernungen und die Startpunkte für die zwei Verkäufer (sie können unterschiedlich sein) so generieren, dass:

Alle Entfernungen sind eindeutig Edit: positive ganze Zahlen
Der Abstand von einem Scheitelpunkt zu sich selbst ist immer 0.
Der Unterschied zwischen der Gesamtstrecke, die von den beiden Verkäufern zurückgelegt wird, muss eine bestimmte Zahl sein, D .
Die Entfernung von A nach B ist gleich der Entfernung von B nach A

Welche effizienten Algorithmen können hilfreich sein, um mir zu helfen? Ich kann nur an Backtracking denken, aber ich sehe keine Möglichkeit, die Arbeit zu reduzieren, die durch das Programm gemacht werden muss.

algorithm optimization computer-science graph

Mystostar 22.11.2015, 17:54

quelle

1 Antwort

Tags und Links algorithm optimization computer-science graph

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Android Studio: Änderung des Inspektionsprofils für ein bestimmtes Modul im Projekt

score 1 · Answer 1

Geometrie ist hilfreich.

Die Entfernung von Punkten auf einem Kreis scheint so zu sein, als würde es funktionieren. Scheint so, als könntest du D anpassen, indem du den Kreisradius größer oder kleiner machst.

Alternativ könnte auch wirklich jede beliebige 2D-Form verwendet werden, bei der die Abstände alle unterschiedlich sind. In diesem Fall sollten Sie die Form nach oben oder unten skalieren, um die korrekte D zu erhalten.

Bearbeiten : Nun, da ich darüber nachdenke, kann die einfachste Lösung darin bestehen, einfach N zufällige 2D-Punkte auszuwählen, z. B. 32-Bit-Ganzzahlkoordinaten, um die Wahrscheinlichkeit zu verringern, dass Abstände zu nah sind. Wenn zwei Entfernungen zu nah sind, wählen Sie einfach einen anderen Punkt für einen von ihnen, bis er gültig ist.

Idealerweise müssten Sie dann nur eine Formel berechnen, um die Beziehung zwischen D und dem Skalierungsfaktor zu bestimmen, worüber ich mir nicht sicher bin. Wenn nichts anderes, könnten Sie auch nur die binäre Suche oder die Interpolationssuche oder etwas verwenden, um nach dem Skalierungsfaktor zu suchen, um die erforderliche D zu erhalten, aber das ist eine langsamere Methode.