• B правой части каждого сообщения есть стрелки ⇧ и ⇩. Не стесняйтесь оценивать ответы. Чтобы автору вопроса закрыть свой тикет, надо выбрать лучший ответ. Просто нажмите значок ✔ в правой части сообщения.

  • 15 апреля стартует «Курс «SQL-injection Master» ©» от команды The Codeby

    За 3 месяца вы пройдете путь от начальных навыков работы с SQL-запросами к базам данных до продвинутых техник. Научитесь находить уязвимости связанные с базами данных, и внедрять произвольный SQL-код в уязвимые приложения.

    На последнюю неделю приходится экзамен, где нужно будет показать свои навыки, взломав ряд уязвимых учебных сайтов, и добыть флаги. Успешно сдавшие экзамен получат сертификат.

    Запись на курс до 25 апреля. Получить промодоступ ...

Задача Коммивояжера С Фиксированным Стартом И Финишем

  • Автор темы nuke4303
  • Дата начала
N

nuke4303

Добрый день. Уже два дня ищу и не могу найти в интернете алгоритм позволяющий решить задачу коммивояжера (гамильтонова пути) с фиксированной точкой старта и финиша. Необходимо обойти все точки графа (все точки графа соединены между собой) начиная со стартовой точки и заканчивая в конечной. Все что есть в интернете будь то генетические алгоритмы, муравьиные или классические - либо вычисляют старт и финиш сами, либо фиксируют только старт. Подскажите название алгоритма который бы помог решить данную задачу.
 
Сортировать по дате Сортировать по голосам
R

rrrFer

2 раза по одной дуге ходить можно?

Зачем искать алгоритм, когда можно составить самому?
 
За 0 Против
N

nuke4303

Ходить то можно, но будет ли это оптимальный путь....
Придумать тоже можно, но это будет перебор...который для 20-30 вершин будет пол дня наверно все комбинации проверять..
 
За 0 Против
I

ixoyz

nuke4303 сказал(а):
Ходить то можно, но будет ли это оптимальный путь....
Нажмите, чтобы раскрыть...
А оптимальный путь обязателен? Если нет и можно по одной дуге несколько раз ходить, можно просто сделать обход графа в глубину (или взять готовый алгоритм задачи коммивояжера с фиксированым стартом) и в конец маршрута добавить путь до заданной конечной точки (взять из того же обхода графа). Решение конечно не оптимальное, но зато просто реализуется и задачу решает.
 
За 0 Против
A

asSerega

Зачем искать алгоритм, когда можно составить самому?
Нажмите, чтобы раскрыть...
Ну-ну. Судя по твоему вопросу у тебя это получится ;)

nuke4303, если длины ребер заданы однозначно попробуй поискать метод Кларка-Райта (это математический точный метод, прогу составить просто). Если длина ребер может изменятся, попробуй метод муравьиных колоний (он приближенный). Если сам не справишься, готов сделать за вознаграждение. Пиши algoritmer@yandex.ru
 
За 0 Против
Для ответа нужно войти/зарегистрироваться
Мы в соцсетях:

Обучение наступательной кибербезопасности в игровой форме. Начать игру!

Верх Низ