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

Тема в разделе "C/C++/C#", создана пользователем nuke4303, 23 июл 2014.

  1. nuke4303

    nuke4303 New Member

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

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    2 раза по одной дуге ходить можно?

    Зачем искать алгоритм, когда можно составить самому?
     
  3. nuke4303

    nuke4303 New Member

    Регистрация:
    13 апр 2010
    Сообщения:
    4
    Симпатии:
    0
    Ходить то можно, но будет ли это оптимальный путь....
    Придумать тоже можно, но это будет перебор...который для 20-30 вершин будет пол дня наверно все комбинации проверять..
     
  4. ixoyz

    ixoyz Member

    Регистрация:
    12 май 2012
    Сообщения:
    16
    Симпатии:
    0
    А оптимальный путь обязателен? Если нет и можно по одной дуге несколько раз ходить, можно просто сделать обход графа в глубину (или взять готовый алгоритм задачи коммивояжера с фиксированым стартом) и в конец маршрута добавить путь до заданной конечной точки (взять из того же обхода графа). Решение конечно не оптимальное, но зато просто реализуется и задачу решает.
     
  5. asSerega

    asSerega New Member

    Регистрация:
    17 ноя 2010
    Сообщения:
    3
    Симпатии:
    0
    Ну-ну. Судя по твоему вопросу у тебя это получится ;)

    nuke4303, если длины ребер заданы однозначно попробуй поискать метод Кларка-Райта (это математический точный метод, прогу составить просто). Если длина ребер может изменятся, попробуй метод муравьиных колоний (он приближенный). Если сам не справишься, готов сделать за вознаграждение. Пиши algoritmer@yandex.ru
     
Загрузка...
Похожие Темы - Задача Коммивояжера Фиксированным
  1. ritmix93
    Ответов:
    0
    Просмотров:
    1.541
  2. Янчик
    Ответов:
    0
    Просмотров:
    489
  3. TrishaRay
    Ответов:
    1
    Просмотров:
    783
  4. elzim
    Ответов:
    0
    Просмотров:
    932
  5. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.127

Поделиться этой страницей