[ad_1]
Ví dụ tiếp theo là một bài toán cổ điển về phân vùng tập hợp con, trong đó mục tiêu của chúng ta là tìm một tập hợp con các phần tử từ đồ thị vô hướng G(V., E) với số phần tử tối đa sao cho không có cạnh nào nối bất kỳ cặp nào từ tập hợp con đã cho.
Chúng ta hãy bắt đầu bằng việc tạo các lớp để làm việc với các phần tử đồ thị của bài toán này. Lớp Node sẽ được sử dụng để biểu diễn một đỉnh (hoặc nút) từ đồ thị vô hướng của chúng ta. Nó sẽ có các thuộc tính:
neighbors: Danh sách các đỉnh lân cậnindex: Mã định danh của nóchosen: Một boolean để cho biết thời điểm nó được đưa vào giải pháp
Bất cứ khi nào một Node occasion bị xóa khỏi tập hợp con các phần tử khả thi của chúng tôi, chúng tôi phải xóa nó khỏi danh sách các phần tử lân cận của nó, vì vậy chúng tôi tạo một phương thức delete làm cho nó dễ dàng hơn.
Bất động sản diploma tính toán số lượng hàng xóm từ một nút nhất định và sẽ được sử dụng làm tiêu chí để chọn phần tử tiếp theo trong tham tiếp cận.
import copy
from typing import Dict, Record, Optionally available, Tupleclass Node:
neighbors: Record('Node')
index: int
chosen: bool
def __init__(self, index):
self.index = index
self.neighbors = ()
self.chosen = 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.take away(self)
@property
def diploma(self):
return len(self.neighbors)
Bây giờ, chúng ta hãy tạo Graph lớp học. Nó phải được khởi tạo từ danh sách các cạnh và danh sách các nút tùy chọn. Nó phải có một thuộc tính N đó là từ điển của các nút (hoặc đỉnh) hiện có.
Bất động sản queue sẽ trả về danh sách các nút chưa được chọn để chúng tôi xem xét đưa vào giải pháp ở mỗi bước trong quá trình phỏng đoán mang tính xây dựng của chúng tôi.
Bất cứ khi nào mới Node trường hợp được chọn, phương thức choose nên được gọi, điều này sẽ thay đổi nó chosen thuộc tính và gọi nó delete phương pháp.
class Graph:N: Dict(int, Node)
def __init__(
self,
edges: Record(Tuple(int, int)),
nodes: Optionally available(Record(int)) = None
):
# Begin the set
if nodes is None:
self.N = {}
else:
self.N = {i: Node(i) for i in nodes}
# Embody 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.chosen)
@property
def inactive_nodes(self):
return (node for node in self.N.values() if not node.chosen)
@property
def nodelist(self):
return checklist(self.N.values())
@property
def queue(self):
return (n for n in self.nodelist if not n.chosen)
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 choose(self, node: Node):
node.chosen = True
selected_neighbors = node.neighbors.copy()
for n in selected_neighbors:
different = self.N.pop(n.index)
different.delete()
def deactivate(self):
for n in self.N.values():
n.chosen = False
def copy(self):
return copy.deepcopy(self)
Bây giờ, chúng ta hãy tạo một sự trừu tượng hóa cho phương pháp phỏng đoán mang tính xây dựng của mình. Nó nên được khởi tạo, tương ứng với nó Graph, từ danh sách các cạnh và danh sách các nút tùy chọn. Khi được khởi tạo, thuộc tính của nó graph được xác định từ biểu đồ ban đầu của trường hợp vấn đề.
from abc import ABC, abstractmethod
from mis.graph import Graph, Node
from typing import Record, Optionally available, Tupleclass BaseConstructive(ABC):
graph: Graph
def __init__(
self,
edges: Record(Tuple(int, int)),
nodes: Optionally available(Record(int)) = None,
):
self.graph = Graph(edges, nodes)
Các resolve phương pháp này sẽ là cốt lõi của quy trình giải pháp của chúng tôi. Nó sẽ trả về một sơ đồ con của G(V., E) với một giải pháp ứng viên. Khi sử dụng một phiên bản của quy trình giải pháp làm đối tượng có thể gọi được, nó sẽ ghi đè lên các nút của nó’ chosen các thuộc tính dựa trên kết quả được trả về bởi resolve phương pháp.
Chú ý selection phương thức ở đây là một sự trừu tượng hóa chưa bị ghi đè bởi các lớp con.
class BaseConstructive(ABC):
# Verify earlier definitionsdef __call__(self, *args, **kwargs):
S = self.resolve(*args, **kwargs)
for i, n in S.N.gadgets():
self.graph.N(i).chosen = n.chosen
@property
def value(self):
return len(self.graph.active_nodes)
def resolve(self, *args, **kwargs) -> Graph:
self.graph.deactivate()
G = self.graph.copy()
for i in vary(len(G.N)):
n = self.selection(G)
G.choose(n)
if len(G.queue) == 0:
assert len(G.N) == i + 1, "Surprising conduct in remaining nodes and iterations"
break
return G
@abstractmethod
def selection(self, graph: Graph) -> Node:
move
Trước tiên, chúng ta hãy tạo một thuật toán chọn ngẫu nhiên nút tiếp theo để đưa vào giải pháp của mình.
import randomclass RandomChoice(BaseConstructive):
rng: random.Random
def __init__(
self,
edges: Record(Tuple(int, int)),
nodes: Optionally available(Record(int)) = None,
seed=None
):
tremendous().__init__(edges, nodes)
self.rng = random.Random(seed)
def selection(self, graph: Graph) -> Node:
return self.rng.selection(graph.queue)
Nó đã có thể được sử dụng trong quy trình giải pháp của chúng tôi và tạo ra các giải pháp khả thi tập hợp độc lập tối đa (không tối đa). Tuy nhiên, hiệu suất của nó thay đổi tùy theo trình tự ngẫu nhiên và chúng ta có thể dễ gặp phải kết quả kém.
Thích nghi tham lam
Ngoài ra, ở mỗi bước, chúng ta có thể chọn nút tiếp theo có tác động nhỏ nhất đến “nhóm” các phần tử khả thi từ tập hợp cơ sở. Điều đó có nghĩa là chọn phần tử tiếp theo trong đồ thị con có số lượng lân cận nhỏ nhất. Nói cách khác, với giá trị nhỏ nhất diploma thuộc tính. Đây là cách tiếp cận tương tự được áp dụng bởi Feo et al. (1994).
Chú ý diploma các nút của chúng tôi có thể thay đổi khi giải pháp một phần thay đổi và các phần tử bị xóa khỏi biểu đồ con. Do đó, nó có thể được định nghĩa là một tham lam thích ứng thủ tục.
Có những tình huống khác trong đó chi phí đóng góp của một phần tử bị ảnh hưởng bởi các lựa chọn phần tử trước đó do thuật toán thực hiện. Chúng ta sẽ gọi những thuật toán tham lam thích ứng này (Resende & Ribeiro, 2016).
Sau đó, chúng ta hãy triển khai một thuật toán chọn phần tử tiếp theo từ sơ đồ con có giá trị nhỏ nhất diploma.
class GreedyChoice(BaseConstructive):def selection(self, graph: Graph) -> Node:
return min((n for n in graph.queue), key=lambda x: x.diploma)
Mặc dù nó không cung cấp bằng chứng về tính tối ưu, nhưng cách tiếp cận tham lam thích ứng cũng có thể là một chiến lược thú vị để mang lại kết quả nhanh chóng và chất lượng tốt cho vấn đề này. Nhưng hãy thử chạy phương pháp ngẫu nhiên nhiều lần… Trong một số trường hợp, nó có thể hoạt động tốt hơn chiến lược tham lam (ít nhất là trong một hoặc một vài lần chạy). Tại sao không triển khai khuôn khổ đa khởi động?
Nhiều lần khởi động
Trong phương pháp này, nhiều lần chạy độc lập được thực hiện và sổ đăng ký giải pháp tốt nhất được lưu giữ. Cuối cùng, giải pháp tốt nhất được trả lại.
class MultiRandom(RandomChoice):def resolve(self, n_iter: int = 10) -> Graph:
best_sol = None
best_cost = 0
for _ in vary(n_iter):
G = tremendous().resolve()
if len(G.N) > best_cost:
best_cost = len(G.N)
best_sol = G
return best_sol
trong tôi Kho lưu trữ GitHubbạn sẽ tìm thấy một ví dụ về biểu đồ 32 nút trong đó tham lam thích ứng đã tìm thấy một tập hợp con gồm 5 đỉnh, nhưng một khung ngẫu nhiên với nhiều điểm bắt đầu đã tìm ra giải pháp có 6. Quy trình giải pháp được trình bày bên dưới.
[ad_2]
Source link