Biorąc pod uwagę listę punktów, znajdź najkrótszą ścieżkę, która odwiedza wszystkie punkty i wraca do punktu początkowego.

Problem komiwojażera jest dobrze znane w dziedzinie informatyki, jak wiele sposobów, aby obliczyć / przybliżają go. Zostało to rozwiązane dla bardzo dużych grup punktów, ale niektóre z największych wymagają wielu lat procesora.

Nie daj się spalić ziemniakowi.

Hot Potato to gra, w której ponad 2 graczy przesyła „ziemniaka” w kółko podczas odtwarzania muzyki. Celem jest szybkie przekazanie go następnemu graczowi. Jeśli trzymasz ziemniaka, gdy muzyka przestaje grać, jesteś poza domem.

Przedmiotem sprzedaży Hot Potato jest:

Biorąc pod uwagę zestaw 100 unikalnych punktów , zwróć te punkty w lepszej kolejności ( krótszy całkowity dystans zdefiniowany w dalszej części ). Spowoduje to „przekazanie” problemu do następnego gracza. Muszą go ulepszyć i przekazać do następnego itd. Jeśli gracz nie może go ulepszyć, nie ma go i gra trwa do momentu, aż opuści jednego gracza.

Aby nie był to konkurs „brutalna siła-mnie-a-ścieżka”, istnieją następujące warunki:

• Przekazanie ziemniaka nie może zająć więcej niż minutę . Jeśli do końca minuty nie znalazłeś i nie przeszedłeś krótszego rozwiązania, jesteś poza domem.

• Nie możesz zmienić pozycji o więcej niż 25 punktów. Aby być dokładnym, >= 75punkty muszą znajdować się w tej samej pozycji, w jakiej je otrzymałeś. Nie ma znaczenia, które z nich zdecydujesz się zmienić, wystarczy zmiana kwoty .

Gdy zostaje tylko jeden gracz, jest on zwycięzcą tej gry i otrzymuje jeden punkt. Turniej składa się z 5*ngier, w których njest liczba graczy. W każdej grze gracz rozpoczynający zostanie obrócony , a kolejność pozostałych graczy zostanie potasowana . Gracz z największą liczbą punktów na końcu jest zwycięzcą turnieju. Jeśli turniej zakończy się remisem na pierwsze miejsce, nowy turniej zostanie rozegrany tylko z tymi uczestnikami. Będzie to trwało, dopóki nie będzie remisu.

Gracz rozpoczynający dla każdej gry otrzyma zestaw pseudolosowo wybranych punktów w dowolnej kolejności.

Punkty są zdefiniowane jako para x,ywspółrzędnych całkowitych na siatce kartezjańskiej. Odległość jest mierzona za pomocą odległość Manhattan , |x1-x2| + |y1-y2|. Wszystkie współrzędne będą w [0..199]zakresie.

Wkład

Dane wejściowe są podawane z argumentem o pojedynczym ciągu. Będzie się składał z 201 liczb całkowitych oddzielonych przecinkami reprezentujących liczbę obecnych graczy ( m) i 100 punktów:

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

Kolejność tych punktów jest bieżącą ścieżką. Całkowitą odległość uzyskuje się przez dodanie odległości od każdego punktu do następnego ( dist(0,1) + dist(1,2) + ... + dist(99,0)). Nie zapomnij powrócić, aby rozpocząć obliczanie całkowitego dystansu!

Pamiętaj, że niem jest to liczba graczy, którzy rozpoczęli grę, to liczba, która wciąż jest w grze.

Wydajność

Dane wyjściowe są podawane w taki sam sposób jak dane wejściowe, minus m; pojedynczy ciąg zawierający liczby całkowite oddzielone przecinkami reprezentujące punkty w ich nowej kolejności.

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

Program sterujący będzie czekał na wyjście tylko przez jedną minutę. Po otrzymaniu danych wyjściowych sprawdzi, czy:

• wynik jest dobrze uformowany
• wyjście składa się tylko ze wszystkich 100 punktów obecnych na wejściu
• >=75 punkty znajdują się w swoich pierwotnych pozycjach
• długość ścieżki jest mniejsza niż poprzednia ścieżka

Jeśli którykolwiek z tych testów zakończy się niepowodzeniem (lub nie ma danych wyjściowych), gra się kończy, a gra przejdzie do następnego gracza.

Program kontroli

