Нахождение самой длинной дороги в Поселенцы игры Catan алгоритмически

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

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

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

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

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

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

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

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

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

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

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

Ruby псевдокод (предполагает функцию 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. Выбираем вершину с дорогой
2. Выбираем не более двух дорог для следования
3. Следуем по дороге; возвращаемся назад, если она разветвляется, и выбираем ту, которая длиннее
4. Если текущая вершина находится в списке посещенных, возвращаемся к 3
5. Добавляем вершину в список посещенных, возвращаемся от 3
6. Если в 3 нет больше дороги, возвращаем длину
7. Когда пройдено не более 2 дорог, складываем их, записываем длину
8. Если в начальной вершине было 3 дороги, возвращаемся к 2.

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

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

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

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

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

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