Как ни странно, я провела лето на старшекурснике по математике, изучая эту проблему, а также придумывая алгоритмы для ее решения. Сначала я прокомментирую другие ответы.
Мартин Б: Правильно определил это как проблему гамильтонова пути. Однако, если график является регулярной сеткой (как вы оба обсуждали в комментариях), то гамильтонов путь может быть найден тривиально (например, в порядке возрастания строки).
agnorest: Правильно говорилось о проблеме гамильтонова пути в классе трудных задач. agnorest также ссылается на возможность использования структуры графа, что достаточно забавно, в случае регулярной сетки тривиально.
Теперь я продолжу обсуждение, подробно остановившись на том, что, на мой взгляд, 1007 * вы пытаетесь достичь. Как вы упомянули в комментариях, тривиально найти определенные классы «заполняющих пространство» непересекающихся «блужданий» на регулярной решетке / сетке. Тем не менее, кажется, что вы не удовлетворены только этим и хотели бы найти алгоритм, который находит «интересные» прогулки, которые покрывают вашу сетку случайным образом. Но прежде чем исследовать эту возможность, я хотел бы отметить, что «непересекающиеся» свойства этих прогулок чрезвычайно важны и что вызывает трудности их перечисления.
На самом деле то, что я изучал во время моей летней практики, называется Самостоятельная прогулка . Удивительно, но изучение SAW (самопожертвование) очень важно для нескольких поддоменов моделирования в физике (и было ключевым элементом Манхэттенского проекта !). Алгоритм, который вы задали в своем вопросе, таков: на самом деле это вариант алгоритма, известного как алгоритм «роста» или алгоритм Розенблута (названный в честь не отличного от маршала Розенблута ). Более подробную информацию как об общей версии этого алгоритма (используемой для оценки статистики по SAW), так и об их отношении к физике можно легко найти в литературе, подобной этой диссертация .
ПАВ в двух измерениях, как известно, трудно изучать. Очень мало теоретических результатов известно о ПАВ в двух измерениях. Как ни странно, в более чем 3 измерениях вы можете сказать, что большинство свойств ПАВ известны теоретически, например, их постоянная роста. Достаточно сказать, что пилы в двух измерениях - очень интересные вещи!
Во время обсуждения этого вопроса о вашей проблеме вы, вероятно, обнаружите, что ваша реализация алгоритма роста довольно часто "обрезается" и не может расширяться, чтобы заполнить всю вашу решетку. В этом случае более уместно рассматривать вашу проблему как задачу о гамильтоновом пути. Мой подход к нахождению интересных гамильтоновых путей состоит в том, чтобы сформулировать задачу как целочисленную линейную программу и добавить фиксированные случайные ребра, которые будут использоваться в ILP. Фиксация случайных ребер дала бы случайность процессу генерации, и часть ILP могла бы эффективно вычислить, возможны ли определенные конфигурации, и если они были бы, вернули бы решение.
Код
Следующий код реализует гамильтонову задачу о пути или цикле для произвольных начальных условий. Он реализует его на обычной двумерной решетке с 4-связностью. Формулировка соответствует стандартному устранению суб-тура ILP Lagrangian. Под-туры лениво исключаются, а это означает, что может потребоваться много итераций.
Вы можете дополнить это, чтобы удовлетворить случайные или другие начальные условия, которые вы считаете "интересными" для вашей проблемы. Если начальные условия недостижимы, он заканчивается досрочно и печатает это.
Этот код зависит от 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