Program sterujący można znaleźć pod tym linkiem . Sam program sterujący jest deterministyczny i jest wysyłany z nasieniem fikcyjnym 1. Ziarno użyte podczas oceniania będzie inne, więc nie zawracaj sobie głowy analizowaniem wyrzucanych przez ciebie kolejności / punktów zwrotów.

Główną klasą jest Tourney. Uruchomienie tego spowoduje pełny turniej z uczestnikami podanymi jako argumenty. Wyrzuca zwycięzcę każdej gry i podsumowanie na końcu. Przykładowy turniej z dwoma SwapBotami wygląda następująco:

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

Jeśli chcesz przetestować tylko jedną grę na raz, możesz Gamezamiast tego uruchomić klasę. To uruchomi jedną grę z graczami w kolejności podanej jako argument. Domyślnie wydrukuje również play-by-play pokazujący aktualny odtwarzacz i długość ścieżki.

Również kilka testów gracze: SwapBot, BlockPermuter, i TwoSwapBot. Pierwsze dwa nie zostaną uwzględnione w biegach punktacji, więc możesz ich używać i nadużywać podczas testowania. TwoSwapBot zostanie uwzględniony w ocenie, a on nie jest garbaty, więc weź swoją grę A.

Zbieranina

• Nie możesz zapisać informacji o stanie, a każda kolej to osobne uruchomienie programu. Jedyną informacją, którą otrzymasz w każdej turze, jest zestaw punktów.

• Nie możesz korzystać z zasobów zewnętrznych. Obejmuje to połączenia sieciowe i dostęp do plików.

• Nie można używać funkcji bibliotecznych zaprojektowanych do rozwiązania / pomocy w przypadku problemu TSP lub jego wariantów.

• Nie możesz w żaden sposób manipulować lub ingerować w innych graczy.

• Nie można w żaden sposób manipulować ani ingerować w program sterujący ani zawarte w nim klasy lub pliki.

• Wielowątkowość jest dozwolona.

• Jedno zgłoszenie na użytkownika. Jeśli prześlesz więcej niż jeden wpis, wprowadzę tylko pierwszy przesłany. Jeśli chcesz zmienić swoje zgłoszenie, edytuj / usuń oryginał.

• Turniej odbędzie się na Ubuntu 13.04, na komputerze z procesorem i7-3770K i 16 GB pamięci RAM. Nie będzie działać na maszynie wirtualnej. Wszystko, co uznam za szkodliwe, natychmiast zdyskwalifikuje bieżące i wszelkie przyszłe wpisy, które prześlesz.

• Wszystkie wpisy muszą być uruchamiane z wiersza poleceń za pomocą bezpłatnego ( jak w przypadku piwa ) oprogramowania. Jeśli mam problemy ze skompilowaniem / uruchomieniem twojego wpisu, poproszę o pomoc w komentarzach. Jeśli nie odpowiesz lub nie uda mi się go uruchomić, zostanie zdyskwalifikowany.

Wyniki (22 maja 2014 r.)

Nowe wyniki już są! UntangleBot dość mocno pokonał konkurencję. TwoSwapBot odniósł siedem zwycięstw, a SANNbot również odniósł zwycięstwo. Oto tablica wyników i link do surowego wyniku :

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

Jak stoi teraz , UntangleBot zdobył zaznaczenie. Nie zniechęcaj cię jednak do wzięcia udziału w turnieju, ponieważ poprowadzę turniej, gdy pojawi się więcej uczestników i odpowiednio zmienię przyjętą odpowiedź.

UntangleBot (wcześniej NiceBot)

Bot C ++ 11 korzystający z dwóch strategii.
Najpierw spróbuje „rozplątać” ścieżkę, jeśli to możliwe, wykrywając przecięcia między ścieżkami, które są bliżej niż 25 punktów (ponieważ rozplątywanie oznacza modyfikację wszystkich punktów pomiędzy).
Jeśli pierwsza strategia zawiedzie, losowo zamienia punkty, aby znaleźć lepsze odległości, dopóki nie zostanie znaleziona lepsza ścieżka.

Ten bot konsekwentnie bije TwoSwapBot o przybliżonym stosunku pięciu zwycięstw za jedną stratę w moich testowych turniejach.

// 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

(symulowany bot wyżarzający w R )

Powinny być wywoływane z 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=","))

