graphs/AntColony/Algorithm/DefaultAnt.cs

namespace AntColony.Algorithm;

/// <summary>
/// Стандартная реализация муравья
/// </summary>
/// <param name="alpha">Значение α (определяет вес феромонов)</param>
/// <param name="beta">Значение β (определяет вес расстояния)</param>
/// <param name="Q">Значение Q (множитель депозита феромонов)</param>
public class DefaultAnt(double alpha = 1, double beta = 1, double Q = 100) : IAnt
{
    private List<int> tour = [];
    private double distance = double.PositiveInfinity;

    /// <inheritdoc/>
    public (List<int> tour, double distance)? ConstructTour(ref double[][] distances, ref double[][] pheromones)
    {
        tour = [];
        distance = double.PositiveInfinity;
        var visited = new bool[distances.Length];
        var curCity = Random.Shared.Next(distances.Length);

        tour.Add(curCity);
        visited[curCity] = true;

        // Пока остались непосещенные города
        while (tour.Count < distances.Length)
        {
            var sel = SelectNextCity(curCity, ref visited, ref distances, ref pheromones);
            while (!sel.HasValue) sel = SelectNextCity(curCity, ref visited, ref distances, ref pheromones);
            // Если не можем найти следующий город - самоубиваемся
            if (sel is not { } nextCity) return null;
            tour.Add(nextCity);
            visited[nextCity] = true;
            curCity = nextCity;
        }

        // Если не можем найти путь до стартовой точки - самоубиваемся
        if (distances[curCity][tour[0]] == 0) return null;

        tour.Add(tour[0]);

        distance = CalculateTourDistance(tour, ref distances);

        return (tour, distance);
    }

    /// <inheritdoc/>
    public void UpdatePheromones(ref double[][] pheromones)
    {
        double deposit = Q / distance;
        for (int i = 0; i < tour.Count - 1; i++)
        {
            int cityA = tour[i];
            int cityB = tour[i + 1];
            pheromones[cityA][cityB] += deposit;
            pheromones[cityB][cityA] += deposit;  // Ненаправленный граф
        }
    }

    private static double CalculateTourDistance(List<int> tour, ref double[][] distances)
    {
        double distance = 0;
        for (int i = 0; i < tour.Count - 1; i++)
        {
            distance += distances[tour[i]][tour[i + 1]];
        }
        return distance;
    }

    private int? SelectNextCity(int currentCity, ref bool[] visited, ref double[][] distances, ref double[][] pheromones)
    {
        var probabilities = new double[distances.Length];
        double probabilitiesSum = 0;

        // Вероятности для каждого непосещенного города
        for (int i = 0; i < distances.Length; i++)
        {
            if (!visited[i])
            {
                if (distances[currentCity][i] == 0) continue;
                probabilities[i] = Math.Pow(pheromones[currentCity][i], alpha) *
                                 Math.Pow(1.0 / distances[currentCity][i], beta);
                probabilitiesSum += probabilities[i];
            }
        }

        // Случайно выбираем следующий город (по вероятностям)
        double randomValue = Random.Shared.NextDouble() * probabilitiesSum;
        //double sum = 0;

        for (int i = 0; i < distances.Length; i++)
        {
            if (!visited[i])
            {
                //sum += probabilities[i];
                if (probabilities[i] >= randomValue)
                {
                    return i;
                }
            }
        }

        return null;
    }
}