Suchen Sie anhand einer Liste von Punkten den kürzesten Pfad, der alle Punkte aufruft und zum Ausgangspunkt zurückkehrt.

Das Problem des Handlungsreisenden ist auf dem Gebiet der Informatik bekannt, da es viele Möglichkeiten gibt, es zu berechnen / zu approximieren. Es wurde für sehr große Punktegruppen gelöst, aber einige der größten benötigen viele CPU-Jahre, um fertig zu werden.

Lass dich nicht von der Kartoffel verbrennen.

Hot Potato ist ein Spiel, bei dem 2+ Spieler eine "Kartoffel" im Kreis herumreichen, während Musik spielt. Das Ziel ist, es schnell an den nächsten Spieler weiterzugeben. Wenn Sie die Kartoffel halten, während die Musik aufhört, sind Sie draußen.

Gegenstand des Hot Potato Salesman ist:

Bei einer Menge von 100 eindeutigen Punkten geben Sie diese Punkte in einer besseren Reihenfolge zurück ( kürzere Gesamtentfernung, wie weiter unten definiert ). Dadurch wird das Problem an den nächsten Spieler "weitergegeben". Sie müssen es verbessern und an die nächste weitergeben usw. Wenn ein Spieler es nicht verbessern kann, sind sie aus und spielen weiter, bis ein Spieler übrig ist.

Damit dies kein "Brute-Force-Me-A-Path" -Wettbewerb ist, gelten folgende Bestimmungen:

• Sie können nicht länger als eine Minute brauchen , um die Kartoffel zu überholen. Wenn Sie bis zum Ablauf einer Minute keine kürzere Lösung gefunden und verabschiedet haben, sind Sie unterwegs.

• Sie können die Position von mehr als 25 Punkten nicht ändern . Um genau zu sein, >= 75müssen sich die Punkte an derselben Position befinden, an der Sie sie erhalten haben. Es spielt keine Rolle, welche Sie ändern möchten, sondern nur den Betrag, den Sie ändern.

Wenn nur noch ein Spieler übrig ist, ist er der Gewinner dieses Spiels und erhält einen Punkt. Ein Turnier besteht aus 5*nSpielen, wobei ndie Anzahl der Spieler ist. Bei jedem Spiel wird der Startspieler gedreht und die verbleibende Spielerreihenfolge wird gemischt . Der Spieler mit den meisten Punkten am Ende ist der Gewinner des Turniers. Wenn das Turnier mit einem Unentschieden um den ersten Platz endet, wird ein neues Turnier nur mit diesen Teilnehmern gespielt. Dies wird so lange fortgesetzt, bis es kein Unentschieden mehr gibt.

Der Startspieler für jedes Spiel erhält eine Reihe von pseudozufällig ausgewählten Punkten in keiner bestimmten Reihenfolge.

Punkte werden als ein Paar ganzzahliger x,yKoordinaten in einem kartesischen Gitter definiert. Die Entfernung wird gemessen mit Manhattan - Distanz , |x1-x2| + |y1-y2|. Alle Koordinaten liegen im [0..199]Bereich.

Eingang

Die Eingabe erfolgt mit einem einzelnen String-Argument. Es besteht aus 201 durch Kommas getrennten ganzen Zahlen, die die Anzahl der aktuellen Spieler ( m) und 100 Punkte darstellen:

m,x0,y0,x1,y1,x2,y2,...,x99,y99

Die Reihenfolge dieser Punkte ist der aktuelle Pfad. Die Gesamtentfernung ergibt sich durch Addition der Entfernung von jedem Punkt zum nächsten ( dist(0,1) + dist(1,2) + ... + dist(99,0)). Vergessen Sie nicht, zurückzukehren, um die Gesamtstrecke zu berechnen!

Beachten Sie, dass mist nicht die Anzahl der Spieler, die das Spiel gestartet wird , ist es die Zahl , die noch in sind.

Ausgabe

Die Ausgabe erfolgt wie die Eingabe minus m; Eine einzelne Zeichenfolge mit durch Kommas getrennten Ganzzahlen, die die Punkte in ihrer neuen Reihenfolge darstellen.

x0,y0,x1,y1,x2,y2,...,x99,y99