Pomysł jest stosunkowo prosty: każda tura to jeden „etap chłodzenia” symulowanego wyżarzania z liczbą graczy wciąż obecnych w grze jako „temperatura” (modyfikowana aktualną odległością ponad 12000, tj. Mniej więcej odległością początkową). Jedyną różnicą przy odpowiednim symulowanym wyżarzaniu jest to, że sprawdziłem, czy nie permutuję więcej niż 25 elementów i jeśli wykorzystałem 20 ruchów, ale wynikowa sekwencja jest warta niż początkowa, to zaczyna się od nowa.

BozoBot

Wykorzystuje złożoną logikę stojącą za Bozosort, aby znaleźć lepszą ścieżkę. To wygląda tak.

• Zamień losowe punkty
• Jeśli się poprawimy
  • Zwróć odpowiedź
• Inaczej
  • Spróbuj ponownie

BozoBot został teraz ulepszony dzięki wielowątkowości ! Cztery stwory bezcelowo żonglują punktami, dopóki nie natkną się na ulepszenie. Pierwszy, który znajdzie rozwiązanie, otrzymuje plik cookie!

Najwyraźniej nie potrafię wielowątkowości.

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

Ulepszenie SwapBottego faceta sprawdza każdą parę zamian. Najpierw sprawdza, czy jakakolwiek pojedyncza zamiana skróci ścieżkę. Jeśli tak, natychmiast wraca. Jeśli nie, sprawdza każdą z nich, aby sprawdzić, czy kolejna zamiana ją skróci. Jeśli nie, po prostu umiera.

Chociaż ścieżka jest nadal w połowie losowa, zwykle powraca po około 100 ms. Jeśli będzie musiał sprawdzać każde 2-zamiany (około 25 mln), zajmuje to około 20 sekund.

W momencie zgłoszenia pokonało to wszystkich innych zawodników w rundach testowych.

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);}
    }
}

Gwintownica

Ten bot

1. Dzieli 100 punktów na 4 10 części po 25 10 punktów
2. Rozpoczyna wątek dla każdego elementu
3. W wątku losowo przetasuj tablicę, zachowując jednocześnie punkt początkowy i końcowy
4. Jeśli odległość nowej tablicy jest mniejsza, zachowaj ją
5. Po 59 sekundach główny wątek zbiera wyniki i drukuje je

Chodzi o to, aby znaleźć najlepszą poprawę ścieżki, tak aby inne boty zawiodły swoją logiką.

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;
    }
}

Divide And Conquer + Greedy Bot

UWAGA: Przejrzałem twój kod, Gamektóry zawiera następujące elementy w Game.parsePath:

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++;

Jednak nie ma żadnego catch(NumberFormatException)bloku, więc twój program najprawdopodobniej ulegnie awarii, gdy program odtwarzający wyświetli ciąg znaków (jak pokazano na końcu metody mojego programu main). Radzę to naprawić, ponieważ programy mogą wyświetlać wyjątki, ślady stosu itp. W przeciwnym razie skomentuj ten wiersz w moim programie, zanim go uruchomisz.

Powrót do tematu

Ta implementacja (w Javie) dzieli listę punktów na kawałki po 25, losowo rozmieszczone na liście. Następnie tworzy wątki, aby skrócić ścieżkę między punktami w każdej części (stąd „Dziel i rządź”). Główny wątek monitoruje pozostałe i zapewnia przedstawienie najkrótszego rozwiązania w wyznaczonym terminie. Jeśli wątek umiera z rozwiązaniem lub bez niego, rozpoczyna kolejny wątek na innym fragmencie.

Każdy wątek wykorzystuje algorytm „chciwy”, który rozpoczyna się od losowego punktu, przechodzi do najbliższego punktu i powtarza, aż wszystkie punkty zostaną pokryte (stąd „chciwy”).

Notatki

• Trwa to pełną minutę (dałem 3 sekundy na uruchomienie / zamknięcie programu i uruchomienie JVM - nigdy nie wiesz, jakie procedury uruchamiania JVM zostaną złapane w następnym ...)
• Nawet jeśli znalazł rozwiązania, będzie szukał dalej, a po upływie 1 minuty przedstawi najlepsze znalezione rozwiązanie.
• Nie jestem pewien, czy ta implementacja jest naprawdę dobra. Bawiłem się jednak kodowaniem :)
• Ponieważ wiele rzeczy jest losowych, może to nie dać tego samego wyniku dla tych samych danych wejściowych.

Wystarczy skompilować i użyć, java DivideAndConquer.classaby uruchomić.

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);
        }
    }
}