Как обойти максимальное количество ребер неориентированного взвешенного графа?

Question

[MonnWhiteborn]

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

UPD. Я пока думаю, что надо отталкиваться от наименьшего расстояния. До тех пор, пока максимальный вес не превышен, искать минимальный путь до вершины (ещё дело в том, что граф большой, а вершины, которые следует обойти, составляют только часть от всех). Немного почитал e-maxx, нашел вот этот алгоритм нахождения кратчайших путей между всеми п..., возможно он мне поможет, но я всё равно пока не знаю как подступиться, с алгоритмами на "вы". И, да, максимальный вес можно немного превысить

UPD. На всякий случай прикладываю файл с матрицей смежности

Comments

[nirvimel]

Похоже, задача NP-полная (сложность экспоненциально зависит от числа вершин).

[Schullz]

В одну и ту же вершину заходить можно несколько раз?
По одному и тому же ребру можно проходить несколько раз?
Какое максимальное количество вершин и рёбер?

[MonnWhiteborn]

Schullz: Да и да, ребер в графе ~200, обойти нужно около сорока

Answer 1

[Станислав Макаров]

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

Если я ничего не путаю но ночь глядя, то это задача коммивояжёра. Странно, что до сих пор про неё никто ничего не упомянул.

Задача NP-полная, достаточно быстро (что-то около 60-70 вершин) становится трансвычислительной, для 200 вершин ни о каком полном переборе не может быть и речи. Советую посмотреть метод ветвей и границ.

Comments

[nirvimel]

Странно, что до сих пор про неё никто ничего не упомянул.

Я упомянул про NP-полноту в комментарии.