Das Steuerungsprogramm wartet nur eine Minute auf die Ausgabe. Beim Empfang der Ausgabe wird Folgendes überprüft:

• der ausgang ist wohlgeformt
• Die Ausgabe besteht aus nur und all den 100 Punkten in dem Eingang
• >=75 Die Punkte befinden sich an ihren ursprünglichen Positionen
• Die Pfadlänge ist kürzer als der vorherige Pfad

Wenn eine dieser Prüfungen fehlschlägt (oder keine Ausgabe erfolgt), sind Sie aus und das Spiel wird zum nächsten Spieler fortgesetzt.

Steuerungsprogramm

Das Steuerungsprogramm finden Sie unter diesem Link . Das Steuerungsprogramm selbst ist deterministisch und wird mit einem Dummy-Startwert von gebucht 1. Die Samen, die während der Wertung verwendet werden, sind unterschiedlich. Versuchen Sie also nicht, die Reihenfolge der Züge und die Punktelisten zu analysieren, die sie ausspucken.

Die Hauptklasse ist Tourney. Wenn Sie dies ausführen, wird ein vollständiges Turnier mit Teilnehmern durchgeführt, die als Argumente angegeben wurden. Es spuckt den Sieger jedes Spiels und eine Bilanz am Ende aus. Ein Beispielturnier mit zwei SwapBots sieht folgendermaßen aus:

Starting tournament with seed 1

(0) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 3
(0) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 4
(1) SwapBot wins a game! Current score: 5
(1) SwapBot wins a game! Current score: 6
(1) SwapBot wins a game! Current score: 7
(1) SwapBot wins a game! Current score: 8

Final Results:

Wins        Contestant
2       (0) SwapBot
8       (1) SwapBot

Wenn Sie jeweils nur ein Spiel testen möchten, können Sie Gamestattdessen die Klasse ausführen . Dies wird ein Spiel mit Spielern in der angegebenen Reihenfolge als Argument ausführen. Standardmäßig wird auch ein Play-by-Play mit dem aktuellen Player und der Pfadlänge gedruckt.

Ebenfalls enthalten sind ein paar Testspieler: SwapBot, BlockPermuter, und TwoSwapBot. Die ersten beiden werden nicht in die Wertungsläufe einbezogen. Sie können sie also während des Tests verwenden und missbrauchen. TwoSwapBot wird in die Bewertung mit einbezogen, und er ist kein Trottel, also bring dein A-Game mit.

Verschiedenes

• Sie können keine Statusinformationen speichern, und jede Runde ist eine separate Ausführung Ihres Programms. Die einzigen Informationen, die Sie in jeder Runde erhalten, sind die Punkte.

• Sie können keine externen Ressourcen verwenden. Dies beinhaltet Netzwerkanrufe und Dateizugriff.

• Sie können keine Bibliotheksfunktionen verwenden, die zur Lösung / Unterstützung des TSP-Problems oder seiner Varianten entwickelt wurden.

• Sie können andere Spieler in keiner Weise manipulieren oder stören.

• Sie können das Steuerprogramm oder eingeschlossene Klassen oder Dateien in keiner Weise manipulieren oder stören.

• Multithreading ist zulässig.

• Eine Einreichung pro Benutzer. Wenn Sie mehr als einen Beitrag einreichen, gebe ich nur den ersten Beitrag ein. Wenn Sie Ihren Beitrag ändern möchten, bearbeiten / löschen Sie das Original.

• Das Turnier läuft unter Ubuntu 13.04 auf einem Computer mit einer i7-3770K-CPU und 16 GB RAM. Es wird nicht in einer VM ausgeführt. Alles, was ich als böswillig empfinde, disqualifiziert sofort den aktuellen und jeden zukünftigen Beitrag, den Sie einreichen.

• Alle Eingaben müssen über die Kommandozeile mit kostenloser ( wie in Bier ) Software ausgeführt werden können. Wenn ich Probleme beim Kompilieren / Ausführen Ihres Eintrags habe, bitte ich um Hilfe in den Kommentaren. Wenn Sie nicht antworten oder ich es letztendlich nicht zum Laufen bringen kann, wird es disqualifiziert.

Ergebnisse (22 Mai 2014)

