国家重点基础研究发展计划 (973计划)(2015CB352201)
国家自然科学基金(61690200,61432020)
感谢匿名审稿人和编委对论文初始提交版本提出的宝贵修改意见和建议.
Appendix 符号与定义说明 本文中使用的基本符号和定义如下. $\bullet$ $(a_i)_1^K$: 数列$a_1,~a_2,~\ldots,~a_{K}$. $\bullet$ $|\mathcal{S}|$: 集合或数列$\mathcal{S}$中包含的元素的数量. $\bullet$ 给定一个图$G$, $\mathcal{V}(G)$表示其节点集合, $\mathcal{E}(G)$表示其边集合. $\bullet$ 给定图$G$中的一个节点$v~\in~\mathcal{V}(G)$, $d(v)$表示节点$v$的度, 即: 节点$v$参与到了几条边中. $\bullet$ 给定图$G$中的一条边$e~\in~\mathcal{E}(G)$, $\mathcal{V}(e)$表示由$e$两端的两个节点构成的集合. $\bullet$ $\mathbf{1}(x)$: 一个谓词函数. 当传入的谓词$x$为真, 该函数返回1; 否则, 返回0. 给定一个有穷实数数列$(a_i)_{1}^{K}$, 满足$a_i~\ge~a_{i+1}$, $i~\in~[1,~K)$. 给定实数常量$\epsilon~\ge~0$. 称$\lceil~(a_i)_{0}^{K}~\rceil^\epsilon$为$(a_i)_{0}^{K}$的$\epsilon$ –最大差分上序列, 当且仅当其满足如下条件: (1) $\forall~i~\in~[1,~K)~:~(a_i~-~a_{i+1})~\le~\epsilon~|a_i|~\Rightarrow~\lceil~(a_i)_{1}^{K}~\rceil^\epsilon=~(a_i)_{1}^{K}$, (2) $\exists~i~\in~[1,~K)~:~(a_i~-~a_{i+1})~>~\epsilon~|a_i|~\Rightarrow~\lceil~(a_i)_{1}^{K}~\rceil^\epsilon~=~(a_i)_{1}^{J}~\land~J~\in~[1,~K)~\land~(\forall~k~\in~[1,~J)~:~(a_k~-~a_{k+1})~<~(a_J~-~a_{J+1}))~\land~(\forall~k~\in~[J+1,~K)~:~(a_k~-~a_{k+1})~\le~(a_J~-~a_{J+1}))$. 按照这个定义, 一个有穷实数降序序列会在一对特定的邻接点(该对邻接点在序列中所有的邻接点中具有最大的差值)上断裂, 形成两个序列; 除非所有临界点$a_j$ 和 $a_{j+1}$的相对差值$\frac{a_j~-~a_{j+1}}{a_j}$都小于或等于常量$\epsilon$. 在后一种情况中, 该序列的$\epsilon$ –最大差分上序列就是其自身; 否则, 该序列的$\epsilon$ –最大差分上序列是断裂形成的前缀序列. 例如, 给定序列$\langle~10,9,8,7,6,3,2,1~\rangle$, 对于任意$\epsilon~<~0.5$, 该序列的$\epsilon$ –最大差分上序列为$\langle~10,9,8,7,6~\rangle$; 对于任意$\epsilon~\ge~0.5$, 该序列的$\epsilon$ –最大差分上序列为其自身. 又例如, 给定序列$\langle~10,9.9,9.8,9.7~\rangle$, 对于任意$\epsilon~<~\frac{1}{98}$, 该序列的$\epsilon$ –最大差分上序列为$\langle~10~\rangle$; 对于任意$\epsilon~\ge~\frac{1}{98}$, 该序列的$\epsilon$ –最大差分上序列为其自身. beginproperty 给定实数常量$\epsilon~\ge~0$, 任何一个有穷实数降序数列具有唯一一个$\epsilon$最大差分上序列. endproperty
[1] Torsvik T H. Geology. The Rodinia jigsaw puzzle.. Science, 2003, 300: 1379-1381 CrossRef PubMed Google Scholar
[2] Burkitt D P. Editorial: Large-bowel cancer: an epidemiologic jigsaw puzzle.. -J Natl Cancer Institute, 1975, 54: 3-6 CrossRef PubMed Google Scholar
[3] Brimacombe R. The Structure of Ribosomal RNA: A Three-Dimensional Jigsaw Puzzle. Eur J Biochem, 1995, 230: 365-383 CrossRef Google Scholar
[4] Verweij M, Thompson M. Clumsy Solutions for a Complex World: Governance, Politics and Plural Perceptions. London: Palgrave Macmillan, 2006. Google Scholar
[5] Zhang W, Mei H. Software development based on Internet collective intelligence: feasibility, state-of-the-practice, and challenges. Sin Chin Inform, 2017, 47: 1601--1622. Google Scholar
[6] Theraulaz G, Bonabeau E. A brief history of stigmergy.. Artificial Life, 1999, 5: 97-116 CrossRef PubMed Google Scholar
[7] Karsai I. Decentralized control of construction behavior in paper wasps: an overview of the stigmergy approach.. Artificial Life, 1999, 5: 117-136 CrossRef PubMed Google Scholar
[8] Susi T, Ziemke T. Social cognition, artefacts, and stigmergy: A comparative analysis of theoretical frameworks for the understanding of artefact-mediated collaborative activity. Cognitive Syst Res, 2001, 2: 273-290 CrossRef Google Scholar
[9] Dorigo M, Bonabeau E, Theraulaz G. Ant algorithms and stigmergy. Future Generation Comput Syst, 2000, 16: 851-871 CrossRef Google Scholar
[10] Freeman H, Garder L. Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition. IEEE Trans Electron Comput, 1964, EC-13: 118-127 CrossRef Google Scholar
[11] Berger R. The Undecidability of The Domino Problem. Washington: American Mathematical Society, 1966. Google Scholar
[12] Demaine E D, Demaine M L. Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity. Graphs Combin, 2007, 23: 195-208 CrossRef Google Scholar
[13] Goldberg D, Malon C, Bern M. A global approach to automatic solution of jigsaw puzzles. In: Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002. 82--87. Google Scholar
[14] Kong W, Kimia B B. On solving 2D and 3D puzzles using curve matching. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Kauai, 2001. 583--590. Google Scholar
[15] Radack G M, Badler N I. Jigsaw puzzle matching using a boundary-centered polar encoding. Comput Graphics Image Processing, 1982, 19: 1-17 CrossRef Google Scholar
[16] Wolfson H, Schonberg E, Kalvin A. Solving jigsaw puzzles by computer. Ann Oper Res, 1988, 12: 51-64 CrossRef Google Scholar
[17] Kosiba D A, Devaux P M, Balasubramanian S, et al. An automatic jigsaw puzzle solver. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, Jerusalem, 1994. 616--618. Google Scholar
[18] Makridis M, Papamarkos N. A new technique for solving a jigsaw puzzle. In: Proceedings of International Conference on Image Processing, Atlanta, 2006. 2001--2004. Google Scholar
[19] Nielsen T R, Drewsen P, Hansen K. Solving jigsaw puzzles using image features. Pattern Recognition Lett, 2008, 29: 1924-1933 CrossRef Google Scholar
[20] Yao F H, Shao G F. A shape and image merging technique to solve jigsaw puzzles. Pattern Recognition Lett, 2003, 24: 1819-1835 CrossRef Google Scholar
[21] Cho T S, Avidan S, Freeman W T. A probabilistic image jigsaw puzzle solver. In: Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, 2010. 183--190. Google Scholar
[22] Pomeranz D, Shemesh M, Ben-Shahar O. A fully automated greedy square jigsaw puzzle solver. In: Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, 2011. 9--16. Google Scholar
[23] Yang X, Adluru N, Latecki L J. Particle filter with state permutations for solving image jigsaw puzzles. In: Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, 2011. 2873--2880. Google Scholar
[24] Gallagher A C. 2012. Jigsaw puzzles with pieces of unknown orientation. In: Proceedings of the 25th IEEE Conference on Computer Vision and Pattern Recognition, Providence, 2012. 382--389. Google Scholar
[25] Sholomon D, David O E, Netanyahu N S. A genetic algorithm-based solver for very large jigsaw puzzles. In: Proceedings of the 26th IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013. 1767--1774. Google Scholar
[26] Sholomon D, David O E, Netanyahu N S. An automatic solver for very large jigsaw puzzles using genetic algorithms. Genet Program Evolvable Mach, 2016, 17: 291-313 CrossRef Google Scholar
[27] Son K, Hays J, Cooper D B. Solving square jigsaw puzzles with loop constraints. In: Proceedings of the 13th European Conference on Computer Vision, Zurich, 2014. 32--46. Google Scholar
[28] Parunak H V D. A survey of environments and mechanisms for human-human stigmergy. In: Proceedings of the 2nd International Workshop on Environments for Multi-Agent Systems, Utrecht, 2005. 163--186. Google Scholar
[29] Heylighen F. Collective intelligence and its implementation on the web: algorithms to develop a collective mental map. Comput Math Organization Theor, 1999, 5: 253-280 CrossRef Google Scholar
[30] Malone T, Laubacher R, Dellarocas C. The collective intelligence genome. IEEE Eng Manag Rev, 2010, 38: 38-52 CrossRef Google Scholar
[31] Rosenberg L B. Artificial swarm intelligence, a human-in-the-loop approach to A.I.. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, 2016. 4381--4382. Google Scholar
[32] Rosenberg L B. Human swarms, a real-time method for collective intelligence. In: Proceedings of the 13th European Conference Artificial Life, York, 2015. 658--659. Google Scholar
[33] Lee J, Kladwang W, Lee M. RNA design rules from a massive open laboratory. Proc Natl Acad Sci USA, 2014, 111: 2122-2127 CrossRef PubMed ADS Google Scholar
[34] Levy P. Collective Intelligence: Mankind's Emerging World in Cyberspace. Cambrigde: Perseus Books, 1997. Google Scholar
[35] Woolley A W, Chabris C F, Pentland A. Evidence for a Collective Intelligence Factor in the Performance of Human Groups. Science, 2010, 330: 686-688 CrossRef PubMed ADS Google Scholar
[36] Nielsen M. Reinventing Discovery: the New Era of Networked Science. Princeton: Princeton University Press, 2011. Google Scholar
[37] Maleszka M, Nguyen N T. Integration computing and collective intelligence. Expert Syst Appl, 2015, 42: 332-340 CrossRef Google Scholar
[38] Brabham D C. Crowdsourcing as a Model for Problem Solving. Convergence, 2008, 14: 75-90 CrossRef Google Scholar
[39] Howe J. Crowdsourcing: A definition. 2006. http://crowdsourcing.typepad.com/cs/2006/06/crowdsourcing_a.html. Google Scholar
[40] Howe J. The rise of crowdsourcing. Wired, 2006, 14: 1--4. Google Scholar
[41] Doan A, Ramakrishnan R, Halevy A Y. Crowdsourcing systems on the World-Wide Web. Commun ACM, 2011, 54: 86-96 CrossRef Google Scholar
[42] Estellés-Arolas E, González-Ladrón-de-Guevara F. Towards an integrated crowdsourcing definition. J Inf Sci, 2012, 38: 189-200 CrossRef Google Scholar
[43] Kittur A, Chi E H, Suh B. Crowdsourcing user studies with Mechanical Turk. In: Proceedings of Conference on Human Factors in Computing Systems, Florence, 2008. 453--456. Google Scholar
[44] Valentine M A, Retelny D, To A, et al. Flash organizations: crowdsourcing complex work by structuring crowds as organizations. In: Proceedings of Conference on Human Factors in Computing Systems, Denver, 2017. 3523--3537. Google Scholar
[45] Kittur A, Nickerson J V, Bernstein M, et al. The future of crowd work. In: Proceedings of Conference on Computer Supported Cooperative Work, San Antonio, 2013. 1301--1318. Google Scholar
[46] Romero J C, Valdez M G. Using a graph based database to support collaborative interactive evolutionary systems. In: Recent Advances on Hybrid Approaches for Designing Intelligent Systems. Berlin: Springer, 2014. 581--591. Google Scholar
Figure 1
Solving the PJ puzzle collaboratively based on the explore-integration-feedback (EIF) loop
Figure 2
A candidate solution of a PJ puzzle and its labelled graph representation. (a) A candidate-solution of a PJ puzzle of size 3$\times$4; (b) the labelled graph representation of this candidate-solution
Figure 3
Deducing edges from existing edges. (a) A connected graph; (b) the connected graphadding two deduced edges
Figure 4
Screenshot of a player's puzzle-solving workspace
Figure 5
The average time for player groups with gs $\in~[1,~10]$ to solve PJ puzzle with ps $\in~[4\times4,~10\times10]$. (a) A 3D view; (b) a 2D view
Figure 6
The puzzle-solving progress of a player group with gs $\in~[1,~10]$ to solve a $10\times10$ PJ puzzle
Figure 7
Average feedback precision (a) and feedback ratio (b) for different combinations of puzzle size and group size
Figure 8
Qualitative evaluations from players about the feedback information received in PJ puzzle solving
Figure 9
Puzzle-solving time and quality of stigmergy-based collaboration, face-to-face collaboration, and auto-solver
| ps | gs | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 4$\times$4 | 7 | 7 | 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 5$\times$5 | 6 | 6 | 6 | 6 | 6 | 5 | 4 | 3 | 2 | 1 |
| 6$\times$6 | 5 | 5 | 5 | 5 | 5 | 5 | 4 | 3 | 2 | 1 |
| 7$\times$7 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 2 | 1 |
| 8$\times$8 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 1 |
| 9$\times$9 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
| 10$\times$10 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| ps | gs | |||||||||
| 1 (s) | 2 (%) | 3 (%) | 4 (%) | 5 (%) | 6 (%) | 7 (%) | 8 (%) | 9 (%) | 10 (%) | |
| 4$\times$4 | 108.12 | 26.93 | 47.51 | 50.05 | 63.01 | 51.91 | 56.99 | 53.76 | 65.78 | 64.86 |
| 5$\times$5 | 191.50 | 26.89 | 34.20 | 58.23 | 31.59 | 64.49 | 72.32 | 51.18 | 45.43 | 65.83 |
| 6$\times$6 | 244.67 | 47.28 | 29.56 | 16.83 | 38.49 | 30.11 | 41.14 | 16.49 | 32.56 | 64.50 |
| 7$\times$7 | 385.38 | 36.69 | 19.50 | 57.44 | 55.37 | 43.95 | 57.44 | 38.76 | 53.03 | 57.23 |
| 8$\times$8 | 575.18 | 20.92 | 43.32 | 62.62 | 40.31 | 36.02 | 58.62 | 43.50 | 49.06 | 64.88 |
| 9$\times$9 | 821.17 | 21.58 | 43.80 | 40.07 | 38.25 | 34.35 | 42.14 | 66.26 | 51.89 | 62.16 |
| 10$\times$10 | 1432.12 | 39.20 | 41.17 | 55.56 | 58.03 | 58.90 | 68.68 | 63.72 | 71.44 | 72.51 |
| Average | 536.88 | 31.36 | 37.01 | 48.69 | 46.44 | 45.68 | 56.76 | 47.67 | 52.74 | 64.57 |
Download PDF
