Проблемы с поиском кратчайшего пути между парами отправления и назначения (Netlogo)
Мое исследование посвящено поиску кратчайшего пути между пунктом назначения и пунктом назначения. Оба (источник и пункт назначения) были расположены с использованием расширения ГИС, потому что они были получены с помощью файла формы. Я использовал команду "спросить патчи gis: пересекающийся шейп-файл", чтобы создать человека в источнике и школу в пункте назначения. У меня есть 10 источников, и для каждого у меня есть конкретный пункт назначения. Я заметил, что когда я использую алгоритм Dijsktra, чтобы найти кратчайший путь, для определенного источника пункт назначения - не соответствующая точка, а ближайший пункт назначения. Итак, я сомневаюсь: является ли Dijsktra лучшим алгоритмом для моей проблемы, или мне нужно использовать алгоритм A*? Если алгоритм Dijsktra является лучшим, как я могу сообщить пары происхождения и назначения в коде? Если алгоритм A* является лучшим, как мне построить код в версии 5.0 Netlogo?
1 ответ
Не уверен насчет netlogo, но поскольку ваш вопрос не заключен в кавычки в тегах, я предполагаю, что ориентированный на алгоритм ответ в порядке
Дейкстра и А * похожи; и посмотри, и найди кратчайший путь из одной точки в другую. A* более эффективен, когда у вас есть заранее известное место назначения, так как он оптимально ищет кратчайший возможный путь через эвристику, в то время как dijkstra расширяет больше узлов в вашем графе, выполняя поиск во всех направлениях.
Если вы обнаружите, что Dijkstra возвращает путь к другому месту назначения, отличному от того, который вы ожидаете, вам следует рассмотреть возможность проверки обнаружения пункта назначения: вам следует завершить поиск dijkstra, когда вы найдете ТО, а не ЛЮБОЙ пункт назначения.
A * не страдает так сильно, поскольку эвристика укажет их на правильный пункт назначения, но в особых случаях может найти ту же проблему (то есть кратчайший путь к правильному пункту назначения проходит через другой пункт назначения).
Чтобы быть более точным, мне понадобится некоторый код - псевдокод в порядке - вашего заключения или подробности на графике.