Ищем алгоритм поиска кратчайшего пути

В основном у меня есть граф с 12 узлами (представляющими города) и 13 ребрами (представляющими маршруты).

введите описание изображения здесь

Теперь предположим, что (случайным образом) у меня есть план посещения n узлов, отклоняясь от определенного (A). Итак (having N <= (12-1)), а затем подошли к отправной точке.

То, что я искал, похоже на Traveling Salesman Problem, но с той разницей, что моему продавцу не обязательно посещать все узлы.

Какой алгоритм я ищу?

ИЗМЕНИТЬ

Очевидно, это не будет TSP, потому что TSP говорит, что граф должен быть замкнут, и мы проходим через каждый город (узел) только один раз. В моем случае он может пересечь город более одного раза, если это сделает маршрут короче.

Еще несколько примеров того, что я ищу:

Пример первый:

Depart from: A
Need to visit (B,D,E,L,G,J,K)
Come back to: A

Пример второй:

Depart from: A
Need to visit (B,C,D,G,H,I,J,K)
Come back to: A

Правила:

- Get shortest path
- No specific order
- Can visit one node (city) more than once

Помните, что это для проекта на C, так что это всего лишь предварительное исследование.


c graph graph-algorithm traveling-salesman
person eduardev    schedule 19.11.2013    source источник
comment
Домашнее задание? Покажи нам, что ты сделал?   -  person JoeC    schedule 20.11.2013
comment
Это называется задачей коммивояжера. попробуйте поискать в Google проблема коммивояжера   -  person DwB    schedule 20.11.2013
comment
Просто игнорируйте узлы, которые вам не нужно посещать, и вы все равно столкнетесь с проблемой коммивояжера.   -  person Nir Alfasi    schedule 20.11.2013
comment
OP - Я предполагаю, что любые N узлов приемлемы? Кроме того, 12 узлов и 13 ребер довольно редко, часто может не быть решения или только одно, и в этом случае поиск оптимального решения (цель та же, что и у коммивояжера, - выбрать пути, которые минимизируют стоимость, верно ?) бессмысленно.   -  person jon_darkstar    schedule 20.11.2013
comment
извините, ребята, что нашли время для ответа. Я работаю над проектом C. Все еще на стадии исследования, кодирования еще нет. Просто интересно, как я собираюсь справиться с этой проблемой. И да, N может быть любым числом (сгенерированным случайным образом), по крайней мере, одним узлом для посещения.   -  person eduardev    schedule 20.11.2013

Ответы (2)


arrow_upward
1
arrow_downward

Для этого существует множество алгоритмов. Ключевое слово - поиск пути.

Лучший алгоритм для начала - старый добрый Дейкстра http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Затем для более крупных графиков (которые не являются лабиринтом) вам может потребоваться алгоритм с некоторой эвристикой направления, ускоряющий оценку, как алгоритм A *. http://en.wikipedia.org/wiki/A *

Есть и другие, но самые распространенные.

Обновление из обсуждения:

Судя по нашему обсуждению, я думаю, что подход к решению этой проблемы был бы подходом к рассмотрению всех перестановок «обязательных узлов» B | L | I | D | G | K | J, начиная с A и затем снова переходя к A:

// Prepare a two dimensional array for the permutations
Node permutation[permutationCount][7];

// Fill it with all permutations
...

int cost[permutationCount];

for (int i = 0; i < permutationCount; ++i) {
    cost[i] =   dijkstraCost(nodeA,             permutation[i][0]) 
              + dijkstraCost(permutation[i][0], permutation[i][1])
              + dijkstraCost(permutation[i][1], permutation[i][2])
              + dijkstraCost(permutation[i][2], permutation[i][3])
              + dijkstraCost(permutation[i][3], permutation[i][4])
              + dijkstraCost(permutation[i][4], permutation[i][5])
              + dijkstraCost(permutation[i][5], permutation[i][6])
              + dijkstraCost(permutation[i][6], nodeA);
}

// Now Evaluate lowest cost and you have your shortest path(s)
....

Я думаю, это должно сработать.

