Поиск самой длинной дороги в игре «Поселенцы Катана» алгоритмически - PullRequest
Новая
       10

Поиск самой длинной дороги в игре «Поселенцы Катана» алгоритмически

11 голосов
/ 07 июля 2010

Я пишу клон «Поселенцы Катана» для класса. Одной из дополнительных кредитных функций является автоматическое определение того, у какого игрока самый длинный путь. Я думал об этом, и кажется, что некоторые небольшие изменения в поиске в глубину могут сработать, но у меня возникают проблемы с выяснением, что делать с обнаружением циклов, как справиться с объединением двух исходных дорожных сетей игрока, и несколько других мелочей. Как я мог сделать это алгоритмически?

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

Ответы [ 8 ]

7 голосов
/ 07 июля 2010

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

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

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

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

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

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

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

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

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

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

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

2 голосов
/ 12 февраля 2011

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

  • Извлечь граф из основного графа, используя все ребра игрока, добавив вершины основного графа, соединенные с ребрами
  • Составить список концов(вершины, где степень == 1) и разбивает (вершины, где степень == 3)
  • Добавить маршрут для проверки (возможныйRoute) для каждого конца и для каждых двух ребер + одна найденная комбинация вершин (3, посколькуСтепень 3) на каждом расколе
  • Пройдите каждый маршрут.Можно встретить три вещи: конец, промежуточный или разделение.
  • Конец : завершить возможный маршрут, добавить его в список найденных
  • Промежуточный : проверить, возможно ли соединение с другим фронтом.Если так, добавьте край.Если нет, прервите маршрут и добавьте его в список найденных маршрутов
  • Разделить : для обоих ребер выполните промежуточные действия.Когда оба маршрута соединятся, скопируйте второй маршрут и тоже добавьте его в список.
  • Проверка соединения выполняется двумя способами: посмотрите, существует ли новое ребро в возможном маршруте (без соединения), и спросите новое ребро, может ли оно соединиться, указав в качестве параметров вершину и исходную вершину.,Дорога может соединяться с дорогой, но только если вершина не содержит город / поселение от другого игрока.Дорога может соединяться с кораблем, но только если вершина содержит город или дорогу от игрока, у которого проверяется маршрут.
  • Петли могут существовать.Каждое встреченное ребро добавляется в список, если его там еще нет.Когда все возможные пути проверены, но количество ребер в этом списке меньше, чем общее количество ребер игрока, существует один или несколько циклов.В этом случае любому непроверенному ребру назначается новый возможный маршрут, и он снова проверяется для маршрута.
  • Длина самого длинного маршрута определяется простой итерацией по всем маршрутам.Возвращается первый встреченный маршрут, имеющий равные или более 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();
}
2 голосов
/ 07 июля 2010

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

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

  • Установить известный максимум по умолчанию 0

  • Выбрать стартузел.Пропустите, если у него ноль или несколько подключенных соседей, и найдите все пути игрока, начиная с него в ширину.Подвох: Как только узел был пройден, он «деактивируется» для всех поисков, оставшихся в этом ходу.То есть его больше нельзя обойти.

    Как это можно реализовать?Вот один из возможных алгоритмов в ширину:

    1. Если нет путей от этого начального узла или более одного пути, отметьте его как деактивированный и пропустите.
    2. Сохраняйте очередь путей.
    3. Добавьте в очередь путь, содержащий только начальный тупиковый узел.Деактивируйте этот узел.
    4. Извлеките первый путь из очереди и «взорвите» его, то есть найдите все допустимые пути, которые являются путем + еще один шаг в правильном направлении.По значению «valid» следующий узел должен быть подключен к последнему по дороге, и он также должен быть активирован.
    5. Деактивировать все узлы, к которым был подключен последний шаг.
    6. Если естьне являются действительными «взрывами» предыдущего пути, затем сравните эту длину этого пути с известным максимумом.Если оно больше этого значения, это новый максимум.
    7. Добавить все разнесенные пути, если таковые имеются, обратно в очередь.
    8. Повторять 4-7, пока очередь не станет пустой.

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

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

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

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

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

Рубиновый псевдокод (предполагает функцию get_neighbors для каждого узла) 

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
1 голос
/ 07 июля 2010

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

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

0 голосов
/ 30 ноября 2017

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

longestRoadLengthForPlayer (player: PlayerColors): число {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
}
0 голосов
/ 15 декабря 2015

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

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

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
0 голосов
/ 07 июля 2010

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

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

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

0 голосов
/ 07 июля 2010

Что бы я сделал:

  1. Выберите вершину с дорогой
  2. Выберите не более двух дорог для следования
  3. Следуйте по дороге;вернитесь назад, если он разветвляется, и выберите тот, который был длиннее
  4. Если текущая вершина находится в списке посещений, вернитесь к 3
  5. Добавьте вершину в список посещений, рекурсивно из 3
  6. Если в 3 больше нет дороги, верните длину
  7. Когда вы проследовали не более 2 дорог, сложите их, отметьте длину
  8. Если в дороге было 3 дорогиначальная вершина, возврат к 2.

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

...