Modelowanie wykresu w języku Python

Question

Próbuję rozwiązać problem związany z wykresami w języku Python. Ponieważ jest to problem programowania comeptitive, nie używam żadnych innych pakietów 3rd party.

Problem przedstawia wykres w formie kwadratowej siatki 5 X 5. Zakłada się, że bot znajduje się na pozycji dostarczonej przez użytkownika w sieci. Siatka jest indeksowana pod numerem (0,0) w lewym górnym rogu i (4,4) w prawym dolnym rogu. Każda komórka w siatce jest reprezentowana przez dowolny z 3 następujących znaków. "b" (wartość ascii 98) wskazuje aktualną pozycję bota, "d" (wartość ascii 100) oznacza brudną komórkę, a "-" (wartość ascii 45) wskazuje czystą komórkę w siatce. Na przykład poniżej znajduje się siatka próbka gdzie bot jest 0 0:

b---d 
-d--d 
--dd- 
--d-- 
----d 

Celem jest, aby oczyścić wszystkie komórki w siatce, w minimalnej liczbie kroków. operacja jest definiowana jako zadania, w przypadku gdy i) Bot zmienia to pozycję ii) Bot zmianę stanu komórki (od D do -)

Załóżmy, że początkowo położenie oznaczone jako b nie musi być oczyszczone. BOT może poruszać się w GÓRĘ, DÓŁ, ​​LEWO i PRAWO.

Moje podejście

Czytałem kilka tutoriali na wykresach i postanowił modelować wykres jako macierz sąsiedztwa z dnia 25 x 25 gdzie 0 oznacza brak ścieżek i 1 reprezentujące ścieżki w macierzy (ponieważ możemy poruszać się tylko w 4 kierunkach). Następnie zdecydowałem się zastosować algorytm najkrótszej ścieżki Floyd Warshell do wszystkich par, a następnie podsumować wartości ścieżek. Ale mam wrażenie, że to nie zadziała. Jestem w delimie, że problem jest albo jeden z następujących:

i) Minimalne drzewo opinające (którego nie jestem w stanie zrobić, ponieważ nie jestem w stanie modelować i przechowywać siatki jako wykres).

ii) A * Search (Ponownie dzikie domysły, ale ten sam problem tutaj, nie jestem w stanie poprawnie modelować siatki jako wykresu).

Byłbym wdzięczny, gdybyś mógł zasugerować dobre podejście do takich problemów. Pomocna byłaby także podpowiedź i pseudokodowanie dotyczące różnych form problemów opartych na wykresach (lub odnośnikach do nich). Dziękujemy

Answer 1

Myślę, że zadajesz tutaj dwa pytania.

1. Jak mogę przedstawić ten problem jako wykres w Pythonie?

Gdy robot porusza się, będzie poruszał się od jednego brudnego kwadratu do drugiego, czasami przechodząc przez kilka czystych przestrzeni po drodze. Twoim zadaniem jest ustalenie kolejności odwiedzania brudnych kwadratów.

# Code is untested and may contain typos. :-) 

# A list of the (x, y) coordinates of all of the dirty squares. 
dirty_squares = [(0, 4), (1, 1), etc.] 
n = len(dirty_squares)  

# Everywhere after here, refer to dirty squares by their index 
# into dirty_squares. 

def compute_distance(i, j): 
    return (abs(dirty_squares[i][0] - dirty_squares[j][0]) 
      + abs(dirty_squares[i][1] - dirty_squares[j][1])) 

# distances[i][j] is the cost to move from dirty square i to 
# dirty square j. 
distances = [] 
for i in range(n): 
    distances.append([compute_distance(i, j) for j in range(n)]) 

# The x, y coordinates of where the robot starts. 
start_node = (0, 0) 

# first_move_distances[i] is the cost to move from the robot's 
# start location to dirty square i. 
first_move_distances = [ 
    abs(start_node[0] - dirty_squares[i][0]) 
     + abs(start_node[1] - dirty_squares[i][1])) 
    for i in range(n)] 

# order is a list of the dirty squares. 
def cost(order): 
    if not order: 
    return 0 # Cleaning 0 dirty squares is free. 
    return (first_move_distances[order[0]] 
      + sum(distances[order[i]][order[i+1]] 
       for i in range(len(order)-1))) 

Twoim celem jest znalezienie sposobu uporządkowania listy (zakres (n)), która minimalizuje koszty.

2. Jak znaleźć minimalną liczbę ruchów, aby rozwiązać ten problem?

Jak zauważyli inni, uogólniona forma tego problemu jest trudna do usunięcia (NP-Hard). Masz dwie informacje, które pomagają ograniczyć ten problem, aby go tractable:

1. wykres jest siatka.
2. Istnieje maksymalnie 24 zabrudzonych kwadratów.

Podoba mi się Twój instynkt do używania A * tutaj. Często jest to dobre rozwiązanie dla rozwiązywania problemów z minimalną liczbą ruchów. Jednak A * wymaga dużej ilości kodu. Myślę, że lepiej byłoby wybrać podejście "Odgałęzienie i zbrodnię" (czasami nazywane Oddział-i-Prune), które powinno być prawie tak samo wydajne, ale znacznie łatwiejsze do wdrożenia.

Chodzi o to, aby rozpocząć wyliczanie wszystkich możliwych rozwiązań przy użyciu depth-first-search tak:

# Each list represents a sequence of dirty nodes. 
    [] 
    [1] 
    [1, 2] 
    [1, 2, 3] 
    [1, 3] 
    [1, 3, 2] 
    [2] 
    [2, 1] 
    [2, 1, 3] 

Za każdym razem masz zamiar recurse do oddziału, sprawdź, czy jest to oddział droższe niż najtańsze rozwiązanie znalezione do tej pory. Jeśli tak, możesz pominąć cały oddział.

Jeśli to nie jest wystarczająco wydajne, dodaj funkcję, aby obliczyć dolną granicę pozostałego kosztu. Następnie, jeśli koszt ([2]) + niższy_złączenie (zestaw ([1, 3])) jest droższy niż najtańsze znalezione rozwiązanie, można pominąć cały oddział. Im ściślejsza jest granica dolna(), tym więcej gałęzi możesz pominąć.

Answer 2

Problem można z pewnością zapisać jako wykres. Koszt między węzłami (zabrudzonymi komórkami) wynosi Manhattan distance. Zignoruj ​​koszt czyszczenia komórek, ponieważ całkowity koszt będzie taki sam, bez względu na to, jaką ścieżkę podjąłeś.

Answer 3

Załóżmy, że V={v|v=b or v=d}, i uzyskaj pełny połączony wykres G(V,E). Możesz obliczyć koszt każdej krawędzi w E ze złożonością czasową O(n^2). Następnie problem staje się dokładnie taki sam jak: Rozpocznij od określonego wierzchołka i znajdź najkrótszą ścieżkę G, która obejmuje V.

Nazywamy to Traveling Salesman Problem(TSP) od 1832.

Answer 4

Ten problem wygląda mi problemu Minimum Rectilinear Steiner Tree. Niestety, problem jest NP trudny, więc jeśli mam rację, musisz wymyślić przybliżenie (minimalne drzewo oparcia oparte na odległości na Manhattanie).