Проет, описываемый в настоящей статье, предназначен для исполнения старшеклассниками (а возможно - студентами младших курсов в качестве курсовой работы). Важно отметить, что реализация первой части проекта (компьютерной программы, решающей конкретную раскладку пасьянса) представляет собой весьма незначительную часть работы, предлагаемой для выполнения в этом проекте. Однако и эта часть - создание компьютерной программы для решения конкретной раскладки - тоже является задачей, относящейся к искусственному интеллекту.
В качестве основного критерия качества программы-решателя мы предлагаем использовать процент решения ею случайно сгенерированных раскладок, причём решение должно быть осуществлено без возможности взятия хода назад. Для программирования решения некоторой заданной раскладки мы предлагаем смоделировать процесс решения этой задачи человеком, мышление которого сильно отличается от «мышления» компьютера, в частности, отличатся объёмом запоминаемой информации. Для этого моделирования запрещается, например, программе запоминать фишки, которые уже вышли из игры.
Мы рассматриваем только «заведомо разрешаемые» раскладки. В качестве первого варианта (то есть в качестве начала реализации), мы предлагаем ученику реализовать программу, которая только решает раскладки, полученные случайным заполнением - заполнением пустого поля «с конца». Возможный подход к реализации программы-решателя - применение генетических алгоритмов. Отметим, что даже в этом случае решатель можно назвать небольшой экспертной системой. Мы также кратко описываем в статье некоторые другие области искусственного интеллекта, знание и применение которых возможно в рассматриваемой задаче.
Ранее авторы уже предагали аналогичные проекты студентам младших курсов, было реализовано несколько из них, но бóльшая часть материала, описанного в статье, ещё не реализована, поэтому документ озаглавлен как научный проект для реализации. С. 41-51.

The project described in this article is intended to be performed by high school students (and possibly by undergraduate students as a term paper).
It is important to note that the implementation of the first part of the project (the computer program that solves the specific layout of the solitaire) is a very small part of the work proposed for implementation in this project. However, this part --- the creation of a computer program for solving a particular layout - is also a task related to artificial intelligence.
As a general criterion for the quality of the solver program, we propose to use the percentage of the solved layouts — which are randomly generated by the program --- with the condition that the solution was found without the possibility of taking a step back. To program the solution of a given layout, we propose to model the process of solving this problem by a person --- whose thinking is very different from the computer’s “thinking”, in particular, it will differ in the amount of information stored. For this simulation, for example, we prohibit the program to memorize the chips that have already left the game.
We consider only ``knowingly solvable'' solitaire layouts. As the first option (that is, the beginning for implementation), we suggest to the student to implement a program that solves the layouts obtained by random generation ``from the end''. A possible approach for the implementation of the solver program is the application of genetic algorithms. Note that even in this case, the solver can be called a small expert system. We also briefly describe in the article some other areas of artificial intelligence, the knowledge and application of which is possible in the task at hand.
Previously, the authors had already presented similar projects to undergraduate students, several of them were implemented, but most of the material described in the article has not yet been implemented; therefore, the document is entitled as a science project for implementation.

С конца 1960-х годов изучается задача минимизации недетерминированных конечных автоматов. В практических программах для больших размерностей получение точного ответа обычно занимает неприемлемо большое время. В связи с этим нас интересуют, среди прочих, эвристические алгоритмы решения задачи - алгоритмы, <<ничего не обещающие>>, однако на практике в большинстве случаев дающие за приемлемое время работы решение, близкое к оптимальному.
Предлагаемый школьникам проект направлен на частичное решение одной из вспомогательных задач, возникающих в упомянутой оптимизационной задаче. Для этого мы специальным образом определяем отношение эквивалентности на множестве таблиц заданного размера M x N, заполненных элементами 0 и 1. Получение количества неэквивалентных таблиц размерности 8 x 10 будет являться серьёзным шагом на пути к доказательству того факта, что описанный ещё в 1970 г. пример <<плохого>> автомата (так называемого автомата Ватерлоо) - минимально возможный пример, не имеющий <<меньших>> аналогов.
Для решения задачи мы сначала предлагаем плохой алгоритм, заключающийся в~простом переборе матриц. Этот алгоритм хорошо работает на матрицах малых размерностей, но, как обычно в подобных ситуациях, при переходе к большим размерностям он работает неприемлемо долго. Для уменьшения времени работы алгоритма мы предлагаем несколько эвристик и приводим результаты работы разных версий программы. Цель проекта - создание новых эвристик, ещё большее убыстрение времени работы программы и, по возможности, получение ответа (количества таблиц) для размерности 8 x 10.
Для большинства описываемых в статье вариантов алгоритма мы приводим реализацию на языке C#, использующую принципы объектно-ориентированного программирования. Мы предполагаем, что дальнейшая работа над проектом будет заключаться в дальнейшей модификации приведённых нами программ. C. 87-107.

