2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Гамильтонов цикл в гридовом графе без дыр
Сообщение30.09.2015, 16:27 


30/09/15
1
Добрый день!
Лет 20 назад мне задали задачку:
Найти полиномиальный алгоритм для нахождения гамильтонова цикла в гридовом графе без дыр (hamiltonian cycle in grid graphs without holes), или доказать что задача NP-полная.
Задачу я решил, алгоритм нашел, доказал его корректность и полиномиальность. Правда задачу я решил далеко не первый, намного раньше появилась статья с другим алгоритмом и другим решением (An Algorithm for Finding Hamiltonian Cycles in Grid Graphs Without Holes (1996) - http://citeseerx.ist.psu.edu/viewdoc/su ... .1.32.6463 ).
Недавно я вспомнил про свое это увлечение на первом курсе, посмотрел решение и вот что обнаружил. Похоже мой при алгоритм после некоторой модификации может решать постановленную задачу за линейное время, то есть за $O(V)$.
Чтобы доказать это наверно придется помучаться, так как надо модифицировать алгоритм и доказать его корректность повторно.
Вопрос вот в чем: стоит ли за это браться? Появиться ли какая-то польза в том, что поставленная задача будет решена за линейное, а не полиномиальное время. К слову, в приведенной выше статье предложен алгоритм с временной сложность $O(V^4)$, да и сам алгоритм и его доказательство не очень красивы (это признает сам автор).
Я не математик, увлекался этим в далеком детстве. В этой области не шарю. Поэтому меня одолевают сомнения, есть ли в этом всем какая-либо практическая или научная ценность, и стоит ли на это тратить время, тем более что прошло 20 лет. Спасибо.

 Профиль  
                  
 
 Re: Гамильтонов цикл в гридовом графе без дыр
Сообщение30.09.2015, 20:59 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Paul
Все формулы и термы здесь следует $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Сейчас я формулы поправил, а следующее неоформленное сообщение поедет в Карантин.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Geen


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group