Diberikan daftar poin, temukan jalur terpendek yang mengunjungi semua titik dan kembali ke titik awal.

Masalah Travelling Salesman terkenal di bidang ilmu komputer, seperti banyak cara untuk menghitung / memperkirakannya. Sudah dipecahkan untuk kelompok poin yang sangat besar, tetapi beberapa yang terbesar membutuhkan banyak CPU-tahun untuk menyelesaikannya.

Jangan sampai terbakar oleh kentang.

Hot Potato adalah gim di mana 2+ pemain mengedarkan "kentang" dalam lingkaran sambil memainkan musik. Tujuannya adalah untuk meneruskannya ke pemain berikutnya dengan cepat. Jika Anda memegang kentang saat musik berhenti, Anda keluar.

Objek dari Penjual Kentang Panas adalah:

Dengan seperangkat 100 poin unik , kembalikan poin-poin itu dalam urutan yang lebih baik ( jarak total lebih pendek seperti yang didefinisikan lebih jauh ke bawah ). Ini akan "meneruskan" masalahnya ke pemain berikutnya. Mereka harus meningkatkan dan meneruskannya ke yang lain, dll. Jika seorang pemain tidak dapat meningkatkannya, mereka keluar dan bermain terus sampai satu pemain tersisa.

Agar ini tidak menjadi kompetisi "brute-force-me-a-path", ada ketentuan berikut:

• Anda tidak dapat mengambil lebih dari satu menit untuk melewatkan kentang. Jika Anda belum menemukan dan memberikan solusi yang lebih singkat saat satu menit berlalu, Anda keluar.

• Anda tidak dapat mengubah posisi lebih dari 25 poin. Tepatnya, >= 75poin harus berada di posisi yang sama dengan yang Anda terima. Tidak masalah mana yang Anda putuskan untuk diubah, hanya jumlah yang Anda ubah.

Ketika hanya satu pemain yang tersisa, dia adalah pemenang dari permainan itu, dan menerima satu poin. Turnamen terdiri dari 5*npermainan, di mana njumlah pemain. Setiap permainan, pemain awal akan diputar , dan urutan pemain yang tersisa akan diacak . Pemain dengan poin terbanyak di akhir adalah pemenang pertandingan. Jika pertandingan berakhir dengan dasi untuk tempat pertama, pertandingan baru akan dimainkan hanya dengan para kontestan. Ini akan berlanjut sampai tidak ada dasi.

Pemain pemula untuk setiap permainan akan menerima satu set poin pseudorandomly yang dipilih tanpa urutan tertentu.

Poin didefinisikan sebagai pasangan x,ykoordinat bilangan bulat pada kisi kartesius. Jarak diukur dengan menggunakan Manhattan jarak , |x1-x2| + |y1-y2|. Semua koordinat akan terletak pada [0..199]kisaran.

Memasukkan

Input diberikan dengan argumen string tunggal. Ini akan terdiri dari 201 bilangan bulat yang dipisahkan koma yang mewakili jumlah pemain saat ini ( m) dan 100 poin:

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

Urutan titik-titik ini adalah jalur saat ini. Total jarak diperoleh dengan menambahkan jarak dari setiap titik ke titik berikutnya ( dist(0,1) + dist(1,2) + ... + dist(99,0)). Jangan lupa untuk kembali memulai ketika menghitung jarak total!

Perhatikan bahwa mini bukan jumlah pemain yang memulai pertandingan, itu adalah jumlah yang masih dalam.

Keluaran

Output diberikan dengan cara yang sama seperti input, minus m; string tunggal berisi bilangan bulat yang dipisahkan koma yang mewakili titik dalam orde baru mereka.

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

Program kontrol akan menunggu output hanya untuk satu menit. Ketika output diterima, itu akan memverifikasi bahwa:

• output terbentuk dengan baik
• output hanya terdiri dari dan semua 100 poin hadir dalam input
• >=75 poin ada di posisi semula
• panjang lintasan lebih kecil dari lintasan sebelumnya

Jika salah satu dari cek ini gagal (atau tidak ada output), Anda keluar dan permainan akan berlanjut ke pemain berikutnya.

Program Kontrol

