Количество решений в задаче коммивояжёра

[Asker Tasker]

Пусть заданы $N$ городов и коммивояжёру нужно посетить их все и вернуться в исходный город. Я хочу посчитать общее количество возможных решений. Насколько я понимаю, выбираем сначала город, в котором начнётся маршрут - $N$ вариантов, затем один из оставшихся - и так далее, и так далее - получим $N!$.

Но это неверный ответ, так как "чистый" факториал получается только в ассиметричном случае - и то не $N!$, а $(N-1)!$. Почему так? И почему в симметричном случае это число делится пополам?

Заранее благодарен.

[ИСН]

Что Вы считаете (т.е. что называется решением) и что такое симметричный случай?

[Zealint]

В первую очередь обратите внимание на то обстоятельство, что по Вашему алгоритму каждое решение будет посчитано N раз. А после этого приглядитесь, чтобы увидеть, что каждый маршрут в симметричном случае (если я правильно понял, т. е. вес ребра туда и обратно одинаковый), вы посчитаете дважды. И всё.

[ИСН]

(Оффтоп)

Zealint, ну ёлки, ну можно же было попробовать добиться от клиента хотя бы минимальных собственных усилий?!
Как-то так:
- А не считаешь ли ты решением, дорогой товарищ, замкнутый цикл на полном графе без учёта начала и направления?
- Да...

[Профессор Снэйп]

ИСН в сообщении #611329 писал(а):

замкнутый цикл на полном графе без учёта начала и направления?

Если б Вы не сказали, я бы сам не додумался

[Zealint]

ИСН, да Вы правы. Я просто только что с допроса...

[Asker Tasker]

ИСН в сообщении #611232 писал(а):

Что Вы считаете (т.е. что называется решением) и что такое симметричный случай?

"Решение" - любой маршрут, удовлетворяющий условию:
1. каждый город посещён хотя бы один раз;
2. коммивояжёр возвращается в исходный город;
Симметричный случай - когда связи между городами задаются неориентированным графом.
Извиняюсь за то, что я также забыл указать, что все города связаны друг с другом (простейший вариант задачи).

Zealint в сообщении #611314 писал(а):

В первую очередь обратите внимание на то обстоятельство, что по Вашему алгоритму каждое решение будет посчитано $N$ раз.

Насколько я понимаю, это в силу того, что маршрут замкнутый?
То есть, если $n(1)-n(2)-...-n(k-1)-n(k)$ - текущий маршрут (поскольку все рёбра связаны друг с другам концовку $n(k)-n(1)$ я не указываю), то маршруты
$n(2)-...-n(k-1)-n(k)-n(1)$
...
$n(k)-n(1)-n(2)-...-n(k-1)$
совпадают с ним.
Поэтому общее число перестановок $N!$ (каждая из которых соответствует некоторому маршруту) делим на $N$.

Zealint в сообщении #611314 писал(а):

А после этого приглядитесь, чтобы увидеть, что каждый маршрут в симметричном случае (если я правильно понял, т. е. вес ребра туда и обратно одинаковый), вы посчитаете дважды. И всё.

Верно ли следующее обоснование? Поскольку все города связаны друг с другом, то обязательно найдутся два "противоположных" маршрута, проходящих одни и те же рёбра, но в противоположных направлениях.
Если $n(i)$ - $i$-ое ребро текущего маршрута, то соответствующими маршрутами будут следующие:
$n(1)-n(2)-n(3)-n(4)-...-n(k-1)-n(k)$
$n(2)-n(1)-n(k)-n(k-1)-...-n(4)-n(3)$
А поскольку рёбра $n(i)-n(j)$ и $n(j)-n(i)$ равнозначный, то два указанные маршрута соответствуют одному решению, поэтому $(N-1)!$ делим ещё на два. Верно ли такое рассуждение?

[Zealint]

Asker Tasker в сообщении #611562 писал(а):

Насколько я понимаю, это в силу того, что маршрут замкнутый?

Одной замкнутости не достаточно. Бывает, что маршруты замкнуты, а делить на $N$ всё равно не нужно (в похожих задачах). Например, представьте, будто в задаче Вам важно, начинать с первого города или со второго (от этого, например, зарплата коммивояжёра будет разной, можно придумать такие условия).

Цитата:

Верно ли следующее обоснование? Поскольку все города связаны друг с другом, то обязательно найдутся два "противоположных" маршрута, проходящих одни и те же рёбра, но в противоположных направлениях.

