Nano Hash - криптовалюты, майнинг, программирование

Алгоритм кратчайшего пути для карты сетки, которая посещает некоторые узлы

У меня есть карта-сетка, и мне нужно найти кратчайший путь между двумя узлами, но этот путь должен включать несколько узлов.

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

Карта будет примерно такой: map

-Dark brown square at Y18 is the start point
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed)
-White squares are walls (you cannot go through them)
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6)

Я собираюсь использовать Java и сделаю эту карту графом со связями между ними (например, s10 связан с s9, o10 и s11).

Большое спасибо за вашу помощь, и если у вас есть какие-либо вопросы, просто спрашивайте.

graph algorithm shortest-path
09.05.2017

Ответы:


1

Насколько я понимаю, это сочетание двух проблем; у вас есть конечная точка, узел назначения и обязательные промежуточные узлы. Для определения кратчайшего пути вам нужно будет рассчитать расстояние между начальным узлом и всеми промежуточными узлами, всеми парами промежуточных узлов и расстоянием от каждого промежуточного узла до пункта назначения. Если задействованы только неотрицательные веса ребер, это можно сделать с помощью алгоритма Dijkstra.

После расчета всех расстояний оптимальный гамильтоновский путь от начального узла до конечного узла, где используются все промежуточные узлы, необходимо рассчитать. Однако, поскольку эта проблема является NP-сложной, ее, скорее всего, нельзя решить с помощью эффективный алгоритм; может быть осуществим полный перебор всех перестановок.

09.05.2017
  • Прежде всего, спасибо за столь быстрый ответ! Итак, мне нужно получить все расстояния между каждой парой узлов? Это даст мне огромный список расстояний между (0,a) и (0,b), (0,a) и (0,c)...(20,y) и (20,z) и их использовать с ними гамильтоновский путь? 10.05.2017
  • @AlbertoMendiolagoitia : вам нужно получить все расстояния между каждой парой S, где S - это объединение [набора обязательных узлов] с набором из 2 элементов ​ {start_node, ending_node} . ​ ​ ​ ​ ​ В зависимости от того, как количество обязательных узлов соотносится с общим числом узлов, получение расстояний между всеми парами может быть или не быть самым быстрым способом сделайте это, но даже если это так, вы можете отбросить расстояния между узлами, которые не оба находятся в S. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 12.05.2017

    • 2

    Асимптотически, вероятно, это не поможет, поскольку вам все еще нужно решить путь Гамильтона, но для расчета расстояний между каждым узлом вы можете использовать Floyd-Warshall, чтобы немного ускорить процесс.

    09.05.2017
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..