Anda dapat menemukan program kontrol di tautan ini . Program kontrol itu sendiri bersifat deterministik, dan diposting dengan benih dummy 1. Benih yang digunakan selama penilaian akan berbeda, jadi jangan repot-repot mencoba menganalisis daftar urutan belokan / titik yang dikeluarkannya.

Kelas utamanya adalah Tourney. Menjalankan ini akan melakukan turnamen penuh dengan kontestan yang diberikan sebagai argumen. Itu memuntahkan pemenang dari setiap pertandingan dan penghitungan di akhir. Contoh pertandingan dengan dua SwapBots terlihat seperti:

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

Jika Anda ingin menguji hanya satu game pada satu waktu, Anda dapat menjalankan Gamekelas sebagai gantinya. Ini akan menjalankan satu game dengan pemain dalam urutan yang diberikan sebagai argumen. Secara default, itu juga akan mencetak play-by-play yang menunjukkan pemain saat ini dan panjang lintasan.

Juga termasuk beberapa pemain tes: SwapBot, BlockPermuter, dan TwoSwapBot. Dua yang pertama tidak akan dimasukkan dalam penilaian berjalan, jadi jangan ragu untuk menggunakan dan menyalahgunakannya selama pengujian. TwoSwapBot akan dimasukkan dalam penilaian, dan dia tidak bungkuk, jadi bawalah A-game Anda.

Varia

• Anda tidak dapat menyimpan informasi status, dan setiap belokan adalah program terpisah dari program Anda. Satu-satunya informasi yang akan Anda terima setiap belokan adalah serangkaian poin.

• Anda tidak dapat menggunakan sumber daya eksternal. Ini termasuk panggilan jaringan dan akses file.

• Anda tidak dapat menggunakan fungsi pustaka yang dirancang untuk memecahkan / membantu dengan masalah TSP atau variannya.

• Anda tidak dapat memanipulasi atau mengganggu pemain lain dengan cara apa pun.

• Anda tidak dapat memanipulasi atau mengganggu program kontrol atau kelas atau file yang disertakan dengan cara apa pun.

• Multi-threading diizinkan.

• Satu pengiriman per pengguna. Jika Anda mengirim lebih dari satu entri, saya hanya akan memasukkan entri pertama yang dikirimkan. Jika Anda ingin mengubah kiriman Anda, edit / hapus yang asli.

• Turnamen akan berjalan di Ubuntu 13.04, di komputer dengan CPU i7-3770K dan RAM 16GB. Itu tidak akan dijalankan di VM. Apa pun yang saya anggap berbahaya akan segera mendiskualifikasi entri saat ini dan di masa mendatang yang Anda kirimkan.

• Semua entri harus dapat dijalankan dari baris perintah dengan perangkat lunak gratis ( seperti bir ). Jika saya memiliki masalah dalam mengkompilasi / menjalankan entri Anda, saya akan meminta bantuan dalam komentar. Jika Anda tidak merespons atau pada akhirnya saya tidak dapat menjalankannya, itu akan didiskualifikasi.

Hasil (22 Mei 2014)

Hasil baru ada di! UntangleBot telah mengalahkan kompetisi dengan cukup baik. TwoSwapBot berhasil tujuh kemenangan, dan SANNbot menyelipkan kemenangan juga. Ini papan skor, dan tautan ke output mentah :

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

Seperti sekarang , UntangleBot telah memenangkan tanda centang. Namun, jangan biarkan hal itu menghalangi Anda untuk masuk, karena saya akan menjalankan turnamen karena semakin banyak kontestan muncul dan ubah jawaban yang diterima.

UntangleBot (sebelumnya NiceBot)

Bot C ++ 11 yang menggunakan dua strategi.
Pada awalnya ia akan mencoba untuk "mengurai" jalan jika mungkin, dengan mendeteksi persimpangan antara jalur yang lebih dekat dari 25 poin (karena penguraian menyiratkan memodifikasi semua titik di antara).
Jika strategi pertama gagal, itu secara acak bertukar poin untuk menemukan jarak yang lebih baik sampai jalan yang lebih baik telah ditemukan.

Bot ini secara konsisten mengalahkan TwoSwapBot dengan rasio perkiraan lima kemenangan untuk satu kekalahan di turnamen tes saya.

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

(bot anil yang disimulasikan dalam R )

Harus dipanggil dengan 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=","))