Neue Ergebnisse liegen vor! UntangleBot hat die Konkurrenz ziemlich gut geschlagen. TwoSwapBot schaffte sieben Siege und SANNbot erzielte ebenfalls einen Sieg. Hier ist ein Anzeiger und ein Link zur Rohausgabe :

Wins        Contestant
22      (2) ./UntangleBot
7       (0) TwoSwapBot
1       (5) SANNbot.R
0       (1) BozoBot
0       (3) Threader
0       (4) DivideAndConquer

Wie steht es nun , UntangleBot hat das Häkchen gewonnen. Lassen Sie sich davon jedoch nicht entmutigen, da ich das Turnier mit mehr Teilnehmern leiten und die akzeptierte Antwort entsprechend ändern werde.

UntangleBot (ehemals NiceBot)

Ein C ++ 11-Bot, der zwei Strategien verwendet.
Zuerst wird versucht, den Pfad nach Möglichkeit zu "entwirren", indem Schnittpunkte zwischen Pfaden erkannt werden, die näher als 25 Punkte sind (da das Entwirren das Ändern aller dazwischen liegenden Punkte impliziert).
Wenn die erste Strategie fehlschlägt, werden die Punkte nach dem Zufallsprinzip ausgetauscht, um bessere Entfernungen zu finden, bis ein besserer Pfad gefunden wurde.

Dieser Bot schlägt durchweg TwoSwapBot mit einem ungefähren Verhältnis von fünf Siegen für einen Verlust in meinen Testturnieren.

// g++ -std=c++11 -O3 -o UntangleBot UntangleBot.cpp
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <sstream>

const int NPOINTS = 100;

struct Point {
    int x, y;

    Point():x(0),y(0) {}    
    Point(int x, int y):x(x),y(y) {}

    int distance_to(const Point & pt) const {
        return std::abs(x - pt.x) + std::abs(y - pt.y);
    }
};

std::ostream & operator<<(std::ostream & out, const Point & point) {
    return out << point.x << ',' << point.y;
}

int total_distance(const Point points[NPOINTS]) {
    int distance = 0;
    for (int i = 0; i < NPOINTS; ++i) {
        distance += points[i].distance_to(points[(i+1)%NPOINTS]);
    }
    return distance;
}

bool intersects(const Point & p1, const Point & p2, const Point & p3, const Point & p4) {
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p2.x - p1.x;
    s1_y = p2.y - p1.y;
    s2_x = p4.x - p3.x;
    s2_y = p4.y - p3.y;

    double s, t;
    s = (-s1_y * (p1.x - p3.x) + s1_x * (p1.y - p3.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p1.y - p3.y) - s2_y * (p1.x - p3.x)) / (-s2_x * s1_y + s1_x * s2_y);

    return s >= 0 && s <= 1 && t >= 0 && t <= 1;
}

