Українська   Русский
DonNTU   Masters' portal

Abstract

Content

Introduction

In the research work of students considered topics associated with automaton analysis of geometrical environments, graphs and other discrete structures .

One of the objectives of this subject is the problem of describing the structure of the object based on information obtained during traversal of a graph on its boundary. Similar problems arise in robotics, and molecular physics: model maps of the environment, the object model.

A number of papers devoted to the structure of the object recognition problem, which considered the case of solving such problems using a single machine (the agent). In this paper we propose an algorithm for solving the problem of recognition with the two agents. As an object model used an undirected graph. One of the objectives of this subject is the problem to the boundary of the mosaic structure of the graph based on finding holes in it.

1. Theme urgency

Topic was relevant back in the 50s of last century, when the first articles began to appear Shannon K., which is actually considered the problem of finding an automaton-mouse specific purpose in the labyrinth, which largely determined the subject areas for the coming years. After 60 years, the topic remains relevant and is often used in the creation of games, software and other products.

2. Purpose and tasks of the research

The purpose of the final work is to develop a new algorithm for reconstructing the mosaic structure of the graph, which may be present hole. Need to develop such algorithms AI agent movement on the original graph G with the transfer of information about it, and restore the graph of AE agent from the data obtained in the form of a formula that the AI in a finite number of steps regardless of the initial placement of bypass of the internal vertices of G are all boundary vertices, step by passing the information on which the AE after a finite number of steps will describe the graph of P, is isomorphic to the original graph G.

The main objectives of the stud.

  1. Develop an algorithm for AI and AE, to circumvent and recognition of the graph.
  2. Create a program to implement these algorithms.

Object of research: automatic analysis of graphs.

Subject of research: methods and algorithms for the reconstruction of the mosaic structure of the graph form, which can be present in the hole.

As part of the master plan to get the actual scientific results in the following areas.

  1. Development of an efficient algorithm for graph to the boundary considering it contains holes.
  2. Development of an efficient algorithm for graph traversal on the border.
  3. Development of an efficient algorithm for finding and describing all holes present in the graph.
  4. Development of an efficient algorithm to restore the graph.
  5. Determination of applications for this algorithm.
  6. Creating programs for graph traversal.

3. A review of research and development

One of the steps in solving the problem of reconstructing a graph with the mosaic structure of holes is to reach the border of the graph with the possibility of finding the holes on the way. In carrying out the research work has been developed algorithm output agent on the vertex of the mosaic structure with holes.

The algorithm outputs the agent on the border of the graph.

After setting the agent on an arbitrary vertex of the graph it is necessary to go to the border of the graph.

  1. Agent placed randomly in an arbitrary vertex of v.
  2. Agent checks the degree of a vertex, which hit.
  3. If the vertex degree to which the agent got less than five, it is a boundary vertex. The algorithm terminates.
  4. Agent checks the degree of vertices adjacent to the current vertex.
  5. If at least one of the adjacent vertices of degree less than five, then this is a boundary vertex and go to it. The algorithm terminates.
  6. If the degree of the current node is equal to six or five and there is diametrically opposite edge relative to the first comer edge, then go to the next summit. Further analysis is performed, starting from step 2.
  7. Diametrically opposite rib If absent, this hole and the hole is performed traversal algorithm.
  8. Actions are repeated until the agent will come to the border.

Traversal algorithm holes.

  1. Regarding diametrically opposite edges one turn clockwise hourly and shift to the next node.
  2. Regarding edges on which moved to the top of this two turns clockwise and move to the next node on the current edge.
  3. Regarding ribs diametrically opposite edge by which moved to the top of the current two turns clockwise and move to the next node.
  4. According edge diametrically opposite absence of a transition to the next node.
  5. Further analysis is made from step 2 of the general algorithm.

Principle of AI (yield on the border of the graph based on holes)


Figure 1 - Principle of AI (yield on the border of the graph based on holes)

3.1 Overview of national sources


Topics of graph theory in the national source of information is virtually absent, but quite often published new articles, algorithms, developments and solutions.

There are several great articles.

  1. Kapitonova Y., A. Letichevsky "The mathematical theory of design of computer systems".
    The fundamentals of mathematical tools and modern methods of data conversion system design: hardware computers, software and software systems, control systems and data processing, based on the use of computer tehniki. Pervaya part provides an overview of the basic mathematical models of computing systems. The second part contains an account of the practical methods of designing different types of systems — the hardware of computers, serial and parallel programs, a component of a system-wide matematiki.Dlya mathematicians and engineers - developers of hardware and software, as well as undergraduate and graduate students in computer science and computer engineering.
  2. V. Kudryavtsev, S. Ushchumlich, G. Kilibarda. "The behavior of automata in labyrinths".
    A survey of more than 80 works made over the past 20 years, the behavior of systems of automata in labyrinths. Stand the basic concepts, problems, achievements, problem-solving methods and open problems. The main assertion in some cases are in a stronger form in comparison with that of the authors. The article also contains new results on the problem of traversing labyrinths by automata.

3.2 Overview of local sources


In the Donetsk National Technical University has a publication entitled "Recognition of the graph of the mosaic structure of a group of agents" the authors: Shatokhina N., Shatokhin P.

The problem of analysis of discrete structures, represented by a graph of special form. In particular, we consider the problem of describing the structure of the graph based on information obtained during its traversal of the boundary. An algorithm for solving the problem, it gives an estimate of time and space complexity.

Conclusion

The analysis of existing recovery algorithms graph mosaic structure.

An algorithm output to the top of the graph with the possibility of the presence of holes in the graph.

An assessment of the complexity of the modified algorithm.

Note

During the publication of this essay, the master's thesis is not yet complete. Completion: December 2014. Full text of the work and materials on the topic can be obtained from the author or his manager after the indicated date.

References

  1. Шатохина Н.К., Шатохин П.А. Распознавание графа мозаичной структуры коллективом агентов. / Научные работы Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования» (МАП-2011). Выпуск: 9 (179) – Донецк, ДонНТУ – 2011. – С. 111–121.
  2. Оре О. Графы и их применение. – М.: «Мир», 1965. – 175 с.
  3. Оре О. Теория графов. – М.: Наука, 1968. – 336 с.
  4. Ерош И.Л., Сергеев М.Б., Соловьев Н.В. Дискретная математика: Учеб. пособие – СПбГУАП. СПб., 2005. – 144 с.
  5. Харари Ф. Теория графов. – М.: «Мир», 1965. – 302 с.
  6. В. Г. Дурнев, М.А. Башкин, О.П. Якимова Элементы дискретной математики. – Яросл. гос. ун-т им. П.Г.–Демидова. – Ярославль: ЯрГУ, 2007. – Часть II. – 173 с.
  7. Д.А. Кларнер Математический цветник. Пер. с англ. Данилова Ю. А. – М.: Мир, 1983. – 484 с.
  8. Ерош И.Л. Дискретная математика. Теория чисел: учеб. пособие / И. Л. Ерош. СПбГУАП. СПб., 2001. – 32 с.
  9. Уилсон Р. Введение в теорию графов. Пер с англ. – М.: Мир, 1977. – 208 с.
  10. Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. – М.: Физико-математическая литература, 1997.
  11. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
  12. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем / Ю.В. Капитонова, А.А. Летичевский. – М.: Наука, 1998. – 296 с.
  13. Кудрявцев В.Б., Ущумлич Ш. О поведении автоматов в лабиринтах / Дискретная математика. – 1992. – Т.4, Выпуск: 3. – С. 3–28.
  14. Анджанс А.В. Возможности автоматов при обходе плоскости / Проблемы передачи информации. – 1983. – Т.19, Выпуск: 3. – С. 78–89.
  15. Анджанс А.В. О возможностях автоматов при обходе одномерных областей / Латвийский математический ежегодник. Выпуск: 27. – Рига, 1983. – С. 191–201.
  16. Бесконечные графы. [Электронный ресурс]. – Режим доступа: https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/vvedenie-v-teoriu/beskonecnye-grafy
  17. Теория графов: основные понятия и определения. [Электронный ресурс]. – Режим доступа: http://mathhelpplanet.com/static.php?p=teoriya-grafov-ponyatiya-i-opredeleniya
  18. Плоские графы. Формула Эйлера. [Электронный ресурс]. – Режим доступа: http://grafielk.narod.ru/HTMLs/theory7.html
  19. Граф (математика). [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Граф_(математика)