聊一下B题

pku007

1 很多人担心 209*209 跑不出来
2 w- o2 `( S# c3 D  很早放弃了 0-1规划
( M8 v: ?3 _$ z" b4 c  但我确信有人用 lingo 完整的跑出来 附件4
  尽管本题的立意不是全靠计算机 后面会说
) i0 Z; O+ e& p8 p8 Q8 B   
/ l0 c. n4 v1 N) x# L* P' \2 题目已经说得很清楚了
  一定是“人机结合”
7 g& c' J6 ?# U3 \, E& a  出题人的立意一定是
  发挥计算机强大的信息搜索和运算能力，
6 x+ J' Q( M3 a8 d) n" f. a  结合人脑对文字语言的不可替代的识别和纠错能力
  准确高效的实现了不同情形的碎片拼接
4 ?( u" q0 C6 p0 k* k3 M
) n% {, f5 q2 |7 g1 g0 C$ [3 提一个可以一直用的目标函数
! `: l9 m2 c% V+ e- |1 ^  记Ai是第i小块列向量，用1-0表示黑-白
  max f(i,j) = <Ai,Aj>
9 H8 ~9 {3 w- ?  u# ?9 Z$ L2 e/ E  内积实际上表示的重合黑点
; l# b# `6 E. g! e2 Y/ I" ]  到第三问的使用
9 r% b1 \8 ^0 {* d  用到的目标函数是
   f(i,j)=max {<Aai,Aaj>+<Abi,Abj>,<Aai,Abj>+<Abi,Aaj>}
: ^. L' e* f9 A1 A2 D7 E  这里a b表示了正反面 目标函数是 正反总共重合黑点数
9 f5 F4 c8 m9 e0 m  H2 U8 W- m- |0 ?  延续了模型的一致性
8 a( d7 ~/ c) Z( P  t! i
4 这个题的整体思路就是
9 C. G  U( r; b5 Z# w3 r, f  分步实施 降低 难度
" A; n8 T: S) D( S4 z3 |  人工干预 提高 准确率  
, `2 u. p* s# a4 [6 \3 n  J% U4 `  比方说问题二
- O  ~0 \! V( D5 W4 k2 i- v4 g    1）按文字基准线 分成11行
4 ~* I7 i& M7 a; y6 i9 l6 ]# Y    2）行内排列 归为问题一
1 V& r3 [( K: F: {& A$ h" A        3）人工纠错 （原因是信息变少了 1980变成180了）
        4）对11行排列 还是归为问题一
    5）进行整体人工识别与纠错。
! B2 {( F1 N8 ~% ^8 W
* l' _% S  N& ]% {5 关于人工干预
& \8 i) t: e$ |  1 人工干预的节点 不是前面 不是最后 应该是中间
+ d* A5 ]7 S: l" S4 ]2 z  s4 P  2 如果要写人工干预 必须讨论 人工干预的次数、节点、工作量或效率
: M; g, e% Z. J0 ^* d
6 基准线计算有技巧
  特别是英文的

. }; f6 i9 v' |2 y

) U6 e/ P5 i1 F+ Q. D" K5 K  x: |5 F
; y4 L* {- I; }
& ~6 a# @. [! u

4 H1 G6 a- _4 k1 R9 ]" {$ W  
5 x' a2 v( r/ d- Q; v# A6 l  
( V2 D& s6 n$ h; K  

漂流者

你的目标函数严格的说比较适合第一问，对于后边两问不好，我们第一问用的就是这个目标函数，直接就出来了，第二问除了这个条件还需要有很多其它条件，基本可以自动拼好，第三问比较麻烦，我们用了这个条件加基准线什么的，跑出来都不理想

maandy

那我也聊一下吧。。。。。
2 N6 T& B  ^- W: u2 p1.我的理解是，自动化程度越高越好
2.如果有牛人能做出全自动，为什么不呢？（虽然我们木有做出）
' Y6 @: w- a  Y' a7 J- E& _7 K3.你的目标函数和我们的很类似，但是实际上，中英文是有差异的；如果用同一个目标函数效果差很多。因此中英文纸片目标函数各不相同。
4.问题二反而人工纠错次数少了。因为看似180信息少了，实际上信息多了，增加了算法稳定性。看你的算法能不能灵活应变；
5.没理解错的话，人工干预的节点是指时间节点吧?
6.基准线的计是有技巧的 严重赞同。实际上在这里英文是可以转化利用中文的计算方法的。
最后吐槽一句，这题对编程能力要求颇高。吾等编程菜鸟挺悲剧!

pku007

maandy 发表于 2013-9-16 21:14
' j1 z% J8 ~1 i/ m- S那我也聊一下吧。。。。。
0 `) ~6 E. c% o. o* I& S" T/ I5 f4 K( L4 ?1.我的理解是，自动化程度越高越好
2.如果有牛人能做出全自动，为什么不呢？（ ...

2 s  i5 @! f$ Z% n/ r- J% K你非常熟悉题目 都是苦命的数模人
- u& i, j& D8 a1 关于 人工 我还是 坚持 应该 适当的加的 不然题目不会那么说
当然计算机 尽可能多处理是 今后的方向
2 人工节点 不是时间节点 应该是步骤节点
( T* c  \4 d! W7 Y4 ~. \3 目标函数 是可以写很多 估计你说的 不同的目标函数 是更优的解法
, x& b7 ]8 q( K
4 S/ @; s8 x5 a% S6 A" y5 x. A) x

Create_our_futu

都好牛啊，佩服佩服

xiehang199228

人工干预在没切到字上的碎片

爱我跟我走

行类聚如何匹配

chen288018

云雨霜露风

我们目标函数差不多，但用的是模拟退火，貌似效果还不错的

我一直都在

pku007 发表于 2013-9-16 21:32
你非常熟悉题目 都是苦命的数模人
1 关于 人工 我还是 坚持 应该 适当的加的 不然题目不会那么说
$ ?' s  _. D. v当然计 ...

/ Z4 C/ C/ g$ H' f这毕竟是一道比赛题目，3天肯定不会太完美，题目提到人工是因为人工有不可比拟的优势，同时作为大学本科生，更多的组没法完全解决，所以需要人工

5 I' Y/ y5 \8 \% g3 C/ s但是如果能够全部自动解决，肯定是最好的