[理工] 台大資工 110資演 NPC

看板Grad-ProbAsk作者 (迷途の獅子)時間2年前 (2021/09/30 21:18), 2年前編輯推噓3(3推 0噓 10→)
留言13則, 3人參與, 2年前最新討論串1/1
這一題前面有人發問過了，不過還是有點不清楚的地方， https://i.imgur.com/igWRlSb.jpg
因為就vertex cover的定義是包含圖形所有邊的最小點集， 那麼我們在找點的時候只要看是否有包含所有邊， 那如題目所述的v1, v3, v4就好了，而對應到的是 x1, x3, x4， 那表格中的 yi 是為什麼產生的？ 這方面有點不太懂 ？？？ 另外我有上網查過了，如https://reurl.cc/GbEg2D 這裡也是用m_ei去做表示，但是就是也不知道為什麼會還需要這個變數， 如果只是為了湊後面變數的2，好像變得很硬要，可以請各位大神解釋，為什麼要有下面 的變數，謝謝～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.138.74 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1633007914.A.BDC.html ※ 編輯: lienasd126 (115.43.138.74 臺灣), 09/30/2021 21:19:23
→
09/30 23:33, 2年前 , 1F
每條edge至少會被一個cover set裡的vertex給cover
09/30 23:33, 1F
→
09/30 23:34, 2年前 , 2F
如果那條edge被兩端都是在cover set裡，那對應那條e
09/30 23:34, 2F
→
09/30 23:34, 2年前 , 3F
dge的digit是不是會被加兩次
09/30 23:34, 3F
→
09/30 23:36, 2年前 , 4F
可是有的edge只有一個端點是在cover set裡面，所以
09/30 23:36, 4F
→
09/30 23:36, 2年前 , 5F
我們為了讓除了最高位外的digit都被加到2次，才有了
09/30 23:36, 5F
→
09/30 23:36, 2年前 , 6F
m_e （題目裡的y)
09/30 23:36, 6F
謝謝Buster大回答 所以等於說是因為邊集內的edge會產生兩次的探訪，所以為了公平性（？）才有下面的那 塊，那如果是這樣不如可以說這個reduction 的 sum target就是固定的就是那個形是這 樣嗎？
推
09/30 23:41, 2年前 , 7F
推樓上回答
09/30 23:41, 7F
※ 編輯: lienasd126 (39.13.5.135 臺灣), 10/01/2021 09:08:56
→
10/01 13:04, 2年前 , 8F
與其說是公平性 不如說m_e是為了讓我們定義target方
10/01 13:04, 8F
→
10/01 13:04, 2年前 , 9F
便而已(除了最高bit 其他都是2)
10/01 13:04, 9F
→
10/01 13:04, 2年前 , 10F
反正我們的目標是n_v的個數而不是m_e
10/01 13:04, 10F
→
10/01 13:05, 2年前 , 11F
因為n_v的個數正是vertex cover set的cardinality
10/01 13:05, 11F
嗯嗯，謝謝 Buster大，大概懂了 ※ 編輯: lienasd126 (115.43.138.74 臺灣), 10/01/2021 13:51:29
推
10/01 14:01, 2年前 , 12F
可是這題最後算出來是22222啊不是32222
10/01 14:01, 12F
推
10/01 14:03, 2年前 , 13F
啊沒事是我看錯了
10/01 14:03, 13F
‣ 更多 lienasd126 的文章
文章代碼(AID): #1XLRaglS (Grad-ProbAsk)