int main(int argc, char ** argv) {
    Point points[NPOINTS];

    using Clock = std::chrono::system_clock;
    const Clock::time_point start_time = Clock::now();

    // initialize points
    if (argc < 2) {
        std::cerr << "Point list is missing" << std::endl;
        return 1;
    }
    std::stringstream in(argv[1]);
    int players;
    char v;
    in >> players >> v;
    for (int i = 0; i < NPOINTS; ++i) {
        in >> points[i].x >> v >> points[i].y >> v;
    }

    int original_distance = total_distance(points);

    // detect intersection between any 4 points
    for (int i = 0; i < NPOINTS; ++i) {
        for (int j = i+1; j < NPOINTS; ++j) {
            Point & p1 = points[i];
            Point & p2 = points[(i+1)%NPOINTS];
            Point & p3 = points[j];
            Point & p4 = points[(j+1)%NPOINTS];

            // points must all be distinct
            if (p1.distance_to(p3) == 0 || p1.distance_to(p4) == 0 || p2.distance_to(p3) == 0 || p2.distance_to(p4) == 0) {
                continue;
            }

            // do they intersect ?
            if (!intersects(p1, p2, p3, p4)) {
                continue;
            }

            // can modify less than 25 points ?
            if (std::abs(j-i) > 25) {
                continue;
            }

            // swap points
            for (int m = 0; m < std::abs(j-i)/2; ++m) {
                if (i+1+m != j-m) {
                    std::swap(points[i+1+m], points[j-m]);
                    //std::cerr << "untangle " << i+1+m << " <=> " << j-m << '\n';
                }
            }

            int new_distance = total_distance(points);
            if (new_distance < original_distance) {
                std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                std::cout << points[NPOINTS-1];
                return 0;
            }
            else {
                // swap points back
                for (int m = 0; m < std::abs(j-i)/2; m++) {
                    if (i+1+m != j-m) {
                        std::swap(points[i+1+m], points[j-m]);
                    }
                }
            }
        }
    }

    // more traditional approach if the first fails
    std::mt19937 rng(std::chrono::duration_cast<std::chrono::seconds>(start_time.time_since_epoch()).count());
    std::uniform_int_distribution<> distr(0, NPOINTS-1);
    while (true) {
        // try all possible swaps from a random permutation
        int p1 = distr(rng);
        int p2 = distr(rng);
        std::swap(points[p1], points[p2]);

        for (int i = 0; i < NPOINTS; ++i) {
            for (int j = i+1; j < NPOINTS; ++j) {
                std::swap(points[i], points[j]);
                if (total_distance(points) < original_distance) {
                    std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                    std::cout << points[NPOINTS-1];
                    return 0;
                }
                else {
                    std::swap(points[i], points[j]);
                }
            }
        }

        // they didn't yield a shorter path, swap the points back and try again
        std::swap(points[p1], points[p2]);
    }
    return 0;
}

SANNbot

(ein simulierter Annealing Bot in R )

Sollte mit angerufen werden Rscript SANNbot.R.

input <- strsplit(commandArgs(TRUE),split=",")[[1]]
n <- as.integer(input[1])                            # Number of players
init_s <- s <- matrix(as.integer(input[-1]),ncol=2,byrow=TRUE) # Sequence of points
totdist <- function(s){                              # Distance function
    d <- 0
    for(i in 1:99){d <- d + (abs(s[i,1]-s[i+1,1])+abs(s[i,2]-s[i+1,2]))}
    d
    }
gr <- function(s){                                   # Permutation function
    changepoints <- sample(1:100,size=2, replace=FALSE)
    tmp <- s[changepoints[1],]
    s[changepoints[1],] <- s[changepoints[2],]
    s[changepoints[2],] <- tmp
    s
    }
d <- init_d <- totdist(s)                            # Initial distance
k <- 1                                               # Number of iterations
v <- 0
t <- n*(init_d/12000)                                 # Temperature
repeat{
    si <- gr(s)                                      # New sequence
    di <- totdist(si)                                # New distance
    dd <- di - d                                     # Difference of distances
    if(dd <= 0 | runif(1) < exp(-dd/t)){             # Allow small uphill changes
        d <- di
        s <- si
        v <- v+2
        }
    k <- k+1
    if(k > 10000){break}
    if(d > init_d & v>20){s <- init_s; d <- init_d; v <- 0}
    if(v>23){break}
}
cat(paste(apply(s,1,paste,collapse=","),collapse=","))

Die Idee ist relativ einfach: Jede Runde ist ein "Abkühlungsschritt" eines simulierten Temperns mit der Anzahl der Spieler, die noch im Spiel sind, als "Temperatur" (geändert um die aktuelle Distanz über 12000, dh ungefähr die anfängliche Distanz). Der einzige Unterschied zu einem richtigen simulierten Tempern ist, dass ich überprüft habe, dass ich nicht mehr als 25 Elemente permutiere. Wenn ich 20 Züge verbraucht habe, aber die resultierende Sequenz mehr wert ist als die anfängliche, dann fängt sie wieder von vorne an.

BozoBot

Verwendet die komplexe Logik hinter Bozosort , um einen besseren Weg zu finden. Es sieht aus wie das.

• Tausche zufällige Punkte
• Wenn wir uns verbessern würden
  • Antwort zurücksenden
• Andernfalls
  • Versuch es noch einmal

BozoBot wurde jetzt mit Multithreading verbessert ! Vier Schergen jonglieren nun ziellos mit Punkten, bis sie auf eine Verbesserung stoßen. Der erste, der eine Lösung findet, bekommt einen Cookie!

