Алгоритмически поиск самой длинной дороги в поселенцах Катана

Ответ 1

Это должен быть довольно простой алгоритм для реализации.

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

• Выберите произвольный сегмент дороги, добавьте его в набор и отметьте его
• Отделимся от этого сегмента, т.е. следуйте связанным сегментам в обоих направлениях, которые не отмечены (если они отмечены, мы уже здесь)
• Если найденный сегмент дороги еще не установлен, добавьте его и отметьте его
• Продолжайте движение с новых сегментов, пока вы не сможете найти больше немаркированных сегментов, которые подключены к тем, которые в настоящее время находятся в наборе
• Если оставшиеся сегменты не отмечены, они являются частью нового набора, выберите случайный и начните с 1 с другого набора

Примечание. Согласно официальному Правилам Catan, дорога может быть нарушена, если другая игра построит расчет на соединение между двумя сегментами. Вам нужно обнаружить это, а не разветвляться через поселение.

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

Это дает вам один или несколько наборов, каждый из которых содержит один или несколько дорожных сегментов.

Хорошо, для каждого набора сделайте следующее:

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

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

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

Сделайте это для всех наборов, и у вас должна быть самая длинная дорога.

Ответ 2

Я бы предложил поиск по ширине.

Для каждого игрока:

• Задайте стандартный максимум 0

• Выберите стартовый node. Пропустите, если у него есть ноль или более одного подключенного соседа, и найдите все пути проигрывателя, начиная с него в ширину в первом порядке. Улов: как только a node пройден, он "деактивирован" для всех поисков, оставшихся в этом направлении. То есть, он больше не может быть пройден.

  Как это можно реализовать? Здесь можно использовать один возможный алгоритм ширины:

  • Если нет путей из этого начального node или более одного пути, отметьте его деактивированным и пропустите его.
  • Сохранять очередь путей.
  • Добавить путь, содержащий только начальный тупик node в очередь. Отключите этот node.
  • Выложите первый путь из очереди и "взорвите" его, то есть найдите все допустимые пути, которые являются шагом + еще один шаг в допустимом направлении. Под "действительным" следующий node должен быть подключен к последнему по дороге, и он также должен быть активирован.
  • Деактивировать все узлы, на которые наступил последний шаг.
  • Если нет действительных "взрывов" предыдущего пути, сравните длину этого пути с известным максимумом. Если это больше, это новый максимум.
  • Добавьте все вложенные пути, если они есть, обратно в очередь.
  • Повторяйте 4-7, пока очередь не будет пустой.

• После этого один раз перейдите к следующему активированному node и запустите процесс заново. Остановитесь, когда все узлы деактивированы.

• Максимум, который у вас сейчас есть, - это самая длинная длина дороги для данного игрока.

Обратите внимание, что это немного неэффективно, но если производительность не имеет значения, тогда это будет работать:)

ВАЖНОЕ ПРИМЕЧАНИЕ, благодаря Cameron MacFarland

• Предположим, что все узлы с городами, которые не принадлежат текущему проигрывателю, автоматически деактивируются всегда.

Псевдокод Ruby (предполагает функцию get_neighbors для каждого node)

def explode n
  exploded = n.get_neighbors             # get all neighbors
  exploded.select! { |i| i.activated? }  # we only want activated ones
  exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones
  return exploded
end

max = 0

nodes.each do |n|                 # for each node n
  next if not n.activated?        # skip if node is deactivated
  if explode(n).empty? or explode(n).size > 1
    n.deactivate                  # deactivate and skip if
    next                          # there are no neighbors or
  end                             # more than one

  paths = [ [n] ]                 # start queue

  until paths.empty?              # do this until the queue is empty

    curr_path = paths.pop         # pop a path from the queue
    exploded = explode(curr_path) # get all of the exploded valid paths

    exploded.each { |i| i.deactivate }  # deactivate all of the exploded valid points

    if exploded.empty?                  # if no exploded paths
      max = [max,curr_path.size].max    # this is the end of the road, so compare its length to
                                        # the max
    else
      exploded.each { |i| paths.unshift(curr_path.clone + i) }  
                                        # otherwise, add the new paths to the queue
    end

  end

end

puts max

Ответ 3

Немного поздно, но все же актуально. Я реализовал его в java, см. здесь. Алгоритм выглядит следующим образом:

• Вывести граф из основного графика, используя все ребра из плеера, добавив вершины главного графика, связанные с ребрами
• Составьте список контуров (вершины, где степень == 1), и расщепляется (вершины, где степень == 3)
• Добавьте маршрут для проверки (possibleRoute) для каждого конца и для каждого двух ребер + найдена одна найденная вершина (3, так как степень 3) в каждом расколе
• Пройдите каждый маршрут. Можно встретить три вещи: конец, промежуточный или раскол.
• Конец: Завершить возможный Route, добавить его в список поиска
• Промежуточный: проверьте, возможно ли подключение к другому краю. Если да, добавьте ребро. Если нет, завершите маршрут и добавьте его в список найденных маршрутов.
• Разделить. Для обоих краев сделайте как промежуточное. Когда оба маршрута соединяются, скопируйте второй маршрут и добавьте его в список.
• Проверка соединения выполняется с использованием двух методов: см., если новый край уже существует в возможном Route (без соединения) и запрашивает новое ребро, если он может подключиться, указав вершину и исходную вершину в качестве параметров. Дорога может соединяться с дорогой, но только если вершина не содержит город/поселение от другого игрока. Дорога может соединяться с судном, но только если вершина держит город или дорогу от игрока, на котором проверяется маршрут.
• Циклы могут существовать. Каждый встреченный край добавляется в список, если он еще не существует. Когда все возможные Routes проверяются, но количество ребер в этом списке меньше, чем общее количество ребер игрока, существует одна или несколько циклов. Если это так, любой неконтролируемый край получает новый возможный Route от него и снова проверяется для маршрута.
• Длина самого длинного маршрута определяется простым повторением всех маршрутов. Возвращается первый маршрут, имеющий равные или более 5 ребер.

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