person Marcel Blanck    schedule 19.11.2013
comment
И Дейкстра, и A * предназначены для пути с наименьшими затратами, поэтому я не на то, на что я смотрю, или мне что-то здесь не хватает. Это больше похоже на проблему продавца - person eduardev; 20.11.2013
comment
Хорошо, но каковы правила для узлов, которые вам не нужно посещать. Или вы хотите только перейти от K к D, не посещая все узлы. Возможно, я не понимаю здесь вопроса, потому что, как утверждали другие, TSM потребует удалить узлы, чтобы они не посещались. - Я бы сказал: Посетите все узлы - TSM, Посетите все заметки, кроме некоторых указанных - TSM с удалением узлов из сети, Перейти отсюда туда, без необходимости посещать все узлы - поиск пути - person Marcel Blanck; 24.11.2013
comment
Привет. Мне нужно выйти из узла A, посетить заданный набор городов (например, B, L, I, D, G, K, J), а затем вернуться в A. Кратчайший маршрут. Правила: на самом деле нет. Я могу проехать через узел (город) более одного раза, если это сделает мой маршрут короче. Судя по всему, это не TSP, потому что TSP говорит, что пройдите через город ТОЛЬКО один раз. - person eduardev; 25.11.2013
comment
Хорошо, вам нужно посетить узлы B, L, I, D, G, K, J в указанном порядке? Потому что опять же, я бы использовал Дейкстру. В противном случае придумать что-то будет намного сложнее. - Может быть (все еще Дейкстра) начинает с a, вычисления прошли все перестановки B, L, I, D, G, K, J + в прошлом. Оцените стоимость каждого маршрута, а затем выберите один. - person Marcel Blanck; 25.11.2013
comment
Нет порядка, только кратчайший путь ... Я жестко тестирую все перестановки (также известные как грубая сила), но опять же, какой алгоритм для этого? Я также рассказывал о минимальном остовном дереве, а затем о Дейкстре на обратном пути (на каждом конечном узле выбирая самый короткий), но ... - person eduardev; 25.11.2013
comment
Да, алгоритм был бы похож на int permutationcost = dijkstraCost (A, B) + dijkstraCost (B, L) + ... + dijkstraCost (K, J) + dijkstraCost (J, A) = ›делая это для всех перестановок. Был бы мой первый наивный подход. Я не могу придумать что-то другое, кроме dijkstra, потому что он кажется мне идеально подходящим для этого. - person Marcel Blanck; 25.11.2013
comment
Хорошо, проверь мое обновление! Вам нужно только создать заданную сеть узлов и реализовать для нее поиск пути с помощью Дейкстры. Тогда переходите к грубой силе ^^ - person Marcel Blanck; 25.11.2013
comment
Марсель хороший подход, позвольте мне подумать и поработать над этим, и я вернусь к вам, и, вероятно, приму ваш ответ. Спасибо :) - person eduardev; 25.11.2013
comment
позвольте нам продолжить обсуждение в чате - person eduardev; 25.11.2013

arrow_upward
0
arrow_downward

Вы правы, это TSP, но вам нужно слишком уменьшить граф, чтобы он содержал только узлы, которые нужно посетить.

Как уменьшить график оставляем читателю в качестве упражнения ;-)

person Bertil Baron    schedule 20.11.2013
comment
Я полагаю, удаляю из него фактические узлы и складываю вес их ребер. Хммм, а как насчет узлов пересечения !? ... интересно! Тем не менее, это приложение на C, мне сказали, что в какой-то момент математика будет важна;) - person eduardev; 20.11.2013
comment
Пример: если вам не нужно посещать узел I на графике выше, вы удалите этот узел и добавите ребра: H ‹--› L вес 7, L ‹--› J вес 10, J ‹--› H вес 9 - person Bertil Baron; 21.11.2013
comment
Видимо это не ЦП, потому что ЦП говорит, что мы проезжаем через город только один раз. А что касается удаления узла, есть ли алгоритм, который я могу запрограммировать? - person eduardev; 25.11.2013