Боря программирует

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

Вчера читал статью на викиконспектах итмо про нахождение гамильтонова цикла наименьшей стоимости. В статье приведен псевдокод, а вот мой вольный перевод на С++:

double findCheapest(int i, int mask) {
  if (d[i][mask] != inf) return d[i][mask];

  for (int j = 0; j < N; j++)
    if ((mask & (1 << j)) != 0)
      d[i][mask] =
          std::min(d[i][mask], findCheapest(j, mask - (1 << j)) + w[i][j]);

  return d[i][mask];
}

double start() {
  for (int i = 0; i < N; i++)
    for (int mask = 0; mask < (1 << N); mask++) d[i][mask] = inf;
  d[0][0] = 0;
  return findCheapest(0, (1 << N) - 1);
}

Отгадайте за сколько он работает?

Правильно, за θ(n!). Например, если в графе вообще нет гамильтонова цикла, то все d[i][mask] будет равны inf и каждый раз будут вычисляться заново. А теперь давайте представим, что между всеми вершинами в графе есть ребра. За сколько будет работать теперь?

Неправильно, все еще за θ(n!). Отгадайте почему.

Если вы смотрите на этот код уже 5 минут, и не верите мне, то попробуйте запустить его локально: https://pastebin.com/ZhzYqRmx

www.tgoop.com/bminaiev_blog/44

2.0K viewsedited  Aug 8, 2023 at 13:55

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

Вчера читал статью на викиконспектах итмо про нахождение гамильтонова цикла наименьшей стоимости. В статье приведен псевдокод, а вот мой вольный перевод на С++:

double findCheapest(int i, int mask) {
  if (d[i][mask] != inf) return d[i][mask];

  for (int j = 0; j < N; j++)
    if ((mask & (1 << j)) != 0)
      d[i][mask] =
          std::min(d[i][mask], findCheapest(j, mask - (1 << j)) + w[i][j]);

  return d[i][mask];
}

double start() {
  for (int i = 0; i < N; i++)
    for (int mask = 0; mask < (1 << N); mask++) d[i][mask] = inf;
  d[0][0] = 0;
  return findCheapest(0, (1 << N) - 1);
}

BY Боря программирует