Краткое объяснение моего алгоритма:
< ul>
[*]Я представляю окончательную конфигурацию головоломки в виде одномерного массива.
[*]Каждая часть содержит массив со значениями пригодности, заданными для каждой другой части (от них зависит, насколько легко они должны соответствовать друг другу)
[*]Порог определяет, насколько разными могут быть части, чтобы алгоритм по-прежнему считался подходящими
Код: Выделить всё
def solve_image(self, col: int, state: list[Candidate], used_pieces: list[int]) -> list:
threshold = 10
print(f'Used pieces: {used_pieces}')
self.counter = self.counter + 1
# finishing condition
if col > self.cols * self.rows - 1:
print(f'Went over {self.counter} pieces')
return state
if col == 0:
# randomly choose the first piece from all the pieces
for piece in self.image_pieces:
# first convert the piece to a candidate to be able to use it in the algorithm
piece_to_candidate = Candidate(piece, fitness_value=0)
result = self.solve_image(col=col + 1, state=[piece_to_candidate],
used_pieces=[piece_to_candidate.piece.index])
if len(result) > 0:
return result
return []
else:
if col % self.cols == 0:
# the piece is in the beginning of the row and therefore there is no piece before it in the row
# take the first piece of the row before and go through the bottom candidates
# the piece from which the candidates will be taken for the next piece
candidate_piece = state[col - self.cols]
sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.BOTTOM)
possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
for candidate in possible_candidates:
if candidate.piece.index not in set(used_pieces):
new_state = state + [candidate]
new_used = used_pieces + [candidate.piece.index]
result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
if len(result) > 0:
return result
return []
else:
# the piece is somewhere in the image where it always has a piece before it
# the piece from which the candidates will be taken for the next piece
candidate_piece = state[col - 1]
sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.RIGHT)
possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
for candidate in possible_candidates:
if candidate.piece.index not in set(used_pieces):
# check if the piece is in a different row than the first one, if yes, compare more edges
passes_top_edge = True
if col > self.cols:
top_edge = state[col - self.cols]
for edge_candidate in top_edge.piece.get_sorted_candidates(Edge.BOTTOM):
if edge_candidate.fitness_value > threshold:
passes_top_edge = False
break
if edge_candidate.piece.index == candidate.piece.index:
break
passes_top_edge = False
if passes_top_edge:
new_state = state + [candidate]
new_used = used_pieces + [candidate.piece.index]
result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
if len(result) > 0:
return result
return []
Основные операторы if предназначены только для проверки того, где находятся части изображения и, следовательно, какие края необходимо учитывать.
В основном , он просто пытается вписать изображения в массив, используя при этом их значение пригодности, чтобы убедиться, что они соответствуют окружающим его частям.
Похоже, что алгоритм работает довольно хорошо для небольших головоломок, например 6х8. Однако в тот момент, когда я ставлю что-то большее, это начинает длиться вечность. Есть идеи, как оптимизировать этот алгоритм? Не стесняйтесь задавать еще вопросы!
Подробнее здесь: https://stackoverflow.com/questions/787 ... saw-puzzle
