Я реализовал алгоритм согласно этой статье он работает хорошо, но для некоторых тестов он не получает кратчайшего пути,
вот псевдокод
Initialize
For t=1 to iteration number do
For k=1 to l do
Repeat until ant k has completed a tour
Select the city j to be visited next
With probability pij given by Eq. (1)
Calculate Lk
Update the trail levels according to Eqs. (2-4).
End
вот код
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class test2 {
private InputReader cin;
private PrintWriter cout;
double pheromones[][];
double distances[][];
double visibility[][];
static int n;
City[] city;
Ant[] ant;
int m;
int T;
double alpha = 1; // pheromone importance
double beta = 2; // visibility importance
double evaporation = 0.1;
double Q = 100.0;
static class City {
double x, y;
int id;
public City(double x, double y, int id) {
this.x = x;
this.y = y;
this.id = id;
}
}
static class Ant {
int whereAmI;
boolean[] visited;
double tourDistance;
LinkedList<Integer> citiesVisitedInOrder;
int cityEdges[][];
Ant(int whereAmI) {
this.whereAmI = whereAmI;
visited = new boolean[n + 1];
cityEdges = new int[n + 1][n + 1];
reset();
}
void reset() {
Arrays.fill(visited, false);
visited[whereAmI] = true;
for (int i = 1; i <= n; i++)
Arrays.fill(cityEdges[i], 0);
tourDistance = 0;
citiesVisitedInOrder = new LinkedList<>();
citiesVisitedInOrder.addLast(whereAmI);
}
}
//the actual algorithm iteration
/*
Initialize
For t=1 to iteration number do
For k=1 to l do
Repeat until ant k has completed a tour
Select the city j to be visited next
With probability pij given by Eq. (1)
Calculate Lk
Update the trail levels according to Eqs. (2-4).
End
*/
private void solve() {
n = cin.readInt();
initializeParameter();
//the main loop
for (int t = 0; t < T; t++) {
for (int i = 0; i < m; i++) {//for each ant
Ant current = ant[i];
for (int j = 0; j < n; j++) {//for each city
int currentAntsCity = current.whereAmI;
double highestProbability = 0;
int cityId = 1;
double sumNotiation = calculateSum(current.visited, currentAntsCity);
//traverse all non-visited cities and choose the best
boolean good = false;
for (int c = 1; c <= n; c++) {//remove the equal
if (!current.visited[c]) {
double prop = (pow(pheromones[currentAntsCity][c], alpha) * pow(visibility[currentAntsCity][c], beta))
/ sumNotiation;
if (prop >= highestProbability) {
highestProbability = prop;
cityId = c;
good = true;
}
}
}
if (good) {
current.tourDistance += distances[currentAntsCity][cityId];
current.cityEdges[currentAntsCity][cityId] = current.cityEdges[cityId][currentAntsCity] = 1;
current.citiesVisitedInOrder.addLast(cityId);
current.whereAmI = cityId;
current.visited[cityId] = true;
}
}//after n iteration i ant completes a tour
current.tourDistance += distances[current.citiesVisitedInOrder.getFirst()][current.citiesVisitedInOrder.getLast()];
}//update
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double deltaPhermons = 0;
for (int a = 0; a < m; a++) {
if (ant[a].cityEdges[i][j] != 0) {
deltaPhermons += Q / ant[a].tourDistance;
}
}
pheromones[i][j] = pheromones[j][i] = pheromones[i][j] * evaporation + deltaPhermons;
pheromones[i][i] = 0;
}
}
if (t == T - 1)
break;
//reset everything
for (int i = 0; i < m; i++) {
ant[i].reset();
}
}
//get the best ant route
double minDistance = Double.MAX_VALUE;
LinkedList<Integer> minRout = new LinkedList<>();
for (Ant ant : ant) {
if (ant.tourDistance < minDistance) {
minDistance = ant.tourDistance;
minRout = ant.citiesVisitedInOrder;
}
}
cout.println(minDistance);
for (int element : minRout)
cout.print(element + " ");
}
private double calculateSum(boolean[] visited, int currentAntsCity) {
//traverse all non-visited cities
double ans = 0.0;
for (int c = 1; c <= n; c++) {
if (!visited[c]) {
ans +=
pow(pheromones[currentAntsCity][c], alpha) *
pow(visibility[currentAntsCity][c], beta);
}
}
return ans;
}
private void initializeParameter() {
m = 2 * n;
T = 4 * m;
city = new City[n + 1];
pheromones = new double[n + 1][n + 1];
distances = new double[n + 1][n + 1];
visibility = new double[n + 1][n + 1];
//read cities coordinates
for (int i = 1; i <= n; i++) {
city[i] = new City(cin.readDouble(), cin.readDouble(), i);
}
//initialize distances
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
distances[i][j] = distances[j][i] = sqrt(pow(city[i].x -
city[j].x, 2.0) + pow(city[i].y -
city[j].y, 2.0));
}
}
//initialize the pheromones
double pheromones0 = 1.0 / (double) n;
for (int i = 1; i <= n; i++) {
Arrays.fill(pheromones[i], pheromones0);
pheromones[i][i] = 0;
}
//initialize the visibility
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
visibility[i][j] = visibility[j][i] = 1.0 / distances[i][j];
}
}
//initialize the ants
ant = new Ant[m];
Random rand = new Random(); //instance of random class for
for (int i = 0; i < m; i++) {
int random_int = rand.nextInt(n) + 1;
ant[i] = new Ant(random_int);
}
}
public static void main(String args[]) {
new test2().run();
}
private void run() {
// cin = new InputReader(System.in);
// cout = new PrintWriter(System.out);
try {
cin = new InputReader(new FileInputStream("input.txt"));
cout = new PrintWriter(new FileOutputStream("output.txt"));
} catch (FileNotFoundException e) {
//System.out.println(e.toString());
}
solve();
cout.close();
}
//just for faster reading from a file
public static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar, numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public double readDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
private boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}
}
контрольный пример
10
-15 89
-5 -49
-35 -18
7 49
-95 -68
85 -39
53 -1
69 -99
-74 8
-52 -35
the right answer:
615.11811789868988853
1 9 5 10 3 2 8 6 7 4
my coes's output:
685.2134200307595
5 9 10 3 2 8 6 7 4 1
, как вы можете заметить, я не получаю кратчайший путь, я считаю, что ошибка где-то в константе, и сравнение вероятностей!
реализованная мною формула 
и формулы обновления 
как повысить точность алгоритма? или, может быть, что-то не так в моей реализации!