Детальная информация

В этой работе исследуются ДНК-вычисления как способ решения задачи о поиске гамильтонова пути в графе. Подробное рассмотрение этого алгоритма необходимо для создания новой концепции вычислительного устройства, потребность в котором возникла из-за того, что современные вычислительные устройства не справляются с большим количеством данных, и их развитие приблизилось к физическим порогам реализуемости. В этой работе также рассматривается метод ветвей и границ и показывается, что время расчета этим методом растет экспоненциально с увеличением количества вершин, в то время как время расчёта алгоритмом, основанном на ДНК-вычислениях, растет линейно. Доказывается, что с помощью ДНК-вычислений возможно решить задачу о поиске гамильтонова пути в графе с большим количеством вершин, чем методом ветвей и границ.

In this work we study and compare two different approaches to one of the most popular combinatorial problem — the Hamiltonian path problem. We show that it becomes inefficient to use branch and bound method, the most popular method which is realized on a computer, from the counted number of vertices because of its exponentially growing time consumption, so we analyze one more algorithm that is based on working with DNA molecules in a laboratory. The study of this method is important to the future development of computers.