Idenya relatif sederhana: setiap belokan adalah satu "langkah pendinginan" dari anil simulasi dengan jumlah pemain yang masih dalam permainan sebagai "suhu" (dimodifikasi oleh jarak saat ini lebih dari 12000, yaitu kira-kira jarak awal). Satu-satunya perbedaan dengan annealing simulasi yang tepat adalah bahwa saya memeriksa bahwa saya tidak mengubah permutasi lebih dari 25 elemen dan jika saya menggunakan 20 gerakan tetapi urutan yang dihasilkan bernilai dari awal maka mulai lagi dari awal.

BozoBot

Memanfaatkan logika kompleks di belakang Bozosort untuk menemukan jalan yang lebih baik. Ini terlihat seperti ini.

• Tukar poin acak
• Jika kami membaik
  • Kembalikan jawabannya
• Jika tidak
  • Coba lagi

BozoBot sekarang telah ditingkatkan dengan Multithreading ! Empat antek sekarang tanpa tujuan menyulap poin sampai mereka menemukan peningkatan. Yang pertama menemukan solusi mendapat cookie!

Ternyata saya gagal dalam 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

Upgrade ke SwapBot, orang ini memeriksa setiap pasang swap. Pertama, ia memeriksa apakah ada pertukaran tunggal yang akan mempersingkat jalur. Jika ya, ia segera kembali. Jika tidak, ia memeriksa masing-masing untuk melihat apakah swap lain akan mempersingkatnya. Jika tidak, dia mati saja.

Sementara jalur masih semi-acak, biasanya kembali dalam sekitar 100 ms. Jika dia harus memeriksa masing-masing dan setiap 2 swap (kira-kira 25 juta), dibutuhkan sekitar 20 detik.

Pada saat pengajuan, ini mengalahkan semua pesaing lainnya di babak uji.

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

Utas

Bot ini

1. Membagi 100 poin dalam 4 10 buah 25 10 poin
2. Mulai utas untuk setiap bagian
3. Di utas, acak acak array, sambil menjaga start dan endpoint tetap
4. Jika jarak array baru lebih pendek, pertahankan
5. Setelah 59 detik, utas utama mengumpulkan hasilnya dan mencetaknya

Idenya adalah untuk menemukan peningkatan terbaik ke jalur, sehingga bot lain akan gagal dengan logika mereka.

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

Membagi Dan Menaklukkan + Bot Serakah

CATATAN: Saya melihat kode Anda Gameyang mencakup hal-hal berikut di 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++;

Namun, tidak ada catch(NumberFormatException)blok, sehingga program Anda kemungkinan akan macet ketika program pemain mengeluarkan string (seperti yang ditunjukkan pada akhir mainmetode program saya ). Saya menyarankan Anda memperbaikinya, karena program dapat menampilkan pengecualian, jejak tumpukan, atau sejenisnya. Kalau tidak, komentari baris itu di program saya sebelum Anda menjalankannya.

Kembali ke topik

Implementasi ini (di Jawa) membagi daftar poin menjadi potongan-potongan 25, spasi secara acak pada daftar. Kemudian, ia menciptakan utas untuk mempersingkat jalur antara titik-titik di setiap potongan (Oleh karena itu, "Bagi dan Taklukkan"). Utas utama memantau yang lain dan memastikan untuk menghadirkan solusi terpendek dalam batas waktu. Jika sebuah utas mati dengan atau tanpa solusi, itu memulai utas lain lagi pada potongan yang berbeda.

Setiap utas menggunakan algoritme "serakah", yang dimulai dari titik acak, menuju ke titik terdekat, dan berulang hingga semua titik dibahas (Oleh karena itu, "serakah").

Catatan

• Ini akan berjalan melalui 1 menit penuh (saya memberi 3 detik untuk startup / shutdown program dan startup JVM - Anda tidak pernah tahu apa yang menjadi rutinitas startup JVM terperangkap di selanjutnya ...)
• Sekalipun telah menemukan solusi, ia akan terus mencari dan setelah 1 menit habis, ia menghadirkan solusi terbaik yang ditemukannya.
• Saya tidak yakin apakah implementasi ini sebenarnya ada gunanya. Saya bersenang-senang mengodekannya :)
• Karena banyak hal yang acak, ini mungkin tidak memberikan output yang sama untuk input yang sama.

Hanya kompilasi dan gunakan java DivideAndConquer.classuntuk menjalankan.

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