Il prossimo esempio è un problema classico sul partizionamento dei sottoinsiemi in cui il nostro obiettivo è trovare un sottoinsieme di elementi da un grafo non orientato G(V, E) con il numero massimo di elementi tale che non ci siano archi che collegano alcuna coppia dal sottoinsieme dato.
Iniziamo creando classi per lavorare con gli elementi grafici di questo problema. La classe Node sarà utilizzato per rappresentare un vertice (o nodo) dal nostro grafo non orientato. Avrà come attributi:
neighbors: Un elenco di vertici viciniindex: Il suo identificatoreselected: un valore booleano per indicare quando è stato incluso nella soluzione
Ogni volta che a Node istanza viene eliminata dal nostro possibile sottoinsieme di elementi, dobbiamo rimuoverla dall'elenco dei vicini dei suoi vicini, quindi creiamo un metodo delete per renderlo più facile.
La proprietà degree calcola il numero di vicini di un dato nodo e verrà utilizzato come criterio per scegliere l'elemento successivo nel avido approccio.
import copy
from typing import Dict, List, Optional, Tupleclass Node:
neighbors: List('Node')
index: int
selected: bool
def __init__(self, index):
self.index = index
self.neighbors = ()
self.selected = False
def __repr__(self) -> str:
return f"N{self.index}"
def add_neighbor(self, node: 'Node'):
if node not in self.neighbors:
self.neighbors.append(node)
def delete(self):
for n in self.neighbors:
n.neighbors.remove(self)
@property
def degree(self):
return len(self.neighbors)
Ora creiamo il nostro Graph classe. Dovrebbe essere istanziato da un elenco di bordi e da un elenco facoltativo di nodi. Dovrebbe avere un attributo N che è un dizionario dei nodi (o vertici) esistenti.
La proprietà queue dovrebbe restituire un elenco di nodi non ancora selezionati da considerare di includere nella soluzione in ogni passaggio della nostra euristica costruttiva.
Ogni volta che c'è una novità Node l'istanza è selezionata, il metodo select dovrebbe essere chiamato, il che cambia il suo selected attributo e lo chiama delete metodo.
class Graph:N: Dict(int, Node)
def __init__(
self,
edges: List(Tuple(int, int)),
nodes: Optional(List(int)) = None
):
# Start the set
if nodes is None:
self.N = {}
else:
self.N = {i: Node(i) for i in nodes}
# Include all neighbors
for i, j in edges:
self._new_edge(i, j)
@property
def active_nodes(self):
return (node for node in self.N.values() if node.selected)
@property
def inactive_nodes(self):
return (node for node in self.N.values() if not node.selected)
@property
def nodelist(self):
return list(self.N.values())
@property
def queue(self):
return (n for n in self.nodelist if not n.selected)
def _new_node(self, i: int):
if i not in self.N:
self.N(i) = Node(i)
def _new_edge(self, i: int, j: int):
self._new_node(i)
self._new_node(j)
self.N(i).add_neighbor(self.N(j))
self.N(j).add_neighbor(self.N(i))
def select(self, node: Node):
node.selected = True
selected_neighbors = node.neighbors.copy()
for n in selected_neighbors:
other = self.N.pop(n.index)
other.delete()
def deactivate(self):
for n in self.N.values():
n.selected = False
def copy(self):
return copy.deepcopy(self)
Ora creiamo un'astrazione per la nostra euristica costruttiva. Dovrebbe essere istanziato, come il suo corrispondente Graphda un elenco di bordi e un elenco opzionale di nodi. Quando istanziato, il suo attributo graph è definito dal grafico originale dell'istanza del problema.
from abc import ABC, abstractmethod
from mis.graph import Graph, Node
from typing import List, Optional, Tupleclass BaseConstructive(ABC):
graph: Graph
def __init__(
self,
edges: List(Tuple(int, int)),
nodes: Optional(List(int)) = None,
):
self.graph = Graph(edges, nodes)
IL solve Il metodo sarà al centro della nostra procedura di soluzione. Dovrebbe restituire un sottografo di G(V, E) con una soluzione candidata. Quando si utilizza un'istanza della procedura di soluzione come richiamabile, dovrebbe sovrascrivere i suoi nodi selected attributi in base al risultato restituito da solve metodo.
Notare il choice Il metodo qui è un'astrazione che deve ancora essere sovrascritta dalle classi figlie.
class BaseConstructive(ABC):
# Check previous definitionsdef __call__(self, *args, **kwargs):
S = self.solve(*args, **kwargs)
for i, n in S.N.items():
self.graph.N(i).selected = n.selected
@property
def cost(self):
return len(self.graph.active_nodes)
def solve(self, *args, **kwargs) -> Graph:
self.graph.deactivate()
G = self.graph.copy()
for i in range(len(G.N)):
n = self.choice(G)
G.select(n)
if len(G.queue) == 0:
assert len(G.N) == i + 1, "Unexpected behavior in remaining nodes and iterations"
break
return G
@abstractmethod
def choice(self, graph: Graph) -> Node:
pass
Creiamo innanzitutto un algoritmo che scelga casualmente il nodo successivo da includere nella nostra soluzione.
import randomclass RandomChoice(BaseConstructive):
rng: random.Random
def __init__(
self,
edges: List(Tuple(int, int)),
nodes: Optional(List(int)) = None,
seed=None
):
super().__init__(edges, nodes)
self.rng = random.Random(seed)
def choice(self, graph: Graph) -> Node:
return self.rng.choice(graph.queue)
Può già essere utilizzato nella nostra procedura di soluzione e crea soluzioni fattibili insiemi indipendenti massimali (non massimo). Tuttavia, le sue prestazioni variano in base alla sequenza casuale e potremmo essere vulnerabili a scarsi risultati.
Avido e adattivo
In alternativa, ad ogni passaggio, avremmo potuto scegliere il nodo successivo che ha il minor impatto sul “pool” di elementi realizzabili del set di terra. Significherebbe scegliere l'elemento successivo che nel sottografo ha il minor numero di vicini. In altre parole, con il più piccolo degree attributo. Questo è lo stesso approccio adottato da Feo et al. (1994).
Notare il degree dei nostri nodi potrebbe variare man mano che la soluzione parziale cambia e gli elementi vengono rimossi dal sottografo. Può quindi essere definito come un avido e adattivo procedura.
Esistono altre situazioni in cui il costo del contributo di un elemento è influenzato dalle scelte precedenti degli elementi effettuate dall'algoritmo. Chiameremo questi algoritmi avidi adattivi (Resende & Ribeiro, 2016).
Implementiamo quindi un algoritmo che scelga come elemento successivo quello del sottografo più piccolo degree.
class GreedyChoice(BaseConstructive):def choice(self, graph: Graph) -> Node:
return min((n for n in graph.queue), key=lambda x: x.degree)
Sebbene non fornisca prova di ottimalità, l’approccio greedy adattivo può anche essere una strategia interessante per fornire risultati rapidi e di buona qualità a questo problema. Ma prova a eseguire l'approccio casuale più volte… In alcuni casi, potrebbe sovraperformare la strategia avida (almeno in una o poche esecuzioni). Perché allora non implementare un quadro multi-start?
Multipartenze
In questo approccio vengono eseguite più esecuzioni indipendenti e viene mantenuto un registro della soluzione migliore. Alla fine, viene restituita la soluzione migliore.
class MultiRandom(RandomChoice):def solve(self, n_iter: int = 10) -> Graph:
best_sol = None
best_cost = 0
for _ in range(n_iter):
G = super().solve()
if len(G.N) > best_cost:
best_cost = len(G.N)
best_sol = G
return best_sol
Nel mio Repositorio GitHubtroverai un esempio di grafico a 32 nodi in cui il avido e adattivo trovato un sottoinsieme di 5 vertici, ma un quadro casuale con multi-start ha trovato una soluzione con 6. La procedura di soluzione è rappresentata di seguito.
Fonte: towardsdatascience.com