Anscheinend scheitere ich beim Multithreading.

import java.util.Random;
public class BozoBot {
    public static String[] input;
    public static void main(String[] args) {
        input = args;
        for(int i = 0; i < 4; i++) new Minion().run();
    }
}

class Minion implements Runnable {
    public static boolean completed = false;
    public static synchronized void output(int[] x, int[] y) {
        if(!completed) {
            completed = true;
            String result = x[0]+","+y[0];
            for (int i = 1; i < 100; i++)
                result+=","+x[i]+","+y[i];
            System.out.print(result);
            // receiveCookie(); // Commented out to save money
        }
    }
    public void run() {
        String[] args = BozoBot.input[0].split(",");
        int[] x = new int[100];
        int[] y = new int[100];
        for (int i = 1; i < 201; i+=2) {
            x[(i-1)/2] = Integer.parseInt(args[i]);
            y[i/2] = Integer.parseInt(args[i+1]);
        }
        int startDistance = 0;
        for (int i = 1; i < 100; i++)
            startDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
        int r1, r2, r3, r4, tX, tY, newDistance;
        Random gen = new java.util.Random();
        while (true) {
            r1 = gen.nextInt(100);
            r2 = gen.nextInt(100);
            r3 = gen.nextInt(100);
            r4 = gen.nextInt(100);
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
            newDistance = 0;
            for (int i=1; i < 100; i++)
                newDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
            if(newDistance < startDistance)
                break;
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
        }
        output(x,y);
    }
}

TwoSwapBot

Bei einem Upgrade auf SwapBotsucht dieser Typ nach jedem Swap-Paar. Zunächst prüft er, ob ein einzelner Swap den Pfad verkürzt. Wenn dies der Fall ist, wird es sofort zurückgegeben. Wenn nicht, prüft er jeden, ob ein anderer Swap ihn verkürzt. Wenn nicht, stirbt er einfach.

Während der Pfad noch halb zufällig ist, kehrt er normalerweise nach etwa 100 ms zurück. Wenn er jeden 2-Swap (ungefähr 25 Millionen) überprüfen muss, dauert es ungefähr 20 Sekunden.

Zum Zeitpunkt der Einreichung schlug dies alle anderen Teilnehmer in Testrunden.

public class TwoSwapBot {

    static int numPoints = 100;

    String run(String input){
        String[] tokens = input.split(",");
        if(tokens.length < numPoints*2)
            return "bad input? nope. no way. bye.";

        Point[] points = new Point[numPoints];  
        for(int i=0;i<numPoints;i++)
            points[i] = new Point(Integer.valueOf(tokens[i*2+1]), Integer.valueOf(tokens[i*2+2]));
        int startDist = totalDistance(points);

        Point[][] swapped = new Point[(numPoints*(numPoints+1))/2][];       
        int idx = 0;
        for(int i=0;i<numPoints;i++){
            for(int j=i+1;j<numPoints;j++){
                Point[] test = copyPoints(points);
                swapPoints(test,i,j);
                int testDist = totalDistance(test);
                if( testDist < startDist)
                    return getPathString(test);
                else
                    swapped[idx++] = test;
            }
        }

        for(int i=0;i<idx;i++){
            for(int k=0;k<numPoints;k++){
                for(int l=k+1;l<numPoints;l++){
                    swapPoints(swapped[i],k,l);
                    if(totalDistance(swapped[i]) < startDist)
                        return getPathString(swapped[i]);
                    swapPoints(swapped[i],k,l);
                }
            }
        }
        return "well damn";
    }

    void swapPoints(Point[] in, int a, int b){
        Point tmp = in[a];
        in[a] = in[b];
        in[b] = tmp;
    }

    String getPathString(Point[] in){
        String path = "";
        for(int i=0;i<numPoints;i++)
            path += in[i].x + "," + in[i].y + ",";
        return path.substring(0,path.length()-1);
    }

    Point[] copyPoints(Point[] in){
        Point[] out = new Point[in.length];
        for(int i=0;i<out.length;i++)
            out[i] = new Point(in[i].x, in[i].y);
        return out;
    }

    static int totalDistance(Point[] in){
        int dist = 0;
        for(int i=0;i<numPoints-1;i++)
            dist += in[i].distance(in[i+1]);
        return dist + in[numPoints-1].distance(in[0]);
    }

