8

// Salesman.cpp : Defines the entry point for the console application.
//

#include "pch.h"
#include "stdio.h"
#include "Windows.h"
#include "time.h"
#include "math.h"

int M[6][6] =
{
    {-1, 1, 4, 5, -1, -1},
    {1, -1, -1, 2, -1, 6},
    {4, -1, -1, -1, 2, -1},
    {5, 2, -1, -1, -1, 3},
    {-1, -1, 2, -1, -1, 2},
    {-1, 6, -1, 3, 2, -1}
};

/*
int M[5][5] =
{
    {-1, 20, 18, 12, 8},
    {5, -1, 14, 7, 11},
    {12, 18, -1, 6, 11},
    {11, 17, 11, -1, 12},
    {5, 5, 5, 5, -1},
};
*/
const float k = 0.8; //скорость испарения
const int n = 8;//количество ребер
const int m = 6;//количество вершин
const int numAnts = 5000;

struct Rib
{
    int num[2];
    int weight;
    float pheromoune;
    float chance;
};

struct Ant
{
    int isAlive;
    int currentPeak;
    int tabuList[m+1];
};

//Находится ли вершина peak в табу-листе
int HasInTabu(int peak, Ant *ant)
{
    for (int i = 0; i < m+1; i++)
    {
        if (ant->tabuList[i] == peak) return 1;
    }
    return 0;
}

//Проверяет, может ли данный муравей пройти куда нибудь
int CanAntMove(Ant *ant)
{
    for (int i = 0; i < m; i++)
    {
        if ((M[ant->currentPeak][i] > 0) && !HasInTabu(i, ant)) return 1;
    }

    return 0;
}


float UpdatePheromoune(const float k, Rib *currentRib)
{
    return (1.0f - k)*currentRib->pheromoune + (1.0f / currentRib->weight);

}

float CalcChance(Rib *rib, Rib *edgesOfI, int countEdges)
{
    float sum = 0;
    for (int i = 0; i < countEdges; i++)
    {
        sum += edgesOfI[i].pheromoune + 1.0f / edgesOfI[i].weight;
    }
    rib->chance = (rib->pheromoune + 1.0f / rib->weight) / sum;
    return rib->chance * 100;
}

//Возвращает ребро из списка по номерам вершин
Rib* GetRib(int firstPeak, int secondPeak, Rib *ribs, int count)
{
    for (int i = 0; i < count; i++)
    {
        if(((ribs[i].num[0] == firstPeak) && (ribs[i].num[1] == secondPeak) ||
            ((ribs[i].num[0] == secondPeak) && (ribs[i].num[1] == firstPeak))))
            return &ribs[i];
    }
    return NULL;
}


//создаем ребра по матрице
int RibsAuto(Rib ribs[n], int weights[][m])
{
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        if (count == n) break;

        for (int j = 0 + i; j < m; j++)
        {
            if (weights[i][j] > 0)
            {
                ribs[count].num[0] = i;
                ribs[count].num[1] = j;
                ribs[count].pheromoune = 0;
                ribs[count].chance = 0;
                ribs[count].weight = weights[i][j];
                count++;

            }
        }
    }
    return count;
}

int CalcLength(int *list, Rib *ribs, Ant *ant)
{
    int length = 0;

    for (int i = 0; i < m; i++)
    {
        if(list[i+1] > -1)
            length += GetRib(list[i], list[i + 1], ribs, n)->weight;
    }
    return length;
}


//решает, что будет делать муравей
int AntSolute(Ant *ant, Rib *ribs)
{
    //проверяем можно ли нам куда идти с помощью табу, или не достигнем начала;
    //ИЛИ ВЫЧИСЛЯЕМ ВЕРОЯТНОСТЬ ПОСЛЕ ИССЛЕДОВАНИЯ!!!

    if (!CanAntMove(ant))
    {
        ant->isAlive = 0;//убиваем муравья

        //обновить феромоны на всем пути

        for (int i = 0; i < m+1; i++)
        {
            if (ant->tabuList[i] == -1)
            {
                ant->tabuList[i] = ant->currentPeak;
                break;
            }
        }
        for (int i = 0; i < m + 1; i++)
        {
            if (ant->tabuList[i] == -1)
            {
                if (GetRib(ant->currentPeak, ant->tabuList[0], ribs, n))
                {
                    ant->tabuList[i] = ant->tabuList[0];
                    break;
                }
                return 0;
            }
        }

        int length = CalcLength(ant->tabuList, ribs, ant);

        for (int i = 0; i < m; i++)
        {
            if (ant->tabuList[i + 1] > -1)
            {
                Rib *temp = GetRib(ant->tabuList[i], ant->tabuList[i + 1], ribs, n);
                temp->pheromoune = UpdatePheromoune(k, temp);
            }
        }
        for (int i = 0; i < m+1; i++)
            if (ant->tabuList[i] > -1)printf("%d - ", ant->tabuList[i] + 1);
        printf(" Length = %d\n", length);
        memset(&ant->tabuList, -1, sizeof(ant->tabuList)); //обнуляем табу-лист
        return 0;
    }
    else
    {
        int peaks[m-1];
        int count = 0;

        for (int i = 0; i < m; i++)
        {
            if (M[ant->currentPeak][i] > 0 && !HasInTabu(i, ant))
            {
                peaks[count] = i;
                count++;
            }
        }

        Rib edgesFromCity[m-1];
        //заполняем массив ребер возможных из данного города
        for (int i = 0; i < count; i++)
            edgesFromCity[i] = *GetRib(ant->currentPeak, peaks[i], ribs, n);

        int nextPeak = 0;
        int chances[n];
        chances[0] = CalcChance(GetRib(ant->currentPeak, peaks[0], ribs, n), edgesFromCity, count);

        for (int i = 1; i < count-1; i++)
            chances[i] = chances[i-1] + CalcChance(GetRib(ant->currentPeak, peaks[i], ribs, n), edgesFromCity, count);
        chances[count - 1] = 100;
        //сортировка массива
        for (int i = 0; i < count - 1; i++)
        {
            for (int j = 0; j < count - i - 1; j++)
            {
                if (chances[j] > chances[j+1])
                {
                    int temp = chances[j];
                    chances[j] = chances[j + 1];
                    chances[j + 1] = temp;
                }
            }
        }

        int random = rand() % 100;

        for (int i = 0; i < count; i++)
        {
            if (random < chances[i])
            {
                nextPeak = peaks[i];
                break;
            }
        }

        //заносим следующую вершину в табу-лист
        for (int i = 0; i < m+1; i++)
        {
            if (ant->tabuList[i] == -1)
            {
                ant->tabuList[i] = ant->currentPeak;
                break;
            }
        }
        //переходим туда
        ant->currentPeak = nextPeak;
        return 1;
    }
}

//Проверяет, есть ли живые муравьи в массиве ants
int HasAntAlive(Ant *ants, int quantityAnt)
{
    for (int i = 0; i < quantityAnt; i++)
        if (ants[i].isAlive) return 1;

    return 0;
}

int main()
{


    Rib ribs[n];
    RibsAuto(ribs, M);

    //delete &agents[1];

    srand(time(NULL));
    /*
    //оживляем муравьев
    for (int i = 0; i < 6; i++)
    {
        agents[i].isAlive = 1;
        agents[i].currentPeak = 0;
        memset(&agents[i].tabuList, -1, sizeof(agents[i].tabuList));
    }

    //исследование
    while (HasAntAlive(agents, 6))
    {
        //выбираем муравьев и решаем куда им идти
        for (int i = 0; i < 6; i++)
        {
            if (agents[i].isAlive == 1)
                AntSolute(&agents[i], ribs);
        }
        //обновляем феромоны?
        for (int i = 0; i < n; i++)
            if (ribs[i].pheromoune > 0) UpdatePheromoune(k, &ribs[i]);

    }*/
    Ant superAgents[numAnts];
    for (int i = 0; i < numAnts; i++)
    {
        superAgents[i].isAlive = 1;
        superAgents[i].currentPeak = 2;
        memset(&superAgents[i].tabuList, -1, sizeof(superAgents[i].tabuList));
    }

    //исследование
    while (HasAntAlive(superAgents, numAnts))
    {
        //выбираем муравьев и решаем куда им идти
        for (int i = 0; i < numAnts; i++)
        {
            if (superAgents[i].isAlive == 1)
                AntSolute(&superAgents[i], ribs);
        }

    }
    system("pause");

    return 0;
}