title: Ð Ð°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÑÐ±Ð¾ÑÐºÐ¸ Ð¿Ð°Ð·Ð»Ð°
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Solving the jigsaw puzzle problem
Creators: name: ÐÑÐ¼ÐµÑÐ¾Ð²Ð°, ÐÐ»ÑÐ±Ð¸Ð½Ð°
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2020
Subjects: Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ðµ Ð¾ÑÑÐ¾Ð²Ð½Ð¾Ðµ Ð´ÐµÑÐµÐ²Ð¾
Ð³ÐµÐ½ÐµÑÐ¸ÑÐµÑÐºÐ¸Ð¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼
ÑÐ°ÑÑÑÐ¾ÑÐ½Ð¸Ðµ Ð¼Ð°Ñ Ð°Ð»Ð°Ð½Ð¾Ð±Ð¸ÑÐ°
ÑÑÐ¼Ð¼Ð° ÐºÐ²Ð°Ð´ÑÐ°ÑÐ¾Ð² ÑÐ°Ð·Ð½Ð¾ÑÑÐµÐ¹
minimal spanning tree
genetic algorithm
mahalanobis distance
sum of squared differences

description: ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ð¸Ñ Ð´Ð²ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² ÑÐ±Ð¾ÑÐºÐ¸ Ð¿Ð°Ð·Ð»Ð¾Ð² Ñ ÐºÐ²Ð°Ð´ÑÐ°ÑÐ½ÑÐ¼Ð¸ ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ°Ð¼Ð¸ Ð±ÐµÐ· Ð¿ÐµÑÐµÐºÑÑÑÐ¸Ð¹, Ð¸ÑÐ¿Ð¾Ð»ÑÐ·ÑÑÑÐ¸Ñ ÑÐ¾Ð»ÑÐºÐ¾ Ð·Ð½Ð°ÑÐµÐ½Ð¸Ñ ÑÐ²ÐµÑÐ¾Ð² Ð¿Ð¸ÐºÑÐµÐ»ÐµÐ¹ Ð½Ð° ÐºÑÐ°ÑÑ ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð²: Ð¶Ð°Ð´Ð½ÑÐ¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼, Ð¾ÑÐ½Ð¾Ð²Ð°Ð½Ð½ÑÐ¹ Ð½Ð° Ð½Ð°ÑÐ¾Ð¶Ð´ÐµÐ½Ð¸Ð¸ Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð¾ÑÑÐ¾Ð²Ð½Ð¾Ð³Ð¾ Ð´ÐµÑÐµÐ²Ð°, Ð¸ Ð³ÐµÐ½ÐµÑÐ¸ÑÐµÑÐºÐ¸Ð¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼, Ð²Ð´Ð¾ÑÐ½Ð¾Ð²Ð»ÐµÐ½Ð½ÑÐ¹ Ð¼ÐµÑÐ°Ð½Ð¸Ð·Ð¼Ð°Ð¼Ð¸ ÐµÑÑÐµÑÑÐ²ÐµÐ½Ð½Ð¾Ð³Ð¾ Ð¾ÑÐ±Ð¾ÑÐ°. ÐÐ°Ð´Ð°ÑÐ¸, ÐºÐ¾ÑÐ¾ÑÑÐµ ÑÐµÑÐ°Ð»Ð¸ÑÑ Ð² ÑÐ¾Ð´Ðµ Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ñ: 1. ÐÐ·ÑÑÐµÐ½Ð¸Ðµ Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ Ð¶Ð°Ð´Ð½Ð¾Ð³Ð¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÑÐ±Ð¾ÑÐºÐ¸ Ð¿Ð°Ð·Ð»Ð¾Ð², Ð¾ÑÐ½Ð¾Ð²Ð°Ð½Ð½Ð¾Ð³Ð¾ Ð½Ð° Ð¿Ð¾Ð¸ÑÐºÐµ Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð¾ÑÑÐ¾Ð²Ð½Ð¾Ð³Ð¾ Ð´ÐµÑÐµÐ²Ð°. 2. ÐÐ·ÑÑÐµÐ½Ð¸Ðµ Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ Ð³ÐµÐ½ÐµÑÐ¸ÑÐµÑÐºÐ¾Ð³Ð¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° Ð´Ð»Ñ ÑÐ±Ð¾ÑÐºÐ¸ Ð¿Ð°Ð·Ð»Ð¾Ð². 3. Ð Ð°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ð¸Ðµ ÐºÐ°Ð¶Ð´Ð¾Ð³Ð¾ Ð¿Ð¾Ð´ÑÐ¾Ð´Ð° Ñ Ð´Ð²ÑÐ¼Ñ ÑÑÐ½ÐºÑÐ¸ÑÐ¼Ð¸ ÑÑÐ°Ð²Ð½ÐµÐ½Ð¸Ñ ÑÐ°Ð·Ð»Ð¸ÑÐ½Ð¾ÑÑÐ¸ ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð² Ð¿Ð°Ð·Ð»Ð°: ÑÑÐ¼Ð¼Ð° ÐºÐ²Ð°Ð´ÑÐ°ÑÐ¾Ð² ÑÐ°Ð·Ð½Ð¾ÑÑÐµÐ¹ Ð¸ ÑÑÐ½ÐºÑÐ¸Ñ, Ð¾ÑÐ½Ð¾Ð²Ð°Ð½Ð½Ð°Ñ Ð½Ð° ÑÐ°ÑÑÑÐ¾ÑÐ½Ð¸Ð¸ ÐÐ°ÑÐ°Ð»Ð°Ð½Ð¾Ð±Ð¸ÑÐ°. 4. Ð¡ÑÐ°Ð²Ð½ÐµÐ½Ð¸Ðµ Ð´Ð²ÑÑ ÑÐ°ÑÑÐ¼Ð°ÑÑÐ¸Ð²Ð°ÐµÐ¼ÑÑ Ð¿Ð¾Ð´ÑÐ¾Ð´Ð¾Ð². ÐÐ»Ñ ÑÐ°Ð±Ð¾ÑÑ Ñ Ð¿ÐµÑÐ²ÑÐ¼ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð¼ Ð¿Ð°Ð·Ð» Ð¸Ð½ÑÐµÑÐ¿ÑÐµÑÐ¸ÑÑÐµÑÑÑ ÐºÐ°Ðº Ð³ÑÐ°Ñ, Ð² ÐºÐ¾ÑÐ¾ÑÐ¾Ð¼ Ð½ÐµÐ¾Ð±ÑÐ¾Ð´Ð¸Ð¼Ð¾ Ð½Ð°Ð¹ÑÐ¸ Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ðµ Ð¾ÑÑÐ¾Ð²Ð½Ð¾Ðµ Ð´ÐµÑÐµÐ²Ð¾, Ð¸ÑÐ¿Ð¾Ð»ÑÐ·ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ ÐÑÐ°ÑÐºÐ°Ð»Ð°. ÐÐµÐ½ÐµÑÐ¸ÑÐµÑÐºÐ¸Ð¹ Ð¶Ðµ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð½Ð°ÑÐ¾Ð´Ð¸Ñ Ð¾Ð¿ÑÐ¸Ð¼Ð°Ð»ÑÐ½Ð¾Ðµ ÑÐ°ÑÐ¿Ð¾Ð»Ð¾Ð¶ÐµÐ½Ð¸Ðµ ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð² Ð¿Ð°Ð·Ð»Ð¾Ð² ÑÑÐµÐ´Ð¸ Ð¿ÑÐ¾ÑÑÑÐ°Ð½ÑÑÐ²Ð° Ð²ÑÐµÑ Ð²Ð¾Ð·Ð¼Ð¾Ð¶Ð½ÑÑ ÑÐµÑÐµÐ½Ð¸Ð¹ Ð¿ÑÑÐµÐ¼ ÑÐ»ÑÑÐ°Ð¹Ð½Ð¾Ð³Ð¾ Ð¿Ð¾Ð´Ð±Ð¾ÑÐ°, ÐºÐ¾Ð¼Ð±Ð¸Ð½Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ Ð¸ Ð¿ÐµÑÐµÑÑÐ°Ð½Ð¾Ð²Ð¾Ðº Ð¸ÑÐºÐ¾Ð¼ÑÑ Ð¿Ð°ÑÐ°Ð¼ÐµÑÑÐ¾Ð². ÐÐ°Ð¶Ð´ÑÐ¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð±ÑÐ» Ð·Ð°Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð¸ÑÐ¾Ð²Ð°Ð½ Ð½Ð° ÑÐ·ÑÐºÐµ Ð¡++ Ð¸ Ð¿ÑÐ¾Ð²ÐµÐ´ÐµÐ½ Ð¸Ñ ÑÑÐ°Ð²Ð½Ð¸ÑÐµÐ»ÑÐ½ÑÐ¹ Ð°Ð½Ð°Ð»Ð¸Ð·. Ð¡ÑÐ°Ð²Ð½ÐµÐ½Ð¸Ðµ Ð¿ÑÐ¾Ð²Ð¾Ð´Ð¸Ð»Ð¾ÑÑ Ð¿Ð¾ ÑÐ¾ÑÐ½Ð¾ÑÑÐ¸ Ð½Ð° Ð½Ð°Ð±Ð¾ÑÐµ Ð´Ð°Ð½Ð½ÑÑ Ð¸Ð· 1800 Ð¿Ð°Ð·Ð»Ð¾Ð² Ñ ÑÐ°Ð·Ð»Ð¸ÑÐ½ÑÐ¼ ÑÐ¸ÑÐ»Ð¾Ð¼ ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð² ÑÑÐµÑ ÑÐ°Ð·Ð¼ÐµÑÐ¾Ð² Ð¸ Ð²ÑÐµÐ¼ÐµÐ½Ð½Ð¾Ð¹ ÑÐ»Ð¾Ð¶Ð½Ð¾ÑÑÐ¸ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð². Ð ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ Ð±ÑÐ» Ð¾Ð¿ÑÐµÐ´ÐµÐ»ÐµÐ½ Ð²ÑÐ±Ð¾Ñ Ð¿Ð¾Ð´ÑÐ¾Ð´Ð° Ð´Ð»Ñ ÑÐµÑÐµÐ½Ð¸Ñ ÑÐ°Ð·Ð»Ð¸ÑÐ½ÑÑ Ð¿Ð°Ð·Ð»Ð¾Ð². ÐÑÐ¸ Ð½ÐµÐ¾Ð±ÑÐ¾Ð´Ð¸Ð¼Ð¾ÑÑÐ¸ ÑÐµÑÐµÐ½Ð¸Ñ Ð¿Ð°Ð·Ð»Ð¾Ð², ÑÐ¾ÑÑÐ¾ÑÑÐ¸Ñ Ð¸Ð· Ð½ÐµÐ±Ð¾Ð»ÑÑÐ¾Ð³Ð¾ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð° ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð², Ð¾Ð±Ð° ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ð½ÑÑ Ð¿Ð¾Ð´ÑÐ¾Ð´Ð° Ð´Ð°ÑÑ ÑÐ¾ÑÐ¾ÑÐ¸Ð¹ ÑÐµÐ·ÑÐ»ÑÑÐ°Ñ, Ð´Ð¾ÑÑÐ¸Ð³Ð½ÑÑÐ°Ñ ÑÐ¾ÑÐ½Ð¾ÑÑÑ ÑÐ¾ÑÑÐ°Ð²Ð¸Ð»Ð° 89%. ÐÑÐ¸ ÑÐµÑÐµÐ½Ð¸Ð¸ Ð¿Ð°Ð·Ð»Ð¾Ð² Ð¸Ð· Ð±Ð¾Ð»ÑÑÐ¾Ð³Ð¾ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð° ÑÑÐ°Ð³Ð¼ÐµÐ½ÑÐ¾Ð² Ð¼Ð°Ð»ÐµÐ½ÑÐºÐ¾Ð³Ð¾ ÑÐ°Ð·Ð¼ÐµÑÐ° ÑÑÐ¾Ð¸Ñ Ð¾ÑÑÐ°Ð½Ð¾Ð²Ð¸ÑÑ ÑÐ²Ð¾Ð¹ Ð²ÑÐ±Ð¾Ñ Ð½Ð° Ð³ÐµÐ½ÐµÑÐ¸ÑÐµÑÐºÐ¾Ð¼ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ðµ Ñ ÑÑÐ½ÐºÑÐ¸ÐµÐ¹, Ð¾ÑÐ½Ð¾Ð²Ð°Ð½Ð½Ð¾Ð¹ Ð½Ð° ÑÐ°ÑÑÑÐ¾ÑÐ½Ð¸Ð¸ ÐÐ°ÑÐ°Ð»Ð°Ð½Ð¾Ð±Ð¸ÑÐ°.
description: This paper is devoted to the development of a genetic algorithm with optimization and comparison with greedy algorithm. This work introduces two algorithms for square-piece image jigsaw puzzles without overlapping that only using information of the pixel value on the border line of the pieces: the first is greedy algorithm based on finding minimum spanning tree and the second one uses genetic algorithm which was inspired by natural selection mechanisms. In this paper were solving the following tasks: 1. Studying and implementing a greedy puzzle assembly algorithm based on finding the minimum spanning tree. 2. Studying and implementing a genetic algorithm. 3. Consideration of each approach with two functions for comparing the differences of puzzle pieces: the sum of the squared differences and a function based on the Mahalanobis distance. 4. Comparing two algorithms. In In the first approach we interpret the puzzle as a graph in which we need to find for a minimum spanning tree. The genetic algorithm searches the optimum piece arrangement in large optimization space by random search, combination and rearrangement of the desired parametres. Other contributions of the paper include two pieces dissimularity measure functions: sum of squared differences and the function based on Mahalanobis distance. Each of approaches was programmed in C++ and analyzed. A comparison for accuracy was made on 1800 pictures dataset with different number of pieces of three sizes. Also, a time complexity comparison was made. As a result, we determine the way to choose algorithm in different cases. If it is necessary to solve puzzles consisting of a small number of fragments, both approaches considered give a good result, the achieved accuracy was 89%. When solving puzzles from a large number of small fragments, it is worth choosing a genetic algorithm with a function based on the distance of the Mahalanobis.