Разместите свой проект бесплатно и начните получать предложения от фрилансеров-исполнителей уже спустя минуты после публикации!
2100 ₴

проход всех ребер графа

проект завершен
C#


в графе необходимо обойти все ребра минимум один раз. В вершины и ребра можно ходить несколько раз. Главное обойти все ребра кратчайшим путем (оптимальным). Граф неориентированный. Граф может быть большим (500-1000 вершин), желательно использовать муравьиный алгоритм. На выходе должна быть последовательность вершин обхода 

image

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



Обновление #1 от 5 августа в 20:00
На выходе должна быть последовательность вершин обхода содержащая все ребра графа (обязательно все), по ребрам и вершинам ходить повторно можно

Отзыв заказчика об исполнителе Володимире Соколове

Качество
Профессионализм
Стоимость
Контактность
Сроки

Всё отлично. Задание выполнены быстро и качественно. Знания в графах отличные, сразу понимал что от него требуется. На контакт выходил постоянно, не пропадал. В установленные сроки уложился.

Михаил К. Михаил Козловский | Сейф Сейф

Отзыв фрилансера о заказчике Михаиле Козловском

Оплата
Постановка задачи
Четкость требований
Контактность

Рекомендую к сотрудничеству

Понятное задание, без особых требований, на связи был в оговоренное время, все хорошо

Володимир С. Володимир Соколов | Сейф Сейф



  1. 2 дняскрыта
    Андрей Каспришин
     478   5   1

    Сделаю. Скайп kasper0507
    Сделаю. Скайп kasper0507
    Сделаю. Скайп kasper0507
    Сделаю. Скайп kasper0507

    Украина Львов | 5 августа в 20:16 |
  2.  1694 
    11   71   2

    7 днейскрытаПобедившая ставка

    добрый день, готов реализовать на C#,
    муравьиный алгоритм не даст минимального решения, какие критерии выполнения? адекватное время или минимальный результат?

    Украина Львов | 5 августа в 21:24 |
  3. 4 дняскрыта
    Роберт Талабишка
     237   1   0

    Выполню без проблем на C# или java, подберу максимально оптимальный алгоритм
    Опишите подробнее, как должен задаваться граф и в каком виде выводится результат

    Украина Одесса | 5 августа в 14:37 |
  4. 3 дняскрыта
    Герман Бернадский
     178   2   0

    День добрый, готов выполнить Ваш заказ обожаю алгоритмы на графах. Выполню на C# или С++ / Python.

    Россия Владивосток | 5 августа в 15:11 |
  5. 7 днейскрыта
    Сергей Петров
     363   3   0

    Здравствуйте. Готов реализовать такой алгоритм. Это задача поиска оптимального пути в графе. В литературе есть ряд разработанных алгоритмов для таких ситуаций, но задача как я понимаю NP полная так что на линейное время относительно количества вершин не расчитывайте.

    Украина Одесса | 5 августа в 16:38 |
  • Какие наработки уже есть? 

  • Михаил Козловский — заказчик проекта
    Пожаловаться | 5 августа в 15:23 |

    нету

  • Это задача поиска оптимального пути в графе. В литературе есть ряд разработанных алгоритмов для таких ситуаций, но задача как я понимаю NP полная так что на линейное время относительно количества вершин не расчитывайте.


    1. задача не на поиск оптимального пути в графе
    2. да, есть целый ряд алгоритмов решающих задачу минимального пути, у всех у них полиномиальное время, не учитывая евристики, которую не применяют к этой задаче
    3. будь это поиск оптимального пути справился бы алгоритм Дейкстры или сразу Флойда-Уоршела, чтоб не размениватся по пустякам, оба они имеют полиномиальную сложность, но да, время не линейное, в зависимости от алгоритма от квадратического до кубического, но никак не NP

    P.s. а здесь и правда задача NP, но она никак не о оптимальном пути в графе

  • Как должен задаваться граф и в каком виде должен выводится результат ?


Заказчик
Проект опубликован
5 августа в 13:52
108 просмотров