Здравствуйте, задача у меня следующая
Имеется N пунктов и имеются пути между ними, другими словами ориентированный граф каждому ребру которого соответствует некий вес, не отрицательный.
Имеется отправной пункт (или вершина) A и множество конечных пунктов (вершин) B = {B1, B2, ..., Bk}

Задача заключается в следующем:
Найти кратчайший путь начиная с пункта (вершины) A до какого-либо одного пункта (вершины) из множества B, но при этом необходимо пройти как минимум M < N (в моем случае M = 4) любых пунктов (вершин) отличных от A и B.
То есть нужно подобрать такие M пунктов из всего множества чтобы пройдя от А через эти пункты до B у меня был кратчайший путь. Или хотя бы какой нибудь более менее оптимальный путь (нужно решить быстро задачу — полный перебор нельзя применить)

Имеются ли алгоритмы для подобных задач, если нет то как можно ее свести к стандартной задаче о коммивояжере?
Спасибо

Обычный поиск + штрафы на пути из A и B. длиной меньше 4

Здравствуйте, tsaple, Вы писали:

T>Имеются ли алгоритмы для подобных задач, если нет то как можно ее свести к стандартной задаче о коммивояжере?
T>Спасибо

1. убрать dest из графа
2. на полученном графе сделать M шагов Дейкстры
3. добавить обратно вершину dest, очистить волну поиска
4. стартовать Дейкстру из последней волны

правда может получится так что некоторые вершины мы пройдем дважды.

Здравствуйте, tsaple, Вы писали:

T>Найти кратчайший путь начиная с пункта (вершины) A до какого-либо одного пункта (вершины) из множества B, но при этом необходимо пройти как минимум M < N (в моем случае M = 4) любых пунктов (вершин) отличных от A и B.

Дважды одну и те же вершину можно посещать? Как в этом случае считать M: +2 (за каждое посещение вершины) или +1 (за вершину) ?

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, tsaple, Вы писали:

T>>Найти кратчайший путь начиная с пункта (вершины) A до какого-либо одного пункта (вершины) из множества B, но при этом необходимо пройти как минимум M < N (в моем случае M = 4) любых пунктов (вершин) отличных от A и B.

Б>Дважды одну и те же вершину можно посещать? Как в этом случае считать M: +2 (за каждое посещение вершины) или +1 (за вершину) ?

За одно посещение вершины +1, второй раз в принципе можно посетить, но тогда ничего не засчитывается, при этом должно быть все оптимально. То есть +1 за вершину.

Здравствуйте, minorlogic, Вы писали:

M>Обычный поиск + штрафы на пути из A и B. длиной меньше 4

А можно по подробнее касательно штрафов, пожалуйста? Что это за штрафы и какой к примеру поиск использовать можно?

Здравствуйте, tsaple, Вы писали:

T>Здравствуйте, задача у меня следующая
T>Имеется N пунктов и имеются пути между ними, другими словами ориентированный граф каждому ребру которого соответствует некий вес, не отрицательный.
T>Имеется отправной пункт (или вершина) A и множество конечных пунктов (вершин) B = {B1, B2, ..., Bk}

Для точного решения без перебора не обойтись.

Разбиваем путь на две части. Первая часть — путь от вершины А до некоторой вершины V, при этом путь должен содержать равно M различных вершин. Вторая часть пути — от V до B, эта часть пути может содержать любые вершины в любом количестве (или вообще не включать дополнительные вершины), лишь бы этот участок пути был минимальным.

Для формирования первой части пути придется перебрать все пути определенной глубины (чтобы в нем было равно M вершин). Возможен ли такой перебор?
Для формирования второй части — достаточно заранее найти минимальные расстояния между всеми вершинами графа (такие алгоритмы есть).

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, tsaple, Вы писали:

T>>Здравствуйте, задача у меня следующая
T>>Имеется N пунктов и имеются пути между ними, другими словами ориентированный граф каждому ребру которого соответствует некий вес, не отрицательный.
T>>Имеется отправной пункт (или вершина) A и множество конечных пунктов (вершин) B = {B1, B2, ..., Bk}

Б>Для точного решения без перебора не обойтись.

Б>Разбиваем путь на две части. Первая часть — путь от вершины А до некоторой вершины V, при этом путь должен содержать равно M различных вершин. Вторая часть пути — от V до B, эта часть пути может содержать любые вершины в любом количестве (или вообще не включать дополнительные вершины), лишь бы этот участок пути был минимальным.

Б>Для формирования первой части пути придется перебрать все пути определенной глубины (чтобы в нем было равно M вершин). Возможен ли такой перебор?
Б>Для формирования второй части — достаточно заранее найти минимальные расстояния между всеми вершинами графа (такие алгоритмы есть).

насчет второй части — минимальные расстояния между всеми вершинами графа не нужны, достаточно после перебора просто запустить серию алгоритмов Дейкстры из множества B, либо из множества V