SidePiece.canConnect(point, to.getSidePiece());

У дороги, корабля, моста реализован интерфейс SidePiece. Дорога имеет реализацию

public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece)
{
    return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null)
            && otherPiece.connectsWithRoad();
}

Ответ 4

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

Возможно, самым простым решением было бы динамическое программирование: сохраните таблицу T [v, l], которая хранит для каждого node v и каждой длины l набор путей, длина которых l и заканчивается на v. Очевидно, что T [v, 1] = {[v]}, и вы можете заполнить T [v, l] для l > 1, собирая все пути из T [w, l-1], где w является соседом v, который еще не содержит v, а затем прикрепление v. Это похоже на решение Justin L., но избегает некоторой дублирующей работы.

Ответ 5

Что я буду делать:

• Выберите вершину с дорогой.
• Выберите не более двух дорог, чтобы следовать
• Следуйте по дороге; backtrack здесь, если он веткится, и выберите то, что было длиннее
• Если текущая вершина находится в посещенном списке, backtrack to 3
• Добавить вершину в список посещений, рекурсия из 3
• Если пути больше нет, верните длину
• Когда вы следуете не более чем на 2 дорогах, добавьте их, отметьте длину
• Если в начальной вершине было 3 дороги, откат до 2.

Извините за пролог-иш терминологию:)

Ответ 6

Вот фрагмент кода, который я использую, чтобы определить самый длинный путь для данного игрока ( "пользователь" ) в моем симуляторе VBA Catan Excel.

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

Private Frays As Dictionary
Private RoadPths As Collection
Public Function GetLongestRoad(g As Board, oUser As User) As Long
    Dim oRoad As Road
    Dim v, w
    Dim fNum As Long
    Dim rCount As Long

    Set Frays = New Dictionary
    Set RoadPths = New Collection

    ' get list of roads that happen to be linked to other roads ("Frays")
    For fNum = 55 To 126
        If g.Roads(fNum).Owner = oUser.Name Then
            For Each v In RoadLinks(g, fNum)
                If g.Roads(v).Owner = oUser.Name Then Frays(fNum) = v
            Next v
        End If
    Next fNum

    ' begin recursion
    For Each v In Frays
        RecurSegmts g, v & ";" & Frays(v)
    Next v

    rCount = 0
    For Each v In RoadPths
        w = Split(v, ";")
        If rCount < UBound(w) Then rCount = UBound(w)
    Next v

    GetLongestRoad = rCount + 1
End Function

Private Sub RecurSegmts(g As Board, Segmts As Variant)
    Dim SegmtArr, NextRoad
    Dim LoopsBack As Boolean
    Dim i As Long

    RoadPths.Add Segmts
    SegmtArr = Split(Segmts, ";")

    For Each NextRoad In RoadLinks(g, CLng(SegmtArr(UBound(SegmtArr))))
        LoopsBack = False
        For i = 0 To UBound(SegmtArr)
            If CLng(NextRoad) = CLng(SegmtArr(i)) Then LoopsBack = True
        Next i

        If LoopsBack = False Then Call RecurSegmts(g, Segmts & ";" & NextRoad)

    Next NextRoad
End Sub

Ответ 7

Вот моя версия, если кому-то это нужно. Написано в Typescript.

longestRoadLengthForPlayer (player: PlayerColors): number {       let longestRoad = 0

    let mainLoop = (currentLongestRoad: number, tileEdge: TileEdge, passedCorners: TileCorner[], passedEdges: TileEdge[]) => {
        if (!(passedEdges.indexOf(tileEdge) > -1) && tileEdge.owner == player) {
            passedEdges.push(tileEdge)
            currentLongestRoad++
            for (let endPoint of tileEdge.hexEdge.endPoints()) {
                let corner = this.getTileCorner(endPoint)!

                if ((corner.owner == player || corner.owner == PlayerColors.None) && !(passedCorners.indexOf(corner) > -1)) {
                    passedCorners.push(corner)
                    for (let hexEdge of corner.hexCorner.touchingEdges()) {
                        let edge = this.getTileEdge(hexEdge)
                        if (edge != undefined && edge != tileEdge) {
                            mainLoop(currentLongestRoad, edge, passedCorners, passedEdges)
                        }
                    }
                } else {
                    checkIfLongestRoad(currentLongestRoad)
                }
            }
        } else {
            checkIfLongestRoad(currentLongestRoad)
        }
    }

    for (let tileEdge of this.tileEdges) {
        mainLoop(0, tileEdge, [], [])
    }

    function checkIfLongestRoad(roadLength: number) {
        if (roadLength > longestRoad) {
            longestRoad = roadLength
        }
    }

    return longestRoad
}

Ответ 8

Вы можете использовать Dijkstra и просто изменить условия, чтобы выбрать самый длинный путь.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Он эффективен, но не всегда найдет путь, который на самом деле является самым коротким/длинным, хотя он будет работать большую часть времени.