    public static void main(String[] args) {
        if(args.length < 1)
            return;
        System.out.print(new TwoSwapBot().run(args[0]));
    }

    class Point{
        final int x; final int y;
        Point(int x, int y){this.x = x; this.y = y;}
        int distance(Point other){return Math.abs(x-other.x) + Math.abs(y-other.y);}
    }
}

Einfädler

Dieser Bot

1. Teilt die 100 Punkte in 4 10 Teile von 25 10 Punkten auf
2. Startet einen Thread für jedes Stück
3. Mische das Array im Thread nach dem Zufallsprinzip, wobei Start- und Endpunkt unverändert bleiben
4. Wenn der Abstand zum neuen Array kürzer ist, behalten Sie ihn bei
5. Nach 59s sammelt der Hauptthread die Ergebnisse und druckt sie aus

Die Idee ist, die beste Verbesserung des Pfades zu finden, damit die anderen Bots mit ihrer Logik scheitern.

import java.util.Arrays;
import java.util.Collections;

public class Threader {
    public static final int THREAD_COUNT = 10;
    public static final int DOT_COUNT = 100;
    private final Dot[] startDots = new Dot[THREAD_COUNT];
    private final Dot[] endDots = new Dot[THREAD_COUNT];
    private final Dot[][] middleDots = new Dot[THREAD_COUNT][DOT_COUNT/THREAD_COUNT-2];
    private final Worker worker[] = new Worker[THREAD_COUNT];
    private final static long TIME = 59000; 

    public static void main(String[] args) {
        Threader threader = new Threader();
        //remove unnecessary player count to make calculation easier
        threader.letWorkersWork(args[0].replaceFirst("^[0-9]{1,3},", "").split(","));
    }

    public void letWorkersWork(String[] args) {
        readArgs(args);
        startWorkers();
        waitForWorkers();
        printOutput();
    }

    private void readArgs(String[] args) {
        final int magigNumber = DOT_COUNT*2/THREAD_COUNT;
        for (int i = 0; i < args.length; i += 2) {
            Dot dot = new Dot(Integer.parseInt(args[i]), Integer.parseInt(args[i + 1]));
            if (i % magigNumber == 0) {
                startDots[i / magigNumber] = dot;
            } else if (i % magigNumber == magigNumber - 2) {
                endDots[i / magigNumber] = dot;
            } else {
                middleDots[i / magigNumber][(i % magigNumber) / 2 - 1] = dot;
            }
        }
    }

    private void startWorkers() {
        for (int i = 0; i < THREAD_COUNT; i++) {
            worker[i] = new Worker(startDots[i], endDots[i], middleDots[i]);
            Thread thread = new Thread(worker[i]);
            thread.setDaemon(true);
            thread.start();
        }
    }

    private void waitForWorkers() {
        try {
            Thread.sleep(TIME);
        } catch (InterruptedException e) {
        }
    }

    private void printOutput() {
        //get results
        Worker.stopWriting = true;
        int workerOfTheYear = 0;
        int bestDiff = 0;
        for (int i = 0; i < THREAD_COUNT; i++) {
            if (worker[i].diff() > bestDiff) {
                bestDiff = worker[i].diff();
                workerOfTheYear = i;
            }
        }
        //build output
        StringBuilder result = new StringBuilder(1000);
        for (int i = 0; i < THREAD_COUNT; i++) {
            result.append(startDots[i]);
            Dot middle[] = middleDots[i];
            if (i == workerOfTheYear) {
                middle = worker[i].bestMiddle;
            }
            for (int j = 0; j < middle.length; j++) {
                result.append(middle[j]);
            }
            result.append(endDots[i]);
        }
        result.replace(0, 1, ""); //replace first comma
        System.out.print(result);
    }

}

class Worker implements Runnable {

    public Dot start;
    public Dot end;
    private Dot[] middle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public Dot[] bestMiddle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public static boolean stopWriting = false;
    private int bestDist = Integer.MAX_VALUE;
    private final int startDist;

