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

楼主: lienasd126 (迷途の狮子)   2021-09-30 21:18:32
这一题前面有人发问过了,不过还是有点不清楚的地方,
https://i.imgur.com/igWRlSb.jpg
因为就vertex cover的定义是包含图形所有边的最小点集,
那么我们在找点的时候只要看是否有包含所有边,
那如题目所述的v1, v3, v4就好了,而对应到的是 x1, x3, x4,
那表格中的 yi 是为什么产生的? 这方面有点不太懂 ???
另外我有上网查过了,如https://reurl.cc/GbEg2D
这里也是用m_ei去做表示,但是就是也不知道为什么会还需要这个变量,
如果只是为了凑后面变量的2,好像变得很硬要,可以请各位大神解释,为什么要有下面
的变量,谢谢~
作者: jacksoncsie (资工肥宅)   2021-09-30 23:41:00
推楼上回答
作者: BusterButter (奶油巴斯特)   2021-09-30 23:33:00
每条edge至少会被一个cover set里的vertex给cover如果那条edge被两端都是在cover set里,那对应那条edge的digit是不是会被加两次可是有的edge只有一个端点是在cover set里面,所以我们为了让除了最高位外的digit都被加到2次,才有了m_e (题目里的y)
作者: BusterButter (奶油巴斯特)   2021-10-01 13:04:00
与其说是公平性 不如说m_e是为了让我们定义target方便而已(除了最高bit 其他都是2)反正我们的目标是n_v的个数而不是m_e因为n_v的个数正是vertex cover set的cardinality
作者: joywilliamjo (joywilliamjoy)   2021-10-01 14:01:00
可是这题最后算出来是22222啊不是32222啊没事是我看错了
作者: alex391a (麦基)   2021-10-07 09:20:00
一个比较直观一点的讲法是今天如果没有y那符合edge cover的取法结果有311111311112311122311121…也就是2^5种那我们有y之后 就可以透过拿某些y来加成322222相对的如果今天怎么取都会有个地方为0例如312120,310122…那不管怎么取y都加不到322222也就是找不到三个点可以cover所有edge

Links booklink

Contact Us: admin [ a t ] ucptt.com