[理工][DS考古] 交大103

楼主: JoJo56 (JoJO)   2014-12-23 20:37:47
想请问以下几题,顺便对下答案
9.假设P不等于NP 当以下问题为P则选1 NP-hard or NP-complete选2 其他选3
(1)Find a longest simple path between two nodes,where the given graph has
positive edge weights.
(2)Find a shortest simple path between two nodes in a directed graph with
negative and/or positive edge weights ,and containing negative weight
cycles.
(3)Find a negative weight directed cycle in a weight directed graph.
(4) "" positive ""
(5)Find a largest cycle in a graph,where the edge-weight is 1 for each edge.
(6) smallest
(7)Find a max-cut in a flow network
(8) min-cut
(9)Find a max independent set in an interval graph
(10)2-CNF SAT problem
想问问大家的答案,目前我写的是2、7、8、9、10都是NPC,剩下的都不清楚
我很好奇他假设P不等于NP是不是有什么陷阱?
还有3既不属于P又不属于NPC那是又什么??
10.这题有图片希望大大能自行翻一下
(1)n=8,所以output = 8! ??? (2) ???
↑这题我不晓得要写什么,希望能解释一下
11.我写的是F T F F T
12.MAX flow 2+3 = 5,切边(S,A)(A,C)(C,D)
有些边流量并没有满(如A,C还有1的流量),就直接切了,可以吗?
求解,感恩
作者: FRAXIS (喔喔)   2014-12-24 02:51:00
1, 5, 7是NPC, 如果 P = NP, 那NPC = P 这题就变成多选题不属于P 又不属于 NPC 是有可能的 像是co-NP-Hard..
作者: APE36 (PT乡民)   2014-12-25 22:57:00
12.不行哦,要算到满才会是正确解
作者: JacobSyu (JacobSyu)   2014-12-27 00:32:00
11.a 若E小比Floyd快,我写True...
楼主: JoJo56 (JoJO)   2014-12-28 09:55:00
那请问第9题的所有答案是什么呢?想确认一下11题的话我是用DS的角度去看得Bellman's跟Floyd均为O(N^2)Dijkstra's为O(n^2)但不可以有负边12题用BFS来跑流量就找不到切边的样子
作者: JacobSyu (JacobSyu)   2014-12-28 15:21:00
12.resudual net.cut为c(S,A)+c(C,D)=511.依照cormen bellman+Dijk.:O(VE+VlgE), Floyd O(V^3)11.提及Bell. technique=>使人联想John.说太细易有bug9.NPC:1,2,4,5,6,7,8,9,10 P:3 (是这样?3.我想到bellman...O(VE)6.即使weight=1, nC3+nC4+...+nCn=2^n仍属NP6.cycle至少由3边构成...至多n6.大硕笔记大部分有整理分类,要感谢之前大大...伟X 烂bellman可得最大负循环?最小负循环稍加修改应该也可以P?或者bellman 只能判断(找)负循环 最大(小)无法判定(问!
楼主: JoJo56 (JoJO)   2014-12-28 16:01:00
11题因为DS上写都为O(n^3)所以我才认为是一样快,写F但用ALGO来看,边小的确是Bellman比较快 了解O硕近几年都没有DS考古题的详解,还挺困扰的12题的(a)用Edmonds-Karp求出MAX flow=5但找不出切边(b)用Ford-Fulkerson求出MAX Flow=4切边(S,A)(A,C)(C,D)

Links booklink

Contact Us: admin [ a t ] ucptt.com