Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Поиск Гамильтонова цикла

Необходимо найти цикл, проходящий по всем вершинам графа ровно по одному разу

Задача о поиске Гамильтонова цикла является NP-полной поэтому используем полный перебор.
Асимптотика O(N*N!).

Листинг C++

bool hamilton (vector < vector < int > > &D, vector < int > &p)
{
    int i, j;
    int n = D.size ();
    for (i = 0; i < n; p.push_back (i), ++ i);

    // полный перебор всех цепочек длины n
    do
    {
        for (i = 0; i < n && D[p[i]][p[(i + 1) % n]] != 0; ++ i);
        if (i >= n) return 1;
    }
    while (next_permutation (p.begin (), p.end ()));

    return 0;
}

01.06.2007, 14:53