Как изменить индекс строки и столбца во вложенном цикле for?

Question

Я пытаюсь выяснить кратчайшее расстояние, путешествуя по городу. У меня уже есть начальная точка, город «0», тогда мы посетим каждый город без повторного посещения предыдущего города. В этом случае нам не нужно возвращаться в город 0.

Предположим, у нас есть 4 города, тогда у нас будет матрица с расстоянием. То, что я пытаюсь сделать, - это то, что я буду перебирать каждый возможный маршрут и получу стоимость для каждого маршрута.

Таким образом, весь возможный маршрут с городом № 4 -

city[0][1] + city[1][2] + city[2][3] 
city[0][1] + city[1][3] + city[3][2] 

city[0][2] + city[2][1] + city[1][3] 
city[0][2] + city[2][3] + city[3][1] 

city[0][3] + city[3][1] + city[1][2] 
city[0][3] + city[3][2] + city[2][1] 

Мой вопрос: как я могу сделать вложенный цикл for для этих уравнений? Я мог видеть, что существует шаблон, по которому «индекс столбца» должен переходить к следующему «индексу строки» и так далее.

Answer 1

Вы ищете перестановки всех городов, в которых установлен первый город.Если число городов фиксировано, вы можете записать, что вложенное меню for зацикливается, но это быстро становится громоздким.

Вместо этого рекурсивно переставляйте массив:

• Создайте массивpath порядка посещения городов;начать с {0, ..., N - 1}.
• Выберите начальный индекс.Если вам нужны все возможные начальные точки, выберите 0. Здесь первый город фиксирован, поэтому начните с индекса 1, поскольку path[1] - это первая запись, которая должна измениться.
• Вызовите функцию перестановки:
  • Теперь, если есть еще города, которые нужно переставить, поменяйте каждый из них по очереди на следующую позицию, вызовите функцию перестановки со следующим индексом, а затем поменяйте местами город назад.Во время повторения следите за текущим расстоянием.
  • Если городов больше нет, вы достигли конца списка.Напечатайте путь и расстояние или все, что вы хотите сделать, и больше ничего не делайте.

Вот как это может выглядеть в коде:

#include <stdlib.h>
#include <stdio.h>

enum {
    N = 4           // number of cities
};

const int city[N][N] = {
    {0, 2, 5, 5},
    {2, 0, 3, 4},
    {5, 3, 0, 6},
    {5, 4, 6, 0},
};

/*
 *      Swap array elements at indices i and j
 */
void swap(int a[], int i, int j)
{
    if (i != j) {
        int swap = a[i]; a[i] = a[j]; a[j] = swap;
    }
}

/*
 *      Permute the subarray of length n, starting at index i
 */
void perm(int path[], int i, int n, int weight)
{
    int j;

    if (i == n) {                                   // path is exhausted:
        for (j = 0; j < n; j++) {                   // print path and distance
            printf("%c ", 'A' + path[j]);
        }

        printf("-> %d\n", weight);
    } else {                                        // more cities to visit:
        for (j = i; j < n; j++) {                   // pick each of them as ...
            int w = 0;                              // ... destination

            if (i > 0) {                            // determine distance ...
                w = city[path[i - 1]][path[j]];     // ... from prev. city,
            }                                       // ... if any

            swap(path, i, j);                       // swap city in;
            perm(path, i + 1, n, weight + w);       // recurse;
            swap(path, i, j);                       // swap city back
        }
    }
}

int main()
{
    int path[N];
    int i;

    for (i = 0; i < N; i++) path[i] = i;            // initial path

    perm(path, 1, N, 0);

    return 0;
}