0

Дан граф, N вершин и M ребёр. Допустим, есть множество вершин, которые нужно посетить за минимальное время, а потом вернуться обратно. Это задача коммивояжера, но в классической постановке нужно пройти по всем вершинам, а мне нужны конкретные.
С помощью какого алгоритма найти такой путь?

задан 3 Окт '14 0:06

изменен 3 Окт '14 11:59

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


99●1●7

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

(3 Окт '14 0:14) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

регистрация »

отмечен:

×728

задан
3 Окт '14 0:06

показан
705 раз

обновлен
3 Окт '14 0:14

Связанные вопросы

0 Графы, многоугольники и независимые множества

0 Найдите все графы, в которых каждая пара рёбер имеет общий конец

0 Минимальное количество ребер?

0 Существует ли граф степени вершин которого равны 0, 1, 1, 3, 3, 4 ?

0 Задача на деление с остатком

0 Что такое основание ориентируемого графа?

2 Какое минимальное количество ребер должен иметь простой граф на n вершинах, чтобы он был связным?

0 Сколько имеется неориентированных графов с n вершинами, в которых допускаются петли?

0 Задача на графы

0 Докажите, что есть вершина со степенью 1.

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru