Wyniki wyszukiwania - BazTech

1

The Use of Fuzzy Evaluation and Radical Cut-Off Strategy to Improve Apictorial Puzzle Assembly with Exhaustive Search Algorithm Performance

Skulimowski Stanisław, Montusiewicz Jerzy, Badurowicz Marcin

Advances in Science and Technology. Research Journal

|

2022

|

Vol. 16, no 2

179--187

EN

The paper presents an approach to solving the problem of assembling broken, flat elements using a letter notation of the elements’ contours and checking their matching using linguistic methods. Previous studies with the use of exhaustive search have shown effectiveness in finding possible connections, but they are burdened with a large number of calculations and the time needed to carry them out. In order to accelerate the process of searching for solutions, the possibility of using a fail-fast method of fuzzy assessment of potential combinations of elements was checked, as well as the method of cutting off potential, but not effective connections. The numerical experiment carried out showed a significant reduction in the number of trials and total computation time while maintaining the quality of the potential solutions found.

2

A Search Method for Reassembling the Elements of a Broken 2D Object

Montusiewicz Jerzy, Skulimowski Stanisław

Advances in Science and Technology. Research Journal

|

2020

|

Vol. 14, no 3

49--56

EN

Searching for and reassembling the elements that used to form one whole is a very common issue faced by archaeologists. This is because preparing an interesting museum exhibition consists in the presentation of the objects that have been put together, not a pile of messily disassembled puzzle pieces. The article presents the concept of using the linguistic methods in the process of joining the elements of a 2D jigsaw puzzle. The method developed in the first stage creates the edge description of an object by defined unit vectors of the same length but different directions, and assigns them a designation in the form of letters, which leads to the creation of abstract words in the form of a sequence of signs. In the second stage, the words with a defined length of strings belonging to two different objects are compared. The authors have created a program that performs an exhaustive search until the pool of available elements is fully exhausted. The conducted numerical experiments indicate the correctness of the method and effectiveness in determining the places of joining elements. The developed method will be useful to automate the reassembly of 2D elements from archaeological excavations.

3

An efficient exhaustive search for the discretizable Distance Geometry Problem with interval data

Mucherino A., Lin J.-H.

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

135--141

EN

The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph can be realized in a given space (generally Euclidean) so that a given set of distance constraints (associated to the edges of the graph) is satisfied. The Discretizable DGP (DDGP) represents a subclass of instances where the search space can be reduced to a discrete domain having the structure of a tree. In the ideal case where all distances are precise, the tree is binary and one singleton, representing one possible position for a vertex of the graph, is associated to every tree node. When the distance information is however not precise, the uncertainty on the distance values implies that a three-dimensional region of the search space needs to be assigned to some nodes of the tree. By using a recently proposed coarse-grained representation for DDGP solutions, we extend in this work the branch-and-prune (BP) algorithm so that it can efficiently perform an exhaustive search of the search domain, even when the uncertainty on the distances is important. Instead of associating singletons to nodes, we consider a pair consisting of a box and of a most-likely position for the vertex in this box. Initial estimations of the vertex positions in every box can be subsequently refined by using local optimization. The aim of this paper is two-fold: (i) we propose a new simple method for the computation of the three-dimensional boxes to be associated to the nodes of the search tree; (ii) we introduce the resolution parameter ρ, with the aim of controling the similarity between pairs of solutions in the solution set. Some initial computational experiments show that our algorithm extension, differently from previously proposed variants of the BP algorithm, is actually able to terminate the enumeration of the solution set by providing solutions that differ from one another accordingly to the given resolution parameter.