А если не все города связаны? Значить "противоположных" маршрутов нет?

Цитата:

Если $n(i)$ - $i$-ое ребро текущего маршрута, то соответствующими маршрутами будут следующие:
$n(1)-n(2)-n(3)-n(4)-...-n(k-1)-n(k)$
$n(2)-n(1)-n(k)-n(k-1)-...-n(4)-n(3)$
А поскольку рёбра $n(i)-n(j)$ и $n(j)-n(i)$ равнозначный, то два указанные маршрута соответствуют одному решению, поэтому $(N-1)!$ делим ещё на два. Верно ли такое рассуждение?

Ну можно и так сказать, но больно коряво, как-то по-гуманитарному. Вы слишком много выдумываете своих слов: "противоположные маршруты", "соответствующие маршруты", "равнозначные рёбра". Кроме того, если у Вас "два маршрута соответствуют решению", а решение - это любой маршрут, то вообще чушь получается.

[Asker Tasker]

Asker Tasker в сообщении #611562 писал(а):

Если $n(i)$ - $i$-ое ребро текущего маршрута, то соответствующими маршрутами будут следующие:

Извиняюсь, я имел в виду "вершина", а не "ребро".

Zealint в сообщении #611601 писал(а):

Одной замкнутости не достаточно.

Zealint в сообщении #611601 писал(а):

А если не все города связаны?

Я исхожу из поставленного условия - "все города связаны друг с другом". Если есть несвязанные, то... Даже не знаю. Может ведь так оказаться, что формула вообще станет неприменимой. Если, например, дано $N$ городов и они связаны последовательно друг с другом, причём $N$-ый связан с первым - тогда решение единственное и никаких факториалов. А в случае, когда все города связаны, замкнутость маршрута (насколько я понимаю) как раз позволяет делить на $N$.

Zealint в сообщении #611601 писал(а):

Ну можно и так сказать, но больно коряво, как-то по-гуманитарному.

Допустим, что я и есть гумманитарий.
Уже без допущений утверждаю, что с терминами у меня тяжко. Я хотел сказать, что "маршрутов" может быть несколько, соответствующих одному "решению": например, для случая трёх городов $(0, 1, 2)$ имеем шесть возможных маршрутов:
$0-1-2-0$
$0-2-1-0$
$1-0-2-1$
$1-2-0-1$
$2-0-1-2$
$2-1-0-2$
Но решение всего одно (это видно даже из картинки, без каких-либо вычислений).

Zealint в сообщении #611601 писал(а):

"равнозначные рёбра"

Если есть рёбра $n(1)-n(2)$ и $n(2)-n(1)$, имеющие одинаковый вес, то как их называть? Ведь вес у них может быть и разный, и это существенное влияет на поставленную задачу. Наверняка есть соответствующий термин - вот только я его, к сожалению, не знаю.

[Zealint]

Цитата:

А в случае, когда все города связаны, замкнутость маршрута (насколько я понимаю) как раз позволяет делить на $N$.

Не только замкнутость позволяет делить на $N$. А ещё тот факт, что по условию Вам всё равно, с какого города начинать движение по любому маршруту. Поэтому удобно в качестве первого города всегда брать номер один. Поэтому второй город выбирается $N-1$ способом и т. д. Получается $(N-1)!$.

В целом Вы всё правильно делаете, но просто говорю, что коряво, я бы не засчитал ответ на экзамене.

Цитата:

Я хотел сказать, что "маршрутов" может быть несколько, соответствующих одному "решению"

Дайте сначала правильные определения маршруту и решению, потом можно будет обсуждать. У Вас сейчас решение - это маршрут. А тогда получается, что цитируемая фраза выглядит так: "маршрутов может быть несколько, соответствующих одному маршруту". Это ерунда.

[Asker Tasker]

Как хорошо, что экзамен мне по этому сдавать не нужно)
Насколько я знаком с терминами теории графов, вот точное определение "решения":

ИСН в сообщении #611329 писал(а):

цикл на полном графе без учёта начала и направления?

"Маршрут" в таком случае - произвольный цикл на полном графе (соответственно с учётом начала и направления). В таком виде действительно несколько маршрутов могут соответствовать одному решению и словесного бардака вроде поменьше, чем у меня было.

[Zealint]

Определения могут быть какими угодно, лишь бы они согласовывались. Разные авторы учебников дают разные определения одному и тому же. Главное разобраться в задаче, что Вы и сделали.

[Asker Tasker]

Спасибо за помощь!