Каков наиболее эффективный способ нахождения пути через небольшой мировой граф?

https://stackoverflow.com/questions/221311

03-07-2019
|

Вопрос

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

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

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

Спасибо

Я смотрю на ПРОСНУЛАСЬ.Есть ли что-нибудь лучше, чем ACO для решения такого рода проблем?

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

Допустим, что самый быстрый или кратчайший маршрут - это не самый важный маршрут, более важным является следование пути, где взвешенные узлы имеют определенное значение.№ 1.

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

-- если только я не ошибаюсь и не неправильно понял*

Тогда что лучше ACO?

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

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

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

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

Решение

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

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

Перед лицом изменения функции затрат Dijksta требует, чтобы кто-то пересчитал решение.

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

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

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

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

Другие советы

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

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

куда мы хотим перейти от пункта А к пункту С.Первоначально алгоритм поиска пути выберет путь 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

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

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

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

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

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

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

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

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

Алгоритм может быть описан следующим образом

Пусть P будет отправной точкой
Присвоите значения g, h и f P
Добавьте P в открытый список (на данный момент P является единственным узлом в этом списке).
Пусть B - лучший узел из открытого списка (лучшее == наименьшее значение f)
- Если B является конечным узлом -> выйти, вы нашли путь
- Если Открытый список пуст -> завершить, никакого пути не существует
Пусть C - допустимый узел, подключенный к B
- Присвоите g, h и f C
- Проверьте, есть ли C в списке Открытых или закрытых
  - Если да, проверьте, является ли новый путь наиболее эффективным (меньшее значение f)
    - Если это так, обновите путь
  - Еще добавьте C в Открытый список
- Повторите шаг 5 для всех узлов, подключенных к B
Добавить B в закрытый список (мы исследовали всех соседей)
Повторите, начиная с шага 4.

Также взгляните на Википедия для получения подробной информации о реализации.

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

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

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

Будет ли недостаточно обычного Дейкстры?

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

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

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")

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow