small-lambda
Senior Member
intuition mình thấy, nhưng giờ muốn chứng minh là nó optimal thì làm ntn?
thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
maskup
Junior Member
Lâu rồi mới đụng vào Kruskal
Python:
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
# step1: use type3 edges as much as possible to connect vertices for both Bob and Alice
# step2: use type1, type2 to connect Alice vertices, Bob vertices respectively
aliceUnions = UnionFind(n + 1)
bobUnions = UnionFind(n + 1)
usedEdges = 0
for _, u, v in filter(lambda edge: edge[0] == 3, edges):
if aliceUnions.find(u) != aliceUnions.find(v):
usedEdges += 1
aliceUnions.union(u, v)
bobUnions.union(u, v)
for edgeType, u, v in filter(lambda edge: edge[0] != 3, edges):
targetUnions = aliceUnions if edgeType == 1 else bobUnions
if targetUnions.find(u) != targetUnions.find(v):
usedEdges += 1
targetUnions.union(u, v)
if not aliceUnions.getUnionCount() == bobUnions.getUnionCount() == 2:
return -1
return len(edges) - usedEdges
class UnionFind:
def __init__(self, dataSize):
self.par = list(range(dataSize))
self.size = [1] * dataSize
self.unionCount = dataSize
def find(self, u):
if self.par[u] != u:
self.par[u] = self.find(self.par[u])
return self.par[u]
def getSize(self, u):
return self.size[self.find(u)]
def union(self, u, v):
u, v = self.find(u), self.find(v)
if u == v:
return
if self.size[u] < self.size[v]:
u, v = v, u
self.par[v] = u
self.size[u] += self.size[v]
self.unionCount -= 1
def getUnionCount(self):
return self.unionCount
billy_don
Senior Member
Cho đồ thị G. Gọi E là tập hợp tất cả các cạnh sao cho G liên thông và tổng số cạnh bé nhất. Chứng minh rằng mỗi vertex của G đều ưu tiên pick cạnh loại 3 để E tối ưu.
Không mất tính tổng quát, giả sử tồn tại một vertex V có 3 cạnh mỗi loại 1, 2, 3. Gọi số cạnh là nghiệm không chứa V là E0.
Mệnh đề A: Pick cạnh loại 3 không phải là phương án tối ưu để E nhỏ nhất => E = E0 + 2 (pick loại 1, 2 để nối tới V).
Tuy nhiên tồn tại phương án pick cạnh loại 3: E0 + 1. Vì E0 + 1 < E0 + 2 nên mệnh đề A sai.
=> pick cạnh loại 3 là phương án tối ưu ở mỗi vertex
=> mỗi vertex của G đều ưu tiên pick cạnh loại 3 để E tối ưu.
Sửa lần cuối:
small-lambda
Senior Member
giờ cho graph chỉ chứa edge type 3 và graph này là hình tam giác thì cây E có chứa toàn bộ edge trong tập B không?
billy_don
Senior Member
Mới sửa lại rồi
Chứng minh rằng mỗi vertex của G đều ưu tiên pick cạnh loại 3 để E tối ưu.
small-lambda
Senior Member
billy_don
Senior Member
Vì mỗi Vertex trên G đều liên thông, nên trường hợp chỉ chứa 1 và 2 hoặc chỉ chứa 3 thì không bàn vì không dùng để chứng minh cho mệnh đề được.
Vì đang chứng minh rằng ưu tiên pick 3, đối với các vertex chứa nhiều 1, 2, 3 thì cũng chỉ cần pick một cặp 1,2 hoặc một 3 để liên thông nên dùng vertex chứa 1, 2, 3 để đại diện vẫn được. Dù số lượng mỗi loại có là bao nhiêu cũng không mất tính tổng quát.
small-lambda
Senior Member
không, cứ cho là ở đây chứng minh được chuyện ưu tiên type 3 edge đúng trong trường hợp có vertex có nhiều edge thuộc cả ba type (gọi là case 1 đi), thì vẫn còn phần còn lại là đi chứng minh là khi không có vertex như vầy thì logic của algo vẫn đúng, tức là khi chỉ có vertex nối edge type 1, 2, v/v, chỉ khi nào cách chứng minh những trường hợp còn lại đó dùng logic giống như case 1 thì mới dùng "không mất tính tổng quát được"
giờ lấy trường hợp chỉ có vertex nối edge type 1, 2 thì chứng minh vầy đâu còn đúng nhỉ
Sửa lần cuối:
billy_don
Senior Member
Không, vì G liên thông nên trường hợp chỉ có (1,2) hoặc (3) thì kệ nó nhé. Đối với vertex có chứa cả 3 loại dù số lượng tụi nó có bao nhiêu đi nữa thì cũng chỉ pick một {(1,2) OR (3)} để E0 nối với V. Nên dùng (1,2,3) là đủ để đại diện cho toàn bộ case rồi còn gì nữa.không, cứ cho là ở đây chứng minh được chuyện ưu tiên type 3 edge đúng trong trường hợp có vertex có nhiều edge thuộc cả ba type (gọi lag case 1 đi), thì vẫn còn phần còn lại là đi chứng minh là khi không có vertex như vầy thì logic của algo vẫn đúng, tức là khi chỉ có vertex nối edge type 1, 2, v/v, chỉ khi nào cách chứng minh những trường hợp còn lại đó dùng logic giống như case 1 thì mới dùng "không mất tính tổng quát được"
giờ lấy trường hợp chỉ có vertex nối edge type 1, 2 thì chứng minh vầy đâu còn đúng nhỉ
small-lambda
Senior Member
vầy thì phải nói rõ ra trong chứng minh chứ nhỉ
billy_don
Senior Member
Đang chứng minh mỗi vertex ưu tiên type 3 mà, mà nếu ưu tiên nghĩa là tồn tại ít nhất một cặp (1,2) và một (3) nối với vertex chứ.vầy thì phải nói rõ ra trong chứng minh chứ nhỉ
small-lambda
Senior Member
có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia: chứng minh chia case mà logic nhiều case khác nhau thì không thể dùng "không mất tính tổng quát" và áp cách chứng minh một case cho các case còn lại được
giờ thêm cái nữa nè, cho là chứng minh như đã nói đúng đi thì nó chỉ mới chỉ ra được là thuật toán bắt buộc phải lấy edge type 3 thôi chứ chưa chứng minh được là cái thứ tự lấy edge type 3 trước rồi mới dùng edge type khác trong algo là đúng, tại sao không thể lấy type 1, 2 trước mà phải lấy type 3 trước? thuật toán nó giữ gìn invariant gì mà kết quả sau khi duyệt qua hết edge là đúng?
small-lambda
Senior Member
giờ pv vặn hỏi đứa pv mấy câu này mà nó không trả lời được thì sao nhỉ? không lẽ mình lại xiên 
không lẽ mình lại xiên
billy_don
Senior Member
Có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia.có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia: chứng minh chia case mà logic nhiều case khác nhau thì không thể dùng "không mất tính tổng quát" và áp cách chứng minh một case cho các case còn lại được
giờ thêm cái nữa nè, cho là chứng minh như đã nói đúng đi thì nó chỉ mới chỉ ra được là thuật toán bắt buộc phải lấy edge type 3 thôi chứ chưa chứng minh được là cái thứ tự lấy edge type 3 trước rồi mới dùng edge type khác trong algo là đúng, tại sao không thể lấy type 1, 2 trước mà phải lấy type 3 trước? thuật toán nó giữ gìn invariant gì mà kết quả sau khi duyệt qua hết edge là đúng?
Chứng minh là ưu tiên pick (3) thì đã chứng minh rồi. Và trường hợp (1,2,3) cũng là tổng quát cho mệnh đề t chứng minh. Các case còn lại dù có từ một trở lên cặp (1,2) hoặc chỉ có từ một trở lên (3) thì chả có duy nhất một lựa chọn à? Nếu nó chỉ có một lựa chọn thì còn gì để nói đâu, hoặc nó chỉ có (1) hoặc chỉ có (2) thì bài toán vô nghiệm.
Thêm nữa nè, để nó đúng cho toàn bộ graph là ở mỗi vertex đã pick thì không xử lí lại lần 2, nên nếu nó có (3) thì pick (3) sau đó xong, không đụng đến nó nữa, nếu nó có thêm cạnh khác thuộc E nối với nó thì đó là vấn đề của vertex khác. Vậy nên nó vẫn đúng cho cả toàn bộ graph.
billy_don
Senior Member
Thì tôi chứng minh nó ưu tiên (3) mà, còn chỉ nối edge 1, 2 thì pick một cặp (1, 2) cho mỗi vertex thôi. Nên chỉ có 1,2 thì chả có gì phải chứng minh hay bàn luận nữa.giờ lấy trường hợp chỉ có vertex nối edge type 1, 2 thì chứng minh vầy đâu còn đúng nhỉ
Sửa lần cuối:
small-lambda
Senior Member
chính vì hiểu rõ nên thấy là hai câu comment này cho thấy người viết comment không thấy vấn đề, không tin thì xin mời hỏi về cái cách chứng minh đã dùng trên một diễn đàn nào khác xem họ có đòi hỏi nói rõ ra từng case không, kiểu như computer science exchange,
mỗi lần nghe vặn thì lại chắp vá thêm vào logic, nhưng không nhìn ra được cái lỗ hỗng trong logic ban đầu, không thấy được sai sót, không hiểu người ta bắt bẻ cái gì
chỉ có lời khuyên là nên theo học một khóa proof-based math đi, có người sửa bài đàng hoàng, có nền tảng đó dễ tiếp thu nhiều thứ trong CS hơn
humanversion9x
Senior Member
Bạn chia ra hai trường hợp:
TH1: Trong những cạnh phải xóa không có bất cứ cạnh chung nào của 2 đồ thị thuộc type 3. Lấy tổng cạnh mỗi đồ thị trừ đi 2 x (số đỉnh - 1).
TH2: Có nhiều hơn hoặc bằng 1 cạnh phải xóa đồng thời trên 2 đồ thị thuộc type 3.
Ta đặt số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec, số cạnh sẽ xóa là Đáp_án_tối_ưu= e1 - (n - 1) + e2 - (n - 1) - ec.
Giả sử số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec - 1, lúc này thì mỗi một đồ thị bạn phải xóa thêm 1 cạnh để đảm bảo là mỗi đồ thị chỉ còn lại n - 1 cạnh.
Số cạnh phải xóa là
e1 - 1 - (n - 1) + e2 - 1 - (n - 1) - ec < Đáp_án_tối_ưu.
Sửa lần cuối:
billy_don
Senior Member
Tôi lại thấy anh bắt bẻ không được tôi nên lại bảo tôi không hiểu anh bắt bẻ gì?
??Còn logic chắp vá là vì anh đọc không hiểu nên tôi phải giải thích ra kĩ hơn đấy. Nên vấn đề ở người đọc chứ không phải người viết đâu.
Tôi học toán nhiều hơn anh đấy không cần phải bảo tôi đi học gì đâu nhé
small-lambda
Senior Member
coolTôi lại thấy anh bắt bẻ không được tôi nên lại bảo tôi không hiểu anh bắt bẻ gì?
Còn logic chắp vá là vì anh đọc không hiểu nên tôi phải giải thích ra kĩ hơn đấy. Nên vấn đề ở người đọc chứ không phải người viết đâu.
Tôi học toán nhiều hơn anh đấy không cần phải bảo tôi đi học gì đâu nhé
small-lambda
Senior Member
cái này mình nghĩ vẫn chưa trực tiếp chứng minh được là cái thuật toán như post trên này ra kết quả đúng, khi chứng minh thì phải nhìn vào phần thân của algo và chỉ ra được là sau mỗi lần loop là nó giữ một cái invariant gì đó dẫn đến kết quả đúng, kể cả khi graph A hoặc B disconnected, nhưng cảm ơn bạn đã dành thời gian
mà nghĩ kĩ, tốn thời gian đi chứng minh làm gì, vì luyện leetcode đâu phải để giỏi CS
- Trạng thái
Chủ đề tương tự
