Учитывая список точек, найдите кратчайший путь, который посещает все точки и возвращает к начальной точке.

Задача коммивояжера хорошо известна в области компьютерных наук, как и многие способы ее расчета / аппроксимации. Это было решено для очень больших групп точек, но для некоторых из самых больших требуется много лет процессора.

Не обжечься картошкой.

Hot Potato - игра, в которой 2+ игрока раздают «картошку» по кругу, пока играет музыка. Цель состоит в том, чтобы быстро передать его следующему игроку. Если вы держите картошку, когда музыка останавливается, вы ушли.

Объектом продаж горячего картофеля является:

Учитывая набор из 100 уникальных точек , верните эти точки в лучшем порядке ( более короткое общее расстояние, как определено ниже ). Это «передаст» проблему следующему игроку. Они должны улучшить его и передать следующему, и т. Д. Если игрок не может улучшить его, он уходит и игра продолжается до тех пор, пока не останется один игрок.

Чтобы это не было соревнованием "грубой силы-меня-пути", существуют следующие условия:

• Вы не можете занять больше одной минуты, чтобы передать картофель. Если к моменту истечения одной минуты вы не нашли и не приняли более короткое решение, значит, вы вышли.

• Вы не можете изменить положение более 25 очков. Точнее, >= 75очки должны быть в том же положении, в котором вы их получили. Неважно, какие из них вы решите изменить, а только сумму, которую вы меняете.

Когда остается только один игрок, он становится победителем этой игры и получает одно очко. Турнир состоит из 5*nигр, где nуказано количество игроков. Каждую игру начальный игрок будет вращать , а оставшийся игрок будет перетасовываться . Игрок с наибольшим количеством очков в конце является победителем турнира. Если турнир заканчивается ничьей за первое место, новый турнир будет сыгран только с этими участниками. Это будет продолжаться, пока не будет галстука.

Начинающий игрок в каждой игре получит набор случайно выбранных очков в произвольном порядке.

Точки определяются как пара целочисленных x,yкоординат на декартовой сетке. Расстояние измеряется с помощью Manhattan расстояние , |x1-x2| + |y1-y2|. Все координаты будут лежать в [0..199]диапазоне.

вход

Ввод дается с одним строковым аргументом. Он будет состоять из 201 целых чисел, разделенных запятыми, представляющих количество текущих игроков ( m), и 100 очков:

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

Порядок этих точек является текущим путем. Общее расстояние получается путем сложения расстояния от каждой точки до следующей ( dist(0,1) + dist(1,2) + ... + dist(99,0)). Не забудьте вернуться к началу при расчете общего расстояния!

Обратите внимание, что mэто не количество игроков, которые начали игру, а число, которое все еще в игре.

Выход

Вывод дается так же, как ввод, минус m; единственная строка, содержащая целые числа через запятую, представляющие точки в их новом порядке.

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

Управляющая программа будет ожидать выхода только в течение одной минуты. Когда получен вывод, он проверит, что:

• выход хорошо сформирован
• вывод состоит из только и все эти 100 точек представить на входе
• >=75 точки находятся в исходном положении
• длина пути меньше, чем предыдущий путь

Если какая-либо из этих проверок не удалась (или нет выходных данных), вы вышли, и игра перейдет к следующему игроку.

Программа управления

Вы можете найти управляющую программу по этой ссылке . Сама управляющая программа является детерминированной и размещена с фиктивным семенем 1. Семя, используемое во время подсчета очков, будет другим, поэтому не пытайтесь анализировать списки очередей / точек поворота, которые оно выплевывает.

Основной класс есть Tourney. Выполнение этого сделает полный турнир с участниками, приведенными в качестве аргументов. Он выплевывает победителя каждой игры и подсчет в конце. Пример турнира с двумя SwapBots выглядит так:

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

Если вы хотите протестировать только одну игру за раз, вы можете Gameвместо этого запустить класс. Это запустит одну игру с игроками в порядке, указанном в качестве аргументов. По умолчанию, он также будет печатать игру за игрой, показывая текущий игрок и длину пути.

Также включены несколько тестов игроков: SwapBot, BlockPermuterи TwoSwapBot. Первые два не будут включены в оценки, поэтому не стесняйтесь использовать и злоупотреблять ими во время тестирования. TwoSwapBot будет включен в судейство, и он не сутулятся, так что возьмите свою A-игру.

альманах

• Вы не можете сохранить информацию о состоянии, и каждый ход - это отдельный прогон вашей программы. Единственная информация, которую вы будете получать каждый ход - это набор очков.

• Вы не можете использовать внешние ресурсы. Это включает в себя сетевые вызовы и доступ к файлам.

• Вы не можете использовать библиотечные функции, предназначенные для решения / помощи с проблемой TSP или ее вариантами.

• Вы не можете манипулировать другими игроками или мешать им.

• Вы не можете манипулировать или вмешиваться в управляющую программу или любые включенные классы или файлы каким-либо образом.

• Многопоточность разрешена.

• Одно представление на пользователя. Если вы отправите более одной заявки, я введу только первую отправленную. Если вы хотите изменить свое представление, отредактируйте / удалите оригинал.

• Турнир будет проходить на Ubuntu 13.04, на компьютере с процессором i7-3770K и 16 ГБ оперативной памяти. Он не будет работать в ВМ. Все, что я считаю злонамеренным, немедленно дисквалифицирует вашу текущую и будущую заявку.

• Все записи должны запускаться из командной строки с бесплатным ( как в пиве ) программным обеспечением. Если у меня возникнут проблемы с компиляцией / запуском вашей записи, я буду просить помощи в комментариях. Если вы не ответите или я не смогу его запустить, он будет дисквалифицирован.

Результаты (22 мая 2014 г.)

Новые результаты в! UntangleBot довольно разумно обошел конкурентов. TwoSwapBot одержал семь побед, и SANNbot также одержал победу. Вот табло и ссылка на необработанный вывод :

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

Как она стоит прямо сейчас , UntangleBot выиграл галочка. Не позволяйте этому отговорить вас от участия, так как я буду проводить турнир по мере появления большего количества участников и соответственно изменяю принятый ответ.

UntangleBot (ранее NiceBot)

Бот C ++ 11, использующий две стратегии.
Сначала он попытается «распутать» путь, если это возможно, путем обнаружения пересечений между путями, которые ближе, чем 25 точек (поскольку распутывание подразумевает изменение всех промежуточных точек).
Если первая стратегия терпит неудачу, она случайным образом меняет точки, чтобы найти лучшие расстояния, пока не будет найден лучший путь.

Этот бот неизменно побеждает TwoSwapBot с приблизительным соотношением пяти побед за один проигрыш в моих тестовых турнирах.

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

(имитируемый бот отжига в R )

Должен быть вызван с 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=","))

Идея относительно проста: каждый ход представляет собой один «этап охлаждения» имитируемого отжига с количеством игроков, все еще находящихся в игре, в виде «температуры» (изменяемой текущим расстоянием более 12000, то есть приблизительно начальным расстоянием). Единственная разница с надлежащим моделируемым отжигом состоит в том, что я проверил, что я не переставляю более 25 элементов, и если я использовал 20 ходов, но результирующая последовательность стоит, чем начальная, то она начинается снова.

BozoBot

Использует сложную логику, стоящую за Bozosort, чтобы найти лучший путь. Похоже на это.

• Обмен случайных точек
• Если мы улучшили
  • Вернуть ответ
• Иначе
  • Попробуйте еще раз

BozoBot теперь улучшен благодаря многопоточности ! Четыре миньона теперь бесцельно жонглируют точками, пока не наткнулись на улучшение. Первый, кто найдет решение, получит печенье!

Видимо я терплю неудачу в многопоточности.

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

Повышение до SwapBot, этот парень проверяет каждую пару свопов. Во-первых, он проверяет, сократит ли какой-либо отдельный своп путь. Если это так, он возвращается немедленно. Если нет, он проверяет каждый, чтобы увидеть, если другой , сократит своп. Если нет, он просто умирает.

Хотя путь все еще полуслучайный, он обычно возвращается примерно через 100 мс. Если он должен проверять каждый 2-местный обмен (примерно 25М), это займет около 20 секунд.

На момент подачи заявки это превзошло всех других участников в тестовых раундах.

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

винторезный станок

Этот бот

1. Разбивает 100 баллов в 4 10 штук 25 10 баллов
2. Начинает поток для каждого куска
3. В потоке случайным образом перемешайте массив, сохраняя начальную и конечную точки фиксированными
4. Если расстояние нового массива короче, держите его
5. После 59-х основной поток собирает результаты и распечатывает их

Идея состоит в том, чтобы найти лучшее улучшение пути, чтобы другие боты потерпели неудачу со своей логикой.

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

Разделяй и властвуй + Жадный бот

ПРИМЕЧАНИЕ. Я посмотрел на ваш код, для Gameкоторого в 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++;

Однако catch(NumberFormatException)блока нет , поэтому ваша программа, скорее всего, вылетит, когда программа проигрывателя выведет строку (как показано в конце метода моей программы main). Я советую вам это исправить, потому что программы могут выводить исключения, трассировки стека или тому подобное. В противном случае закомментируйте эту строку в моей программе, прежде чем запускать ее.

Вернуться к теме

Эта реализация (в Java) разбивает список точек на 25 частей, случайно расположенных в списке. Затем он создает потоки, чтобы сократить путь между точками в каждом фрагменте (следовательно, «Разделяй и властвуй»). Основной поток отслеживает другие и обеспечивает представление кратчайшего решения в установленные сроки. Если поток умирает с решением или без него, он снова запускает другой поток на другом чанке.

Каждый поток использует «жадный» алгоритм, который начинается в произвольной точке, переходит к ближайшей точке и повторяется до тех пор, пока не будут охвачены все точки (следовательно, «жадные»).

Заметки

• Это будет продолжаться в течение полной 1 минуты (я дал 3 секунды на запуск / выключение программы и запуск JVM - вы никогда не знаете, какие процедуры запуска JVM настанут в следующий раз ...)
• Даже если он нашел решения, он продолжит поиск, и по истечении 1 минуты он представит лучшее найденное решение.
• Я не уверен, что эта реализация действительно хороша. Я немного повеселился, хотя и кодировал его :)
• Поскольку многие вещи являются случайными, это может не дать одинаковый вывод для одного и того же ввода.

Просто скомпилируйте и используйте java DivideAndConquer.classдля запуска.

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