Table | Card | RUSMARC | |
Allowed Actions: –
Action 'Read' will be available if you login or access site from another network
Action 'Download' will be available if you login or access site from another network
Group: Anonymous Network: Internet |
Annotation
В этой работе исследуются ДНК-вычисления как способ решения задачи о поиске гамильтонова пути в графе. Подробное рассмотрение этого алгоритма необходимо для создания новой концепции вычислительного устройства, потребность в котором возникла из-за того, что современные вычислительные устройства не справляются с большим количеством данных, и их развитие приблизилось к физическим порогам реализуемости. В этой работе также рассматривается метод ветвей и границ и показывается, что время расчета этим методом растет экспоненциально с увеличением количества вершин, в то время как время расчёта алгоритмом, основанном на ДНК-вычислениях, растет линейно. Доказывается, что с помощью ДНК-вычислений возможно решить задачу о поиске гамильтонова пути в графе с большим количеством вершин, чем методом ветвей и границ.
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.
Document access rights
Network | User group | Action | ||||
---|---|---|---|---|---|---|
ILC SPbPU Local Network | All | |||||
Internet | Authorized users SPbPU | |||||
Internet | Anonymous |
Usage statistics
Access count: 25
Last 30 days: 0 Detailed usage statistics |