    public Worker(Dot start, Dot end, Dot[] middle) {
        this.start = start;
        this.end = end;
        System.arraycopy(middle, 0, this.middle, 0, middle.length);
        System.arraycopy(middle, 0, this.bestMiddle, 0, middle.length);
        startDist = Dot.totalDist(start, middle, end);
    }

    @Override
    public void run() {
        while (true) {
            shuffleArray(middle);
            int newDist = Dot.totalDist(start, middle, end);
            if (!stopWriting && newDist < bestDist) {
                System.arraycopy(middle, 0, bestMiddle, 0, middle.length);
                bestDist = newDist;
            }
        }
    }

    public int diff() {
        return startDist - bestDist;
    }

    private void shuffleArray(Dot[] ar) {
        Collections.shuffle(Arrays.asList(ar));
    }

}

class Dot {

    public final int x;
    public final int y;

    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int distTo(Dot other) {
        return Math.abs(x - other.x) + Math.abs(y - other.y);
    }

    public static int totalDist(Dot start, Dot[] dots, Dot end) {
        int distance = end.distTo(start);
        distance += start.distTo(dots[0]);
        distance += end.distTo(dots[dots.length - 1]);
        for (int i = 1; i < dots.length; i++) {
            distance += dots[i].distTo(dots[i - 1]);
        }
        return distance;
    }

    @Override
    public String toString() {
        return "," + x + "," + y;
    }
}

Teilen und Erobern + Gieriger Bot

HINWEIS: Ich habe mir Ihren Code angesehen Game, der Folgendes in Game.parsePath enthält:

for(int i=0;i<numPoints;i++){
        test[i] = new Point(Integer.valueOf(tokens[i*2]), Integer.valueOf(tokens[i*2+1]));
        if(test[i].equals(currentPath[i]))
            same++;

Es gibt jedoch keinen catch(NumberFormatException)Block, sodass Ihr Programm wahrscheinlich abstürzt, wenn ein Player-Programm eine Zeichenfolge ausgibt (wie am Ende der mainMethode meines Programms gezeigt ). Ich rate Ihnen, dies zu beheben, da Programme Ausnahmen, Stack-Traces oder ähnliches ausgeben können. Kommentieren Sie andernfalls diese Zeile in meinem Programm aus, bevor Sie es ausführen.

Zurück zum Thema

Diese Implementierung (in Java) teilt die Liste der Punkte in Stücke von 25 auf, die zufällig auf der Liste verteilt sind. Anschließend werden Threads erstellt, um den Pfad zwischen den Punkten in jedem Block zu verkürzen (daher "Teilen und Erobern"). Der Haupt-Thread überwacht die anderen und stellt sicher, dass die kürzeste Lösung innerhalb des Zeitlimits angezeigt wird. Wenn ein Thread mit oder ohne Lösung stirbt, startet er einen anderen Thread auf einem anderen Block.

Jeder Thread verwendet den "gierigen" Algorithmus, der an einem zufälligen Punkt beginnt, zum nächsten Punkt geht und sich wiederholt, bis alle Punkte abgedeckt sind (daher "gierig").

Anmerkungen

• Dies dauert 1 Minute (ich habe 3 Sekunden für das Starten / Herunterfahren des Programms und für das Starten der JVM angegeben - Sie wissen nie, worauf die JVM-Startroutinen als nächstes abzielen ...)
• Selbst wenn Lösungen gefunden wurden, wird die Suche fortgesetzt, und nach Ablauf von 1 Minute wird die beste gefundene Lösung angezeigt.
• Ich bin mir nicht sicher, ob diese Implementierung wirklich gut ist. Ich hatte zwar ein bisschen Spaß beim Codieren :)
• Da viele Dinge zufällig sind, wird möglicherweise nicht dieselbe Ausgabe für dieselbe Eingabe ausgegeben.

Einfach kompilieren und java DivideAndConquer.classausführen.

public class DivideAndConquer extends Thread {
    static LinkedList<Point> original;
    static Solution best;
    static LinkedList<DivideAndConquer> bots;
    static final Object _lock=new Object();

