Какой самый эффективный способ найти путь по маленькому графу мира?

Question

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

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

(sidenote: здесь можно использовать нейронные сети?)

Спасибо

---

Я смотрю на ACO . Есть ли что-нибудь лучше, чем ACO для такого рода проблем?

---

Справа алгоритм A * находит маршрут с наименьшей стоимостью или самым быстрым без балансировки нагрузки.

Позволяет сказать, что самый быстрый или самый короткий маршрут не является самым важным маршрутом, и что более важно, следует по пути, где взвешенные узлы имеют определенное значение. no1.

NO2. Если при использовании A * трафик на этом маршруте перегружается, то внезапно этот путь становится избыточным. Каким бы классным ни был A *, у него нет определенных функций, таких как ACO, то есть внутренняя балансировка нагрузки.

- если я не ошибаюсь и не понимаю A *

Тогда что бьет ACO?

---

Это действительно похоже на шоу между ACO и A *, было так много позитивных разговоров об A *, что я, конечно, углублюсь в это.

Во-первых, в ответ Давиду; Я могу запустить симуляцию ACO на заднем плане и найти лучший путь, так что да, первоначальная стоимость запуска существует, но, к счастью, запуск не является существенным. Так что я могу позволить себе запускать симуляцию несколько раз. Одна реальная проблема заключается в поиске подключенных узлов источника и назначения. В то время как, кажется, A * сможет сделать это довольно легко. Теперь, что происходит, когда эта сеть становится ужасно большой, как в миллионах узлов. Сможет ли A * легко масштабироваться?

Я буду исследовать A * дальше. Но я оставляю вас с последним вопросом!

Сможет ли A * масштабироваться так же, как и Antnet (ACO)?

Answer 1

Общие примечания

Алгоритм Дейкстры и его оптимизированный вариант A * находят путь с "минимальной" стоимостью через ваш граф. Важными вещами являются: а) правильное определение графика и б) определение соответствующей функции стоимости.

Перед лицом меняющейся функции стоимости Дейкста требует пересчета решения.

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

Оптимизация колонии муравьев , с другой стороны, кажется гораздо более гибким в адаптации к изменяющейся функции стоимости, продолжая итерацию после / пока функция стоимости изменяется.

Эффективность

Это очень сильно зависит от вашей проблемной области. Если у вас хорошая эвристика (см. Раздел Сложность статьи A * ) и редко меняются затраты, тогда полиномиальное время выполнения A * может благоприятствовать повторным пересчетам. ACO, с другой стороны, должен повторяться снова и снова, прежде чем сходиться к приближенному решению. Если изменения стоимости происходят очень часто, продолжение итерации с постоянной скоростью может быть более эффективным, чем обновление A * -решения, поскольку информация сохраняется в состоянии алгоритма. ACO не обещает оптимального решения, хотя , вероятно, имеет более высокие начальные затраты перед переходом на "хорошее" решение. Опять же, это во многом зависит от вашего конкретного домена, графика и функции стоимости, а также от ваших требований к оптимальности.

Answer 2

При использовании A * стоимость пути не обязательно должна быть постоянной, поэтому вы можете начать со следующего графика:

A---1---B---1---C
|               |
\-------1-------/

где мы хотим перейти от A к C. Первоначально алгоритм поиска пути выберет путь A-C, поскольку A-B-C равен 2, тогда как A-C равен 1. Мы можем добавить дополнительный термин к путям:

A---r---B---r---C
|               |
\-------r-------/

с

r(NM) = k(NM) + users(NM) / 10

, где

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

По мере добавления пользователей в систему маршрут AC будет стоить дороже, чем ABC, для двадцати пользователей (1 + 20/10) = 3, ABC равен 2. По мере удаления пользователей из системы маршрут AC станет снова лучший вариант.

Реальная сила A * - это эвристика, которую вы используете для расчета стоимости каждого соединения.

Answer 3

Наиболее часто используемый алгоритм для этой задачи: A * (A Star) , который представляет собой обобщенный алгоритм Дейкстры поиск с добавленной эвристикой - цель эвристики - направить поиск к цели поиска, чтобы типичные поиски заканчивались быстрее.

У этого алгоритма много вариантов, производных версий и улучшений, поиск Google или страница Википедии должны быть хорошей отправной точкой.

Answer 4

Определенно А *. * Либо найдет наилучший возможный путь, либо не найдет путь вообще, если пути не существует. Например. Путь этой лодки был рассчитан с использованием A *

_{(источник: cokeandcode.com )}

Вот интерактивная демонстрация Java 1014 *, с которой можно поиграть. Обратите внимание, что этот алгоритм замедлен из-за снов, поэтому вы видите, как он работает. Без этого замедления он найдет путь менее чем за секунду.

Алгоритм прост, но мощен. Каждый узел имеет 3 значения, g - стоимость до этого узла. h - предполагаемая стоимость от этого узла до цели, а f - сумма обоих (это предположение для полного пути). A * поддерживает два списка, открытый и закрытый. Список Open содержит все узлы, которые еще не исследовались. Закрытый список всех узлов, которые были исследованы. Узел считается исследованным, если алгоритм уже протестировал каждый узел, подключенный к этому узлу (подключенный может означать только горизонтальное и вертикальное положение, но также диагональный, если разрешены диагональные перемещения между узлами).

Алгоритм может быть описан как

1. Пусть P будет отправной точкой
2. Назначить значения g, h и f P
3. Добавьте P в открытый список (на данный момент P - единственный узел в этом списке).
4. Пусть B будет лучшим узлом из списка Open (best == наименьшее значение f)
   • Если B - целевой узел -> выход, вы нашли путь
   • Если открытый список пуст -> выход, пути не существует
5. Пусть C будет действительным узлом, связанным с B
   • Назначьте g, h и f для C
   • Проверьте, находится ли C в открытом или закрытом списке
     • Если да, проверьте, является ли новый путь наиболее эффективным (меньшее значение f)
       • Если это так, обновите путь
     • Иначе добавить C в открытый список
   • Повторите шаг 5 для всех узлов, подключенных к B
6. Добавить B в закрытый список (мы исследовали всех соседей)
7. Повторите с шага 4.

Также ознакомьтесь с Wikipedia для подробностей реализации.

Answer 5

Алгоритм Дейкстры, небольшой пример для вас

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")

Answer 6

Я слышал о реализации NN, чтобы справиться и с этой проблемой. Поэтому, если вы хотите использовать NN, вы в конечном итоге найдете свой путь ;-) но они должны быть хуже по сравнению с «генетическими алгоритмами».

Если проблема в вычислительном / временном расходе, я настоятельно рекомендую использовать генетические алгоритмы. Это именно тот тип проблем, в которых они исключительны.

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

Answer 7

Разве обычного Дейкстры недостаточно?

http://improve.dk/generic-dijkstras-algorithm/