Wenn Sie die Conway's Game of Life überprüfen, werden Sie feststellen, dass das Race-Problem sehr ähnlich ist. Hier
ist die Analogie:
- Der Anfangszustand (der Samen des Systems):
- Spiel des Lebens: initial Muster auf dem Raster. Jede Zelle mit den folgenden Parametern:
- x und y-Koordinate
- ob die Zelle lebt oder tot ist
- Rennen Problem: n Fahrzeuge jeweils eine mit vorbestimmten Parametern und die Länge der Strecke l. Jeder Wagen hat die folgenden Parameter:
- Endgeschwindigkeit
- Beschleunigungs
- Faktor Handhabung
- Position auf der Strecke
- aktuelle Geschwindigkeit
- Die Regeln an diskreten Momente aufgebracht werden, die heißen Ticks.
- Spiel des Lebens: Die Regeln werden gleichzeitig auf jede Zelle der vorherigen Generation angewendet, die eine nächste Generation produziert. Jede Generation ist eine reine Funktion des vorhergehenden.
- Race Problem: die Regeln werden gleichzeitig auf jedes Auto aus dem vorherigen Zustand angewendet, der einen nächsten Zustand produziert. Dies geschieht alle 2 Sekunden. Wie bei Game of Life ist jeder Schritt eine reine Funktion des vorhergehenden, was bedeutet, dass es nur von den Parametern der Autos aus dem vorherigen Zustand abhängt.
Was anders ist, ist, dass das Spiel des Lebens endet nie während des Rennens Problems beendet werden soll, wenn die aktuelle Position jedes Auto größer oder gleich die Spurlänge l ist (Obwohl die letzte Aussage ist fraglich: due zum Handling-Faktor ist es möglich, dass unter manchen Bedingungen einige Autos nie die Ziellinie erreichen werden).
Der entscheidende Punkt ist, dass Berechnungen an diskreten Momente getan werden, die Ihre Frage beantwortet:
Aber wie kann ich auf das, was beispielsweise herausfinden, ich sollte die Berechnungen machen?
Sie können die Idee aus dem Abschnitt Algorithms nehmen, um dieses Problem zu lösen. Sie müssen 2 Autos Arrays haben: eine repräsentiert den aktuellen Zustand und die andere den nächsten Schritt. Bei jeder Iteration berechnen Sie die aktuelle Position und die Geschwindigkeit jedes Autos nach den Regeln aus der Zuweisung und prüfen, ob die Schleife beendet werden soll. Vor der nächsten Iteration tauschen Sie die Array-Rollen aus, so dass das Nachfolger-Array in der letzten Iteration in der nächsten Iteration zum aktuellen Array wird.
Der hohe Pseudo-Code kann wie folgt aussehen:
n = ..; // initial number of cars
l = ..; // track length
Car[] currentState = initializeState(n, l);
Car[] nextState = clone(currentState);
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
calculateNextState(currentState, nextState, iteration);
swap(currentState, nextState);
if (shouldTerminate(currentState, l) {
break;
}
}
printResultOrClaimNotTerminated(currentState);
Die Regeln angewandt werden in der calculateNextState (..) Funktion. In der am meisten naiven Implementierung überprüfen Sie jedes Paar von Autos, die Ihnen
O (C(n, 2)) = O (n * (n - 1)/2) = O (n^2)
Komplexität für jede Iteration gibt. Allerdings können Sie hier an mögliche Optimierungen denken. Zum Beispiel können Sie die Autos nach der aktuellen Position zuerst sortieren (O (n * log(n))) und dann das sortierte Array durchqueren und nur benachbarte Autos überprüfen (O (2 * n)). Sie können dies tun, da, wenn die 10-Meter-Bedingung für benachbarte Autos nicht genügt, sie für nicht benachbarte Autos nicht genügen wird. Dies gibt Ihnen die resultierende Komplexität von:
was viel besser ist. Das sortierte Array von Autos gibt Ihnen natürlich das Auto mit der letzten Position, auf die Sie die Nitro Boost-Regel anwenden müssen. Wahrscheinlich kann es andere Optimierungen geben. Dies beantwortet Ihre Frage:
Für jede Instanz sollte ich alle C (n, 2) Kombinationen von jedem Paar Treiber überprüfen und das Ergebnis berechnen?
ich bin mir nicht sicher, aber wenn ich Ihre Frage habe, ich denke, Sie müssen in "Client-Server" -Modell implementiert werden.Sie haben einen Server, der verantwortlich ist für das Halten der match.clients sind Autos (Teams). Bei jedem Schritt teilen die Clients dem Server ihre Informationen mit, und der Server speichert sie. Sie können auf alle anderen Informationen zugreifen. So erhalten sie bei jedem Schritt eine vollständige Liste der Autos und ihrer Informationen. So können sie herausfinden, ob es Autos gibt innerhalb von 10 Metern mit der Zeit von O (n). gerade wie reale Formel 1, die alle Fahrerklassifizierungen und den Platz zeigt, den sie auf dem Schirm sind! –