Since the late 1960s, the problem of minimizing non-deterministic finite automata has been studied. In practical programs for large dimensions, obtaining an exact answer usually takes an unacceptably long time. In this regard, we are interested in, among others, heuristic algorithms for solving the problem, i.e. in algorithms that ``do not promise anything'', which, however, in practice in most cases, they give a solution that is close to optimal for an acceptable working time.
The project proposed for schoolchildren is aimed at a partial solution of one of the auxiliary tasks arising in the mentioned optimization problem. To do this, we define in a special way the equivalence relation on the set of tables of a given size M x N filled with elements 0 and 1. Obtaining the number of nonequivalent tables of dimension 8 x 10 will be a serious step on the way to proving the fact that the example of the ``bad'' automaton described in 1970 (the so-called Waterloo automaton) is the minimal possible example, not having ``lesser'' analogues.
To solve the problem, we first propose a bad algorithm, which consists in a simple enumeration of matrices. This algorithm works well on matrices of small dimensions, but, as usual in such situations, it works unacceptably long when moving to large dimensions. To reduce the operating time of the algorithm, we offer several heuristics, and present the results of the work of different versions of the program. The goal of the project is the creation of new heuristics, an even greater increase in the operating time of the program and, if possible, obtaining an answer (the number of tables) for the dimension 8 x 10.
For the majority of variants of the algorithm described in the paper, we present the implementation in C# using the principles of the object-oriented programming. We assume that further work on the project will consist in further modification of the programs we have provided.

В литературе описано очень много задач, которые могут быть названы задачами дискретной оптимизации: от шифровки информации в Интернете (включая создание программ для криптовалют) до поиска групп <<по интересам>> в социальных сетях. Часто эти задачи очень сложны для решения на компьютере, откуда и идёт их название <<труднорешаемые>>. Точнее, сложны для решения (описания алгоритмов, программирования) возможные подходы к быстрому решению этих задач, переборное же решение, как правило, программируется просто, но работает соответствующая программа гораздо медленнее. Практически каждую из таких труднорешаемых задач можно назвать математической моделью. При этом часто и сама модель, и алгоритмы, предназначенные для её решения, создаются для одной предметной области, но могут найти применение и во многих других областях. Примером такой модели является задача коммивояжёра. Особенностью задачи является то, что при относительной простоте её постановки нахождение оптимального решения (оптимального маршрута) является весьма сложным и относится к так называемому классу NP-полных проблем. Более того, согласно имеющейся классификации, задача коммивояжёра является примером оптимизационной проблемы, входящей в самый сложный подкласс этого класса. Однако основной предмет статьи – это не задача, а метод её решения, метод ветвей и границ. Он состоит из нескольких связанных между собой эвристик, и в монографической литературе подобная мультиэвристичость метода ветвей и границ ранее отмечена, по-видимому, не была: разработчики алгоритмов и программ это должны были понимать сами. При этом сам метод может быть применён с небольшими изменениями и ко многим другим задачам дискретной оптимизации. Итак, классический вариант метода ветвей и границ – основной предмет настоящей статьи, но почти столь же важен и второй её предмет – задача коммивояжёра, тоже в классической её постановке. Речь идёт о применении метода ветвей и границ при решении задачи коммивояжёра, причём в отношении этого применения также можно употребить прилагательное <<классическое>>. Однако в дополнение к классической версии этой реализации мы рассматриваем новые эвристики, связанные с необходимостью разработки алгоритмов реального времени. C. 21-44.

In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for ``interests'' groups in social networks. Often, these problems are very difficult to solve on a computer, hence they are called ``intractable''. More precisely, the possible approaches to quickly solving these problems are difficult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, finding the optimal solution (the optimal route). This problem is very difficult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classification, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class. However, the main subject of the paper is not the problem, but the method of its solution, i.e. the branch and bound method. It consists of several related heuristics, and in the monographs, such a multi-heuristic branch and bound method was apparently not previously noted: the developers of algorithms and programs should have understood this themselves. At the same time, the method itself can be applied (with minor changes) to many other discrete optimization problems. So, the classical version of branch and bound method is the main subject of this paper, but also important is the second subject, i.e. the traveling salesman problem, also in the classical formulation. The paper deals with the application of the branch and bound method in solving the traveling salesman problem, and about this application, we can also use the word ``classical''. However, in addition to the classic version of this implementation, we consider some new heuristics, related to the need to develop real-time algorithms

