Как ни странно, я провел студенческое лето на математическом факультете, изучая эту проблему, а также придумывая алгоритмы для ее решения. Сначала я прокомментирую другие ответы.
Мартин Б.: Правильно определил, что это проблема гамильтоновых путей. Однако, если граф представляет собой обычную сетку (как вы двое обсуждали в комментариях), то гамильтонов путь может быть найден тривиально (например, извилистый порядок строк).
agnorest: Правильно сказано о том, что проблема гамильтоновых путей относится к классу сложных задач. agnorest также упомянул о возможном использовании структуры графа, что, как ни странно, тривиально в случае регулярной сетки.
Теперь я продолжу обсуждение, уточнив, что, по моему думаю, вы пытаетесь достичь. Как вы упомянули в комментариях, тривиально найти определенные классы «заполняющих пространство» непересекающихся «прогулок» на регулярной решетке/сетке. Однако, похоже, вы не удовлетворены только этим и хотели бы найти алгоритм, который находит «интересные» прогулки, которые случайным образом покрывают вашу сетку. Но прежде чем я исследую эту возможность, я хотел бы указать, что свойство «непересекаемости» этих блужданий чрезвычайно важно и вызывает трудности при их перечислении.
На самом деле, вещь, которую я изучал во время летней стажировки, называется самоизбегающая прогулка. . Удивительно, но изучение SAW (самоизбегающих прогулок) очень важно для нескольких подобластей моделирования в физике (и было ключевым компонентом Манхэттенский проект!) Алгоритм, который вы дали в своем вопросе, на самом деле является вариантом алгоритма, известного как алгоритм "роста" или алгоритм Розенблюта (названный не иначе как Маршал Розенблют). Более подробную информацию как об общей версии этого алгоритма (используемой для оценки статистики ПАВ), так и об их отношении к физике можно легко найти в литературе, подобной этой тезис.
Общеизвестно, что ПАВ в двух измерениях трудно изучать. Известно очень мало теоретических результатов о ПАВ в 2 измерениях. Как ни странно, в измерениях выше 3 можно сказать, что большинство свойств ПАВ известны теоретически, например, их постоянная роста. Достаточно сказать, что ПАВ в 2-х измерениях — это очень интересно!
Доминируя в этом обсуждении, чтобы поговорить о вашей проблеме, вы, вероятно, обнаружите, что ваша реализация алгоритма роста довольно часто «обрезается» и не может расширяться, чтобы заполнить всю вашу решетку. В этом случае более уместно рассматривать вашу проблему как проблему гамильтонового пути. Мой подход к поиску интересных гамильтоновых путей состоял бы в том, чтобы сформулировать задачу как целочисленную линейную программу и добавить фиксированные случайные ребра для использования в ILP. Фиксация случайных ребер придаст случайность процессу генерации, а часть ILP будет эффективно вычислять, допустимы ли определенные конфигурации, и если да, то возвращать решение.
Код
Следующий код реализует гамильтонову задачу о пути или цикле для произвольных начальных условий. Он реализует его на обычной двумерной решетке с 4-связностью. Формулировка следует стандартному лагранжиану ILP с исключением субтуров. Вложенные туры удаляются лениво, что означает, что потенциально может потребоваться много итераций.
Вы можете увеличить это, чтобы удовлетворить случайные или иные начальные условия, которые вы считаете «интересными» для вашей проблемы. Если начальные условия невыполнимы, он завершается досрочно и печатает это.
Этот код зависит от NetworkX и PuLP.
"""
Hamiltonian path formulated as ILP, solved using PuLP, adapted from
https://projects.coin-or.org/PuLP/browser/trunk/examples/Sudoku1.py
Authors: ldog
"""
# Import PuLP modeler functions
from pulp import *
# Solve for Hamiltonian path or cycle
solve_type = 'cycle'
# Define grid size
N = 10
# If solving for path a start and end must be specified
if solve_type == 'path':
start_vertex = (0,0)
end_vertex = (5,5)
# Assuming 4-connectivity (up, down, left, right)
Edges = ["up", "down", "left", "right"]
Sequence = [ i for i in range(N) ]
# The Rows and Cols sequences follow this form, Vals will be which edge is used
Vals = Edges
Rows = Sequence
Cols = Sequence
# The prob variable is created to contain the problem data
prob = LpProblem("Hamiltonian Path Problem",LpMinimize)
# The problem variables are created
choices = LpVariable.dicts("Choice",(Vals,Rows,Cols),0,1,LpInteger)
# The arbitrary objective function is added
prob += 0, "Arbitrary Objective Function"
# A constraint ensuring that exactly two edges per node are used
# (a requirement for the solution to be a walk or path.)
for r in Rows:
for c in Cols:
if solve_type == 'cycle':
prob += lpSum([choices[v][r][c] for v in Vals ]) == 2, ""
elif solve_type == 'path':
if (r,c) == end_vertex or (r,c) == start_vertex:
prob += lpSum([choices[v][r][c] for v in Vals]) == 1, ""
else:
prob += lpSum([choices[v][r][c] for v in Vals]) == 2, ""
# A constraint ensuring that edges between adjacent nodes agree
for r in Rows:
for c in Cols:
#The up direction
if r > 0:
prob += choices["up"][r][c] == choices["down"][r-1][c],""
#The down direction
if r < N-1:
prob += choices["down"][r][c] == choices["up"][r+1][c],""
#The left direction
if c > 0:
prob += choices["left"][r][c] == choices["right"][r][c-1],""
#The right direction
if c < N-1:
prob += choices["right"][r][c] == choices["left"][r][c+1],""
# Ensure boundaries are not used
for c in Cols:
prob += choices["up"][0][c] == 0,""
prob += choices["down"][N-1][c] == 0,""
for r in Rows:
prob += choices["left"][r][0] == 0,""
prob += choices["right"][r][N-1] == 0,""
# Random conditions can be specified to give "interesting" paths or cycles
# that have this condition.
# In the simplest case, just specify one node with fixed edges used.
prob += choices["down"][2][2] == 1,""
prob += choices["up"][2][2] == 1,""
# Keep solving while the smallest cycle is not the whole thing
while True:
# The problem is solved using PuLP's choice of Solver
prob.solve()
# The status of the solution is printed to the screen
status = LpStatus[prob.status]
print "Status:", status
if status == 'Infeasible':
print 'The set of conditions imposed are impossible to solve for. Change the conditions.'
break
import networkx as nx
g = nx.Graph()
g.add_nodes_from([i for i in range(N*N)])
for r in Rows:
for c in Cols:
if value(choices['up'][r][c]) == 1:
nr = r - 1
nc = c
g.add_edge(r*N+c,nr*N+nc)
if value(choices['down'][r][c]) == 1:
nr = r + 1
nc = c
g.add_edge(r*N+c,nr*N+nc)
if value(choices['left'][r][c]) == 1:
nr = r
nc = c - 1
g.add_edge(r*N+c,nr*N+nc)
if value(choices['right'][r][c]) == 1:
nr = r
nc = c + 1
g.add_edge(r*N+c,nr*N+nc)
# Get connected components sorted by length
cc = sorted(nx.connected_components(g), key = len)
# For the shortest, add the remove cycle condition
def ngb(idx,v):
r = idx/N
c = idx%N
if v == 'up':
nr = r - 1
nc = c
if v == 'down':
nr = r + 1
nc = c
if v == 'left':
nr = r
nc = c - 1
if v == 'right':
nr = r
nc = c + 1
return nr*N+c
prob += lpSum([choices[v][idx/N][idx%N] for v in Vals for idx in cc[0] if ngb(idx,v) in cc[0] ]) \
<= 2*(len(cc[0]))-1, ""
# Pretty print the solution
if len(cc[0]) == N*N:
print ''
print '***************************'
print ' This is the final solution'
print '***************************'
for r in Rows:
s = ""
for c in Cols:
if value(choices['up'][r][c]) == 1:
s += " | "
else:
s += " "
print s
s = ""
for c in Cols:
if value(choices['left'][r][c]) == 1:
s += "-"
else:
s += " "
s += "X"
if value(choices['right'][r][c]) == 1:
s += "-"
else:
s += " "
print s
s = ""
for c in Cols:
if value(choices['down'][r][c]) == 1:
s += " | "
else:
s += " "
print s
if len(cc[0]) != N*N:
print 'Press key to continue to next iteration (which eliminates a suboptimal subtour) ...'
elif len(cc[0]) == N*N:
print 'Press key to terminate'
raw_input()
if len(cc[0]) == N*N:
break
person
ldog
schedule
15.11.2017
