Я ищу алгоритм, который мог бы найти случайный цикл в графе от узла, в то время как этот цикл пересекает другие узлы (область). Например, из зеленой звезды слева от изображения обнаруживается случайный цикл, который идет вокруг узлов красной звезды.алгоритм, который мог бы найти случайный цикл в графе
Учитывая, что вы ищете путь, который является «случайным», но все еще достаточно близко к минимальному периметру вокруг «красной звезды», вы можете попробовать это:
Во-первых, нам нужны выбрать направление, в котором мы идем. Решим по часовой стрелке, и мы начнем в точке S.
Во-вторых, рассчитать кратчайший путь вокруг красной звезды, включая точку S. Здесь я не буду вдаваться в подробности (например, если он вогнутый), так как это другой вопрос. Также обратите внимание, что принятие решения по S уже отнимает от случайности алгоритма.
При выборе пути держите 3 параметра (forward, left, right), которые представляют вес при случайном выборе следующего хода. Разница в результатах будет в значительной степени определяться обработкой этих параметров. Вы всегда можете держать вес равным, и тогда вы, возможно, никогда не вернетесь к начальной точке, и даже если вы это сделаете, вы не знаете, что красная звезда внутри.
Чтобы исправить это, проверьте положение с минимальным путем, рассчитанным ранее.
Если вы на нем, то right = 0. Кроме того, направления, уходящие от минимального пути, могут получить все меньше и меньше шансов, что вы от него.
Надеюсь, это было полезно.
В вашем текущем местоположении выберите следующий возможный узел таким образом, чтобы он был ближе всего к группе или красным узлам и еще не был посещен. Чтобы найти метрику для «ближайших к красным узлам», просто выберите ту, у которой минимальная «сумма расстояния». Например, в вашем первом углу на картинке справа один ближе, чем один. По-моему, вы закончили, когда вернетесь на стартовый узел. – BitTickler
Можно ли предположить, что граф плоский? – slider
Да, мы могли бы предположить, что график плоский. Это также направлено. Это в основном дорожная сеть. – Ark