В компьютерной литературе описано много проблем, которые можно назвать задачами дискретной оптимизации: от шифрования информации в Интернете (включая создание программ для цифровых криптовалют) до поиска групп по интересам в социальных сетях. Часто эти задачи очень сложно решить на компьютере, поэтому их называют «труднорешаемыми».Точнее, сложно описывать возможные подходы к решению этих проблем; при этом программы, основанные на полном переборе вариантов, как правило, программируются просто, но работают значительно медленнее. Почти каждую из этих трудноразрешимых задач можно назвать математической моделью. В то же время как сама модель, так и алгоритмы, предназначенные для ее решения, часто создаваемые для одной предметной области, могут быть также использованы во многих других областях. Примером такой модели является задача коммивояжера. Особенность проблемы в том, что несмотря на относительную простоту её формулировки, поиск оптимального решения (оптимального маршрута) достаточно сложен. Эта задача очень трудна и относится к так называемому классу NP-полных задач. Кроме того, согласно существующей классификации, задача коммивояжера является примером оптимизационной задачи из самого сложного подкласса этого класса. В настоящей работе мы описываем несколько вариантов алгоритмов формирования исходных данных для задачи коммивояжера. После этого мы рассматриваем как классические эвристики, связанные с методом ветвей и границ, так и некоторые дополнения к ним. Далее мы представляем программную реализацию нашей интерпретации алгоритма. В конце статьи мы предлагаем несколько задач для дальнейшего исследования, поэтому статью можно считать описанием проекта для научной работы студентов. (На англ.) С. 41–58.

In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for “interests” groups in social networks. Often, these problems are very difficult to solve on a computer, hence they are called “intractable”. More precisely, the possible approaches to quickly solving these problems are difficult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, finding the optimal solution (the optimal route). This problem is very difficult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classification, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class. In this paper, we describe several variants of algorithms for generating source data for the traveling salesman problem. We consider both the classical heuristics associated with the branch and bound method, and some added to them. Next, we present a software implementation of our interpretation of the algorithm. At the end of the paper, we formulate some tasks for further research, so the paper can be a project for students' scientific work.

Мы продолжаем рассматривать псевдогеометрическую задачу коммивояжера. В частности, мы рассматриваем несколько вспомогательных алгоритмов, необходимых для реализации различных версий алгоритма «луковой шелухи». Мы не нашли в~литературе точного описания конкретных версий алгоритмов для геометрической версии (впрочем, в этом нет необходимости, поскольку исходные версии этих алгоритмов необходимо реализовать для псевдогеометрической версии), поэтому мы начинаем работу с геометрической версии.
Случайная генерация данных для вычислительных экспериментов соответствовала решаемой проблеме: для каждого из нескольких вариантов размерности задачи были проведены некоторые вычислительные эксперименты со случайно сгенерированными входными данными. Были рассчитаны следующие характеристики полученных результатов: среднее количество результирующих контуров для геометрического варианта; отношение решения с контурами к оптимальному решению; отношение решения псевдогеометрической версии, соответствующее порядку точек геометрической версии, к геометрическому решению.
Полученные результаты вычислительных экспериментов в целом приблизительно соответствуют ожидаемым значениям. (на англ.) С. 30-40.

We continue to consider the pseudo-geometric traveling salesman problem. Specifically, we are considering several auxiliary algorithms needed to implement different versions of the “onion husk” algorithm. We have not found in the literature an accurate description of specific versions of algorithms for the geometric version (however, this is not necessary, since it is necessary to implement the original versions for the pseudo-geometric version), so we start with the geometric version.
Random generation of data for computational experiments corresponded to the problem being solved.
For each of the some dimensional variants, some computational experiments were conducted with randomly generated input data.
The following characteristics were calculated: the average number of resulting contours for the geometric variant; the ratio of the solution with contours to the optimal solution; the ratio of the solution of the pseudo-geometric version corresponding to the order of points of the geometric version to the geometric solution.
The obtained results of computational experiments in general approximately correspond to the expected values.