Denna handledning innehåller en implementering av en sökalgoritm för tillbaka-spårning i Python. Tillbaka-spårning är en rekursiv algoritm som används för att hitta lösningar på problem som innehåller begränsningar (CSP). Jag kommer att försöka lösa ett sodoku och ett schemaläggningsproblem i denna handledning, båda dessa problem har begränsningar men schemaläggningsproblemet har också en tidsvariabel som kan minimeras.
En sökningsalgoritm för tillbaka-spårning försöker tilldela ett värde till en variabel i varje rekursion och algoritmen går tillbaka och testar ett annat värde om det inte finns fler tillåtna värden att tilldela. En ren tillbaka-spårnings-algoritm kan vara ganska långsam, vi kan dock förbättra dess prestanda genom att styra sökningen i rätt riktning.
Vi kan använda Arc-konsistens för att påskynda sökningen, det här innebär att vi bara inkluderar tillåtna värden i domänen för varje variabel och detta innebär att vi har färre värden att välja mellan. Vi kan också välja den mest begränsade variabeln (den variabel med minst antal återstående värden) först, detta innebär att vi hjälper algoritmen att hitta en lösning snabbare.
Sodoku
Den här koden kan användas för att lösa sodoku-pussel av olika storlekar. Jag har inkluderat två algoritmer för tillbaka-spårning i den här koden, backtracking_search_1 och en optimerad version som heter backtracking_search_2. Enklare sodoku-pussel kan lösas inom rimlig tid med hjälp av den första algoritmen, svårare pussel måste dock lösas med den andra mer optimerade versionen.
# Import libraries
import copy
# This class represent a sodoku
class Sodoku():
# Create a new sodoku
def __init__(self, state:[], size:int, sub_column_size:int, sub_row_size:int):
# Set values for instance variables
self.state = state
self.size = size
self.sub_column_size = sub_column_size
self.sub_row_size = sub_row_size
self.domains = {}
# Create domains for numbers by using Arc consistency
# Arc consistency: include only consistent numbers in the domain for each cell
self.update_domains()
# Update domains for cells
def update_domains(self):
# Reset domains
self.domains = {}
# Create an array with numbers
numbers = []
# Loop the state (puzzle or grid)
for y in range(self.size):
for x in range(self.size):
# Check if a cell is empty
if (self.state[y][x] == 0):
# Loop all possible numbers
numbers = []
for number in range(1, self.size + 1):
# Check if the number is consistent
if(self.is_consistent(number, y, x) == True):
numbers.append(number)
# Add numbers to a domain
if(len(numbers) > 0):
self.domains[(y, x)] = numbers
# Check if a number can be put in a cell
def is_consistent(self, number:int, row:int, column:int) -> bool:
# Check a row
for x in range(self.size):
# Return false if the number exists in the row
if self.state[row][x] == number:
return False
# Check a column
for y in range(self.size):
# Return false if the number exists in the column
if self.state[y][column] == number:
return False
# Calculate row start and column start
row_start = (row//self.sub_row_size)*self.sub_row_size
col_start = (column//self.sub_column_size)*self.sub_column_size;
# Check sub matrix
for y in range(row_start, row_start+self.sub_row_size):
for x in range(col_start, col_start+self.sub_column_size):
# Return false if the number exists in the submatrix
if self.state[y][x]== number:
return False
# Return true if no conflicts has been found
return True
# Get the first empty cell (backtracking_search_1)
def get_first_empty_cell(self) -> ():
# Loop the state (puzzle or grid)
for y in range(self.size):
for x in range(self.size):
# Check if the cell is empty
if (self.state[y][x] == 0):
return (y, x)
# Return false
return (None, None)
# Get the most constrained cell (backtracking_search_2)
def get_most_constrained_cell(self) -> ():
# No empty cells left, return None
if(len(self.domains) == 0):
return (None, None)
# Sort domains by value count (we want empty cells with most constraints at the top)
keys = sorted(self.domains, key=lambda k: len(self.domains[k]))
# Return the first key in the dictionary
return keys[0]
# Check if the puzzle is solved
def solved(self) -> bool:
# Loop the state (puzzle or grid)
for y in range(self.size):
for x in range(self.size):
# Check if the cell is empty
if (self.state[y][x] == 0):
return False
# Return true
return True
# Solve the puzzle
def backtracking_search_1(self) -> bool:
# Get the first empty cell
y, x = self.get_first_empty_cell()
# Check if the puzzle is solved
if(y == None or x == None):
return True
# Assign a number
for number in range(1, self.size + 1):
# Check if the number is consistent
if(self.is_consistent(number, y, x)):
# Assign the number
self.state[y][x] = number
# Backtracking
if (self.backtracking_search_1() == True):
return True
# Reset assignment
self.state[y][x] = 0
# No number could be assigned, return false
return False
# Solve the puzzle (optimized version)
def backtracking_search_2(self) -> bool:
# Check if the puzzle is solved
if(self.solved() == True):
return True
# Get a an empty cell
y, x = self.get_most_constrained_cell()
# No good cell was found, retry
if (y == None or x == None):
return False
# Get possible numbers in domain
numbers = copy.deepcopy(self.domains.get((y, x)))
# Assign a number
for number in numbers:
# Check if the number is consistent
if(self.is_consistent(number, y, x)):
# Assign the number
self.state[y][x] = number
# Remove the entire domain
del self.domains[(y, x)]
# Backtracking
if (self.backtracking_search_2() == True):
return True
# Reset assignment
self.state[y][x] = 0
# Update domains
self.update_domains()
# No number could be assigned, return false
return False
# Print the current state
def print_state(self):
for y in range(self.size):
print('| ', end='')
if y != 0 and y % self.sub_row_size == 0:
for j in range(self.size):
print(' - ', end='')
if (j + 1) < self.size and (j + 1) % self.sub_column_size == 0:
print(' + ', end='')
print(' |')
print('| ', end='')
for x in range(self.size):
if x != 0 and x % self.sub_column_size == 0:
print(' | ', end='')
digit = str(self.state[y][x]) if len(str(self.state[y][x])) > 1 else ' ' + str(self.state[y][x])
print('{0} '.format(digit), end='')
print(' |')
# The main entry point for this module
def main():
# Small puzzle 81 (9x9 matrix and 3x3 submatrixes)
#data = '4173698.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
#data = data.strip().replace('.', '0')
#numbers = [int(i) for i in data]
#size = 9 # 9 columns and 9 rows
#sub_column_size = 3 # 3 columns in each submatrix
#sub_row_size = 3 # 3 rows in each submatrix
# Larger puzzle 144 (12x12 matrix and 4x3 submatrixes)
numbers = [7,0,5,0,4,0,0,1,0,0,3,6,9,6,0,0,7,0,0,0,0,1,4,0,0,2,0,0,0,0,3,6,0,0,0,8,0,0,0,10,8,0,0,9,3,0,0,0,11,0,12,1,0,0,0,0,10,0,5,9,0,0,6,0,0,3,12,0,0,0,0,0,0,0,0,0,0,7,4,0,0,9,0,0,2,12,0,7,0,0,0,0,4,10,0,5,0,0,0,11,5,0,0,2,7,0,0,0,1,0,0,0,3,6,0,0,0,0,8,0,0,11,3,0,0,0,0,5,0,0,9,7,10,5,0,0,2,0,0,7,0,3,0,1]
size = 12 # 12 columns and 12 rows
sub_column_size = 4 # 4 columns in each submatrix
sub_row_size = 3 # 3 rows in each submatrix
# Create the initial state
initial_state = []
row = []
counter = 0
# Loop numbers and append to initial state
for number in numbers:
counter += 1
row.append(number)
if(counter >= size):
initial_state.append(row)
row = []
counter = 0
# Create a sodoku
sodoku = Sodoku(initial_state, size, sub_column_size, sub_row_size)
# Print sodoku
print('Puzzle input:')
sodoku.print_state()
# Solve sodoku with optimized version
sodoku.backtracking_search_2()
# Print sodoku
print('\nPuzzle solution:')
sodoku.print_state()
print()
# Tell python to run main method
if __name__ == "__main__": main()Puzzle input:
| 7 0 5 0 | 4 0 0 1 | 0 0 3 6 |
| 9 6 0 0 | 7 0 0 0 | 0 1 4 0 |
| 0 2 0 0 | 0 0 3 6 | 0 0 0 8 |
| - - - - + - - - - + - - - - |
| 0 0 0 10 | 8 0 0 9 | 3 0 0 0 |
| 11 0 12 1 | 0 0 0 0 | 10 0 5 9 |
| 0 0 6 0 | 0 3 12 0 | 0 0 0 0 |
| - - - - + - - - - + - - - - |
| 0 0 0 0 | 0 7 4 0 | 0 9 0 0 |
| 2 12 0 7 | 0 0 0 0 | 4 10 0 5 |
| 0 0 0 11 | 5 0 0 2 | 7 0 0 0 |
| - - - - + - - - - + - - - - |
| 1 0 0 0 | 3 6 0 0 | 0 0 8 0 |
| 0 11 3 0 | 0 0 0 5 | 0 0 9 7 |
| 10 5 0 0 | 2 0 0 7 | 0 3 0 1 |
Puzzle solution:
| 7 10 5 8 | 4 12 2 1 | 9 11 3 6 |
| 9 6 11 3 | 7 10 5 8 | 12 1 4 2 |
| 12 2 1 4 | 9 11 3 6 | 5 7 10 8 |
| - - - - + - - - - + - - - - |
| 4 7 2 10 | 8 5 1 9 | 3 12 6 11 |
| 11 3 12 1 | 6 2 7 4 | 10 8 5 9 |
| 8 9 6 5 | 11 3 12 10 | 1 2 7 4 |
| - - - - + - - - - + - - - - |
| 5 1 10 6 | 12 7 4 11 | 8 9 2 3 |
| 2 12 9 7 | 1 8 6 3 | 4 10 11 5 |
| 3 8 4 11 | 5 9 10 2 | 7 6 1 12 |
| - - - - + - - - - + - - - - |
| 1 4 7 2 | 3 6 9 12 | 11 5 8 10 |
| 6 11 3 12 | 10 1 8 5 | 2 4 9 7 |
| 10 5 8 9 | 2 4 11 7 | 6 3 12 1 |Schemaläggningsproblem
Det här problemet handlar om att schemalägga arbetsuppgifter i olika jobb. Varje uppgift måste utföras i en viss maskin (Job Shop Problem) och varje uppgift måste utföras i en viss ordning, i enlighet med arbetsbeskrivningen. Slutresultatet kommer att bli ett schema med sluttid för varje maskin.
# This class represent a task
class Task:
# Create a new task
def __init__(self, tuple:()):
# Set values for instance variables
self.machine_id, self.processing_time = tuple
# Sort
def __lt__(self, other):
return self.processing_time < other.processing_time
# Print
def __repr__(self):
return ('(Machine: {0}, Time: {1})'.format(self.machine_id, self.processing_time))
# This class represent an assignment
class Assignment:
# Create a new assignment
def __init__(self, job_id:int, task_id:int, start_time:int, end_time:int):
# Set values for instance variables
self.job_id = job_id
self.task_id = task_id
self.start_time = start_time
self.end_time = end_time
# Print
def __repr__(self):
return ('(Job: {0}, Task: {1}, Start: {2}, End: {3})'.format(self.job_id, self.task_id, self.start_time, self.end_time))
# This class represents a schedule
class Schedule:
# Create a new schedule
def __init__(self, jobs:[]):
# Set values for instance variables
self.jobs = jobs
self.tasks = {}
for i in range(len(self.jobs)):
for j in range(len(self.jobs[i])):
self.tasks[(i, j)] = Task(self.jobs[i][j])
self.assignments = {}
# Get the next assignment
def backtracking_search(self) -> bool:
# Prefer tasks with an early end time
best_task_key = None
best_machine_id = None
best_assignment = None
# Loop all tasks
for key, task in self.tasks.items():
# Get task variables
job_id, task_id = key
machine_id = task.machine_id
processing_time = task.processing_time
# Check if the task needs a predecessor, find it if needs it
predecessor = None if task_id > 0 else Assignment(0, 0, 0, 0)
if (task_id > 0):
# Loop assignments
for machine, machine_tasks in self.assignments.items():
# Break out from the loop if a predecessor has been found
if(predecessor != None):
break
# Loop machine tasks
for t in machine_tasks:
# Check if a predecessor exsits
if(t.job_id == job_id and t.task_id == (task_id - 1)):
predecessor = t
break
# Continue if the task needs a predecessor and if it could not be found
if(predecessor == None):
continue
# Get an assignment
assignment = self.assignments.get(machine_id)
# Calculate the end time
end_time = processing_time
if(assignment != None):
end_time += max(predecessor.end_time, assignment[-1].end_time)
else:
end_time += predecessor.end_time
# Check if we should update the best assignment
if(best_assignment == None or end_time < best_assignment.end_time):
best_task_key = key
best_machine_id = machine_id
best_assignment = Assignment(job_id, task_id, end_time - processing_time, end_time)
# Return failure if we can not find an assignment (Problem not solvable)
if(best_assignment == None):
return False
# Add the best assignment
assignment = self.assignments.get(best_machine_id)
if(assignment == None):
self.assignments[best_machine_id] = [best_assignment]
else:
assignment.append(best_assignment)
# Remove the task
del self.tasks[best_task_key]
# Check if we are done
if(len(self.tasks) <= 0):
return True
# Backtrack
self.backtracking_search()
# The main entry point for this module
def main():
# Input data: Task = (machine_id, time)
jobs = [[(0, 3), (1, 2), (2, 2)], # Job 0
[(0, 2), (2, 1), (1, 4)], # Job 1
[(1, 4), (2, 3)]] # Job 2
# Create a schedule
schedule = Schedule(jobs)
# Find a solution
schedule.backtracking_search()
# Print the solution
print('Final solution:')
for key, value in sorted(schedule.assignments.items()):
print(key, value)
print()
# Tell python to run main method
if __name__ == "__main__": main()Final solution:
0 [(Job: 1, Task: 0, Start: 0, End: 2), (Job: 0, Task: 0, Start: 2, End: 5)]
1 [(Job: 2, Task: 0, Start: 0, End: 4), (Job: 0, Task: 1, Start: 5, End: 7), (Job: 1, Task: 2, Start: 7, End: 11)]
2 [(Job: 1, Task: 1, Start: 2, End: 3), (Job: 2, Task: 1, Start: 4, End: 7), (Job: 0, Task: 2, Start: 7, End: 9)]