    public static void main(String[] args){
        if(args.length != 1) {
            System.err.println("Bad input!");
            System.exit(-1);
        }
        // make sure we don't sleep too long... get the start time
        long startTime = System.currentTimeMillis();
        // parse input
        String[] input=args[0].split(",");
        int numPlayers=Integer.parseInt(input[0]);
        original=new LinkedList<Point>();
        for(int i=1;i<input.length;i+=2){
            original.add(new Point(Integer.parseInt(input[i]), Integer.parseInt(input[i+1])));
        }
        // start threads
        bots=new LinkedList<DivideAndConquer>();
        for(int i=0;i<6;i++)
            bots.add(new DivideAndConquer(i));
        // sleep
        try {
            Thread.sleep(57000 - (System.currentTimeMillis() - startTime));
        } catch(Exception e){} // should never happen, so ignore
        // time to collect the results!
        Solution best=getBestSolution();
        if(best!=null){
            best.apply(original);
            String printStr="";
            for(int i=0;i<original.size();i++){
                Point printPoint=original.get(i);
                printStr+=printPoint.x+","+printPoint.y+",";
            }
            printStr=printStr.substring(0, printStr.length()-1);
            System.out.print(printStr);
        } else {
            System.out.println("Hey, I wonder if the tournament program crashes on NumberFormatExceptions... Anyway, we failed");
        }
    }

    // check the distance
    public static int calculateDistance(List<Point> points){
        int distance = 0;
        for(int i=0;i<points.size();i++){
            int next=i+1;
            if(next>=points.size())next=0;
            distance+=points.get(i).distance(points.get(next));
        }
        return distance;
    }

    public static void solutionFound(Solution s){
        // thanks to Java for having thread safety features built in
        synchronized(_lock){
            // thanks to Java again for short-circuit evaluation
            // saves lazy programmers lines of code all the time
            if(best==null || best.distDifference < s.distDifference){
                best=s;
            }
        }
    }

    public static Solution getBestSolution(){
        // make sure we don't accidentally return
        // the best Solution before it's even
        // done constructing
        synchronized(_lock){
            return best;
        }
    }

    List<Point> myPoints;
    int start;
    int length;
    int id;

    public DivideAndConquer(int id){
        super("DivideAndConquer-Processor-"+(id));
        this.id=id;
        myPoints=new LinkedList<Point>();
        start=(int) (Math.random()*75);
        length=25;
        for(int i=start;i<start+length;i++){
            myPoints.add(original.get(i));
        }
        start();
    }

    public void run(){
        // copy yet again so we can delete from it
        List<Point> copied=new LinkedList<Point>(myPoints);
        int originalDistance=calculateDistance(copied);
        // this is our solution list
        List<Point> solution=new LinkedList<Point>();
        int randomIdx=new Random().nextInt(copied.size());
        Point prev=copied.get(randomIdx);
        copied.remove(randomIdx);
        solution.add(prev);
        while(copied.size()>0){
           int idx=-1;
           int len = -1;
           for(int i=0;i<copied.size();i++){
               Point currentPoint=copied.get(i);
               int dist=prev.distance(currentPoint);
               if(len==-1 || dist<len){
                   len=dist;
                   idx=i;
               }
           }
           prev=copied.get(idx);
           copied.remove(idx);
           solution.add(prev);
        }
        // aaaand check our distance
        int finalDistance=calculateDistance(solution);
        if(finalDistance<originalDistance){
            // yes! solution
            Solution aSolution=new Solution(start, length, solution, originalDistance-finalDistance);
            solutionFound(aSolution);
        }
        // start over regardless
        bots.set(id, new DivideAndConquer(id));
    }

    // represents a solution
    static class Solution {
        int start;
        int length;
        int distDifference;
        List<Point> region;
        public Solution(int start, int length, List<Point> region, int distDifference){
            this.region=new LinkedList<Point>(region);
            this.start=start;
            this.length=length;
            this.distDifference=distDifference;
        }
        public void apply(List<Point> points){
            for(int i=0;i<length;i++){
                points.set(i+start, region.get(i));
            }
        }
    }

    // copied your Point class, sorry but it's useful...
    // just added public to each method for aesthetics
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        Point(Point other){
            this.x = other.x;
            this.y = other.y;
        }
        public boolean equals(Point other){
            if(this.x==other.x && this.y==other.y)
                return true;
            return false;
        }

        public int distance(Point other){
            return Math.abs(x-other.x) + Math.abs(y-other.y);
        }
    }
}