Программа работает дольше, чем ожидалось, работает ли она правильно? - PullRequest
Новая
       39

Программа работает дольше, чем ожидалось, работает ли она правильно?

0 голосов
/ 10 октября 2019

не уверен, что это правильное место ... Я использую код перебора, чтобы решить проблему с асимметричной продажей путешественников. У него 17 городов, один фиксированный, поэтому у него будет 16! (> 20 триллионов) перестановок для проверки. 

unsigned long TotalCost(unsigned long *Matrix, short *Path, short 
Dimention)
{
    unsigned long result = 0;
    unsigned long Cost;
    int iD;

    for (iD = 1; iD <= Dimention; iD++)
    {
            Cost = Matrix[Dimention*Path[iD - 1] + Path[iD]];
            if (Cost > 0)
            {
                result = result + Cost;
            }
            else
            {
                return 4099999999;
            }

    }
    return result;
}

void swapP(short *x, short *y)
{
    short temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(unsigned long *Matrix, short Dimention, unsigned long *CurrentMin, short *PerPath, short **MinPath, short l, short r)
{
short i;
unsigned long CCost;

if (l == r)
{
    CCost = TotalCost(Matrix, PerPath, Dimention);
    if (CCost < (*CurrentMin))
    {
        for (i = 0; i <= Dimention; i++)
        {
            (*MinPath)[i] = PerPath[i];
        }
        (*CurrentMin) = CCost;
        PrintResults(Matrix, PerPath, Dimention, 2);
    }
}
else
{
    for (i = l; i <= r; i++)
    {
        swapP((PerPath+l), (PerPath+i));
        permute(Matrix, Dimention, CurrentMin, PerPath, MinPath, l+1, r);
        swapP((PerPath+l), (PerPath+i)); //backtrack
    }
}
}

int main (void)
{
// The ommited code here, allocs memory for the matrix, HcG and HrGR array
// it also initializes them

   permute(Matrix, Dimention, &TotalMin, HcG, &HrGR, 1, Dimention - 1);
}

Я протестировал приведенный выше код для экземпляра из пяти городов, и он успешно вернулся, как и ожидалось, за несколько миллисекунд. Для 17 городов я сначала думал, что это займет несколько часов, а затем пару дней. Он работает в течение 4 дней, и я начинаю подозревать, что программа по какой-то причине больше не работает, как будто она заморожена. Я не получаю никаких ошибок, но это занимает намного больше времени, чем я ожидал, программа печатает общую стоимость и путь каждый раз, когда находит путь с более низкой стоимостью, но она перестала печатать через полчаса с момента запуска.

Я использую Ubuntu 18.04, программа «работает» на терминале, системный монитор сообщает Memory: N / A, значит ли это, что он не использует память? Это также говорит CPU: 6%, я могу увеличить его? Есть ли способ проверить, работает ли он правильно? Или оценить, сколько времени потребуется, чтобы закончить? Я так не уверен в его целостности, что думаю, что должен остановить процесс, но в то же время я действительно хотел увидеть результаты.

1 Ответ

1 голос
/ 10 октября 2019

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

  1. добавить оператор печати способом (возможно, со счетчиком модов), который вы ожидаетепечатать, чтобы выходить примерно один раз каждые 2-3 минуты. Включите некоторую информацию в распечатку, чтобы вы могли определить, как далеко продвигается ваша симуляция. (обратите внимание, что среди этой информации вы, вероятно, захотите обязательно распечатать переменные, которые, в случае их сброса, могут вызвать бесконечный цикл, например, «Измерение» (что вы допустили, например, с ошибкой)

  2. Я бы лично не прыгнул с 5 городов на 17. Скорее с 5 на 7, потом, может быть, на 9 или 10 ... просто чтобы подтвердить, что все работает, и понять, сколько времени нужно ожидать с вашим конкретным процессором.

Наконец, в ситуации, в которой вы сейчас находитесь, возможно ли получить другое окно и запустить «ps», чтобы увидеть, получает ли ваша работа какое-либо время процессора? Если нет, то мой подходчтобы убить его и реализовать, как я описал выше. HTH.

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

...