2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Помогите разобраться Warnsdorff алгоритмом.
Сообщение09.06.2024, 14:28 


15/02/19
9
Warnsdorff предложил алгоритм для пути коня по всем клеткам шахматной доски в 1823 году.

Объясните, пожалуйста, как Warnsdorff доказал или пришёл к выводу, что самый простой и общий способ для коня - это идти в клетку
с минимальным количеством ходов ?

 Профиль  
                  
 
 Re: Помогите разобраться Warnsdorff алгоритмом.
Сообщение09.06.2024, 20:35 
Заслуженный участник


12/08/10
1676
Это эвристика - предположение, что такие действия приведут к результату.
Причины просты: если мы не пойдем в клетку с наименьшим количеством способов уйти, то в дальнейшем мы можем заблокировать все входы-выходы из нее и лучше сходить пока есть возможность.

 Профиль  
                  
 
 Re: Помогите разобраться Warnsdorff алгоритмом.
Сообщение11.06.2024, 13:14 


15/02/19
9
Null, я бы хотел познакомиться с доказательством Варнсдорфа от 1823 года.
Пришлось исполизовать перевод книги на Гугл https://books.google.ru/books?id=zvNdAAAAcAAJ&pg=PA1&source=gbs_selected_pages&cad=1#v=onepage&q&f=false .
Там 68 страниц, пока прочитал 14 с доказательствами разных теорем. Но ещё не дошёл до места где автор даёт идею
Цитата:
идти в клетку
с минимальным количеством ходов

 Профиль  
                  
 
 Re: Помогите разобраться Warnsdorff алгоритмом.
Сообщение14.06.2024, 21:31 


15/02/19
9
В 20 параграфе длинное доказательство того, что нужно "ставьте коня на пустое поле или произвольно на одно из полей, из которых у него меньше всего выходов на незанятые поля."
Считаю объяснение Null более понятным и коротким. Хотя и есть другие объяснения.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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