Коммивояжер по Java

Основываясь на этом псевдокоде, я пытаюсь реализовать функцию пригодности java для проблемы коммивояжера, но я не уверен, что делаю это правильно, может кто-нибудь помочь мне.

N   The number of cities to visit
T   A tour (list of integers of size N)
D   An N by N matrix containing each d(i,j)

Let s = 0
For i = 1 to (N-1)
Let a = ti
Let b = ti+1
Let s = s + d(a,b)
 End For
     Let end_city = tn
     Let start_city = t1
     Let s = s + d(end_city,start_city)
The tour length s

Моя попытка написать это на java

public static ArrayList<Integer> Fitness(){
    int n = 10; // Number of cities to visit
    ArrayList<Integer> t = new ArrayList<Integer>();
    int[][] d = null;
    int s = 0, a, b;

    for (int i = 1; i<n; i++){
        for (int j = 1; j<n; j++){
            d = new int[i][j];
        }

        for( i = 1; i<n; i++){
            a = t.get(i);
            b = t.get(i+1);
            s = s + d[a][b];
        }
        int end_city = t.get(n);
        int start_city = t.get(1);
        s = s + d[end_city][start_city];
    }
    return t;

Может кто-нибудь, пожалуйста, помогите мне. Спасибо.


java arraylist traveling-salesman
person Mikey    schedule 25.02.2015    source источник
comment
примечание: индексы массива в java основаны на 0, см. учебное пособие подробности   -  person harshtuna    schedule 26.02.2015

Ответы (1)


arrow_upward
1
arrow_downward

Вы должны начать решать, что у вас есть и чего вы хотите.

Что у тебя есть

Для фитнес-функции для задачи коммивояжера в соответствии с вашим псевдокодом у вас будет следующий ввод.

  • Количество городов
  • Тур, пригодность которого должна быть рассчитана
  • Карта с расстояниями (в данном случае матрица смежности).

Это должны быть формальные параметры вашей фитнес-функции.

Что вы хотите

Цель фитнес-функции состоит в том, чтобы иметь способ измерить качество с точки зрения одного параметра.

В этом случае длина служит этой цели.

Это должно быть возвращаемое значение вашей фитнес-функции.

Это делает прототип вашей фитнес-функции следующим:

public double fitness(List<Integer> tour,
                      int numberOfCities,
                      double[][] distanceBetween);

Теперь псевдокод для тела легко расшифровать, если вы правильно сделаете отступ и посмотрите еще раз.

Let s = 0
For i = 1 to (N-1)
    Let a = ti
    Let b = ti+1
    Let s = s + d(a,b)
End For
Let end_city = tn
Let start_city = t1
Let s = s + d(end_city,start_city)
The tour length s

Остальное должно быть довольно легко решить. Это довольно просто перевести на Java.

Удачи.

person Tanmay Patil    schedule 25.02.2015
comment
вы видите для этой части Пусть a = ti, Пусть b = ti+1, Пусть s = s + d(a,b). Правильно ли я сделал. Кроме того, у меня есть тип переменной, который представляет «Let»? например пусть a = ti будет ли a int? - person Mikey; 26.02.2015
comment
Поскольку псевдокод максимально избегает указания типов, вам придется работать с ним самостоятельно. В данном случае все эти переменные указывают расстояния. Таким образом, это будут переменные типа double. В общем, Let представляет собой присвоение значения переменной. - person Tanmay Patil; 26.02.2015
comment
Я получаю сообщение об ошибке в List‹Integer›, в котором говорится, что список типов не является универсальным; его нельзя параметризовать аргументами ‹Integer› - person Mikey; 26.02.2015
comment
Проверьте, не импортировали ли вы какой-либо класс List, отличный от java.util.List. - person Tanmay Patil; 26.02.2015
comment
Спасибо, я пропустил этот импорт. - person Mikey; 26.02.2015
comment
Рад узнать, что это помогло. - person Tanmay Patil; 26.02.2015
comment
Кстати, что представляет собой эта линия? D Матрица N на N, содержащая каждый d(i,j) - person Mikey; 26.02.2015
comment
Кроме того, вы видите для этой части Пусть a = ti, Пусть b = ti+1, Пусть s = s + d(a,b). Правильно ли я сделал. - person Mikey; 26.02.2015
comment
Матрица D (N на N) — см. страницу TSP. набор городов и стоимость проезда между каждой парой из них. В другой формулировке D представляет расстояния между каждой парой городов. - person harshtuna; 26.02.2015
comment
Матрица — это двумерный массив distanceBetween, о котором я упоминал в прототипе. Когда вы обращаетесь к его значению по двум индексам, соответствующим двум городам, между которыми должно быть рассчитано расстояние, оно дает вам расстояние. - person Tanmay Patil; 26.02.2015
comment
Вы сделали эту часть правильно, но вам не следует создавать массив в методе. Массив должен быть передан методу в качестве аргумента. - person Tanmay Patil; 26.02.2015
comment
Привет, извините, по какой-то странной причине это не позволит мне проголосовать, но я отметил это как правильное. Спасибо за вашу помощь. - person Mikey; 28.02.2015