У меня есть хороший граф (список), содержащий 81 вершины (каждая вершина является экземпляром класса Vertex). Каждая вершина имеет 20 соседей. Каждая вершина имеет ряд возможных значений (в диапазоне от 1 до 9), которые, учитывая некоторые начальные ограничения задачи, будут в среднем 4 или 5. Я реализовал на этом графе простую DFS, которая принимает узел с меньшими возможными значениями, значение foreach создает другой «глубоко скопированный» графа, имеющего только одно из возможных значений, и, наконец, передает «глубокую копию»; граф снова в DFS рекурсивно. Проблема в скорости; cПрофилируя мой код, я обнаружил, что 635 из 641 секунды, которые мой Mac использует для решения этой проблемы, используются copy.deepcopy. Есть ли обходные пути для этой проблемы? Вот мой DFS:

<code>def dfs(graph):
    global initial_time_counter

    if all(len(i.possible_values)==1 for i in graph):
        sys.exit("Done in: %s" % (time.time()-initial_time_counter))

    #find out the non-solved vertex with minimum possible values
    min_vertex=sorted(filter(lambda x: len(x.possible_values)>1,graph),
                      key=lambda x: len(x.possible_values))[0]

    for value in min_vertex.possible_values:

        sorted_graph_copy=sorted(copy.deepcopy(graph), key=lambda x: len(x.possible_values))
        min_vertex_copy=filter(lambda x: len(x.possible_values)>1,sorted_graph_copy)[0]
        sorted_graph_copy.remove(min_vertex_copy)

        if min_vertex_copy.try_value(value): #Can this vertex accept value -> value?
            min_vertex_copy.set_value(value) #Yes, set it.
            sorted_graph_copy.append(min_vertex_copy) #Append it to the graph.
            dfs(sorted_graph_copy) #Run the DFS again.
    return False
</code>

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

[Edit]

Та же проблема, к которой подошли чисто строковые представления вершин, заняла & lt; 0,75 с должно быть решено. Я публикую весь код для справки, если в будущем у кого-то возникнет подобная проблема:

<code>import sys,time

def srange():
    return [[x,y] for x in range(9) for y in range(9)]

def represent_sudoku(sudoku):
    print "\n".join(["|".join([str(elem) for elem in line]) for line in sudoku])

#Hard sudoku
sudoku=[[4, 0, 0, 0, 0, 0, 8, 0, 5], [0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 7, 0], [5, 0, 0, 2, 0, 0, 0, 0, 0], [1, 0, 4, 0, 0, 0, 0, 0, 0]]

represent_sudoku(sudoku)

def get_nbs(x,y,sudoku,also_incomplete=False):
    line_nbs=sum([elem for elem in sudoku[y] if ((elem!=[0] and len(elem)==1) or also_incomplete)],[])

    column_nbs=sum([sudoku[xline][x] for xline in range(9) if ((sudoku[xline][x]!=[0] and len(sudoku[xline][x])==1) or also_incomplete)],[])


    area_nbs=[[j for j in i[(x/3)*3:(x/3)*3+3] if ((j!=[0] and len(j)==1) or also_incomplete)] for i in sudoku[(y/3)*3:(y/3)*3+3]]

    area_nbs=sum(sum(area_nbs,[]),[])    

    if not also_incomplete:
        return list(set(line_nbs+column_nbs+area_nbs))

    return line_nbs+column_nbs+area_nbs

for x,y in srange():
    sudoku[y][x]=[sudoku[y][x]]

def base_cleanup(sudoku):
    while 1:
        something_changed=False
        for x,y in srange():
            if sudoku[y][x]==[0] or len(sudoku[y][x])>1:
                possible_values=range(1,10) if sudoku[y][x]==[0] else sudoku[y][x]
                sudoku[y][x]=list(set(possible_values)-set(get_nbs(x,y,sudoku)))
                if sudoku[y][x]==[]:
                    return False
                something_changed=True if possible_values!=sudoku[y][x] else False
            else:
                sudoku[y][x]=sudoku[y][x]
        if not something_changed:
            break
    return sudoku


def dfs(graph):
    global s

    if graph==False:
        return False

    if all(sum([[len(elem)==1 for elem in line] for line in graph],[])):
        represent_sudoku(graph)
        sys.exit("Done in: %s" % (time.time()-s))

    enumerated_filtered_sudoku=filter(lambda x: len(x[1])>1, enumerate(sum(graph,[])))
    sorted_enumerated_sudoku=sorted(enumerated_filtered_sudoku,key=lambda x: len(x[1]))
    min_vertex=sorted_enumerated_sudoku[0]

    possible_values=[value for value in min_vertex[1]]

    for value in possible_values:        
        graph_copy=[[elem for elem in line] for line in graph]

        y,x=elements_position[min_vertex[0]]

        if not any(value==i for i in get_nbs(x,y,graph_copy)):
            graph_copy[y][x]=[value]
            if base_cleanup(graph_copy)!=False:
                graph_copy=base_cleanup(graph_copy)
                if graph_copy:
                    dfs(graph_copy)

    return False

sudoku = base_cleanup(sudoku)

elements_position = {i:srange()[i] for i in range(81)}
s = time.time()

dfs(sudoku)
</code>