Математические методы сборки пятнашек - Public forum of MSU united student networks

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.fds-net.ru/showflat.php?Number=5951029&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 10:01:08 2016
Кодировка: Windows-1251

Root \| Google \| Yandex \| Mail.ru \| Kommersant \| Afisha \| LAN Support

General Discussion >> Study (Archive)

Страницы: 1

teonik

member

Рег.: 03.03.2007

Сообщений: 119

Рейтинг: 35

Математические методы сборки пятнашек
26.03.2007 23:09

Вопрос математикам настоящим от математика бывшего: есть ли (ведь быть не может, чтоб не было) математические методы складывания картинки-пятнашки (стандарт: картинка поделена на 16 квадратиков 4х4, одна клетка пустая, можно двигать квадратик на соседнюю по стороне пустую клетку).

ksa

Умка

Рег.: 04.10.2006

Сообщений: 14535

Из: где-то на белом свете

Рейтинг: 7761

Re: Математические методы сборки пятнашек [re: teonik]
26.03.2007 23:47

Нет, хочет разгадать оригинальную задачу изобретателя Сэмюэля Лойда где 14 и 15 местами переставлены и заработать миллион - его так за 100 лет никому и не выплатили.

Читай Кострикин. Введение в алгебру.

Рег.: 26.12.2006

Сообщений: 439

Рейтинг: 0

Re: Математические методы сборки пятнашек [re: teonik]
27.03.2007 16:39

Доказано, что существуют неприводимые начальные расположения.

ksa

Умка

Рег.: 04.10.2006

Сообщений: 14535

Из: где-то на белом свете

Рейтинг: 7761

Re: Математические методы сборки пятнашек [re: Re]
27.03.2007 18:22

Ровно половина. Как перестановки. Все упирается в четность и нечетность перестановки. Задача, за которую Лойд обещал заплатить $$, вызвала полное сумасшествие, и все бросились ее разгадывать. Изобретатель очевидно знал, что не решается. Наварился на продаже головоломок хорошо.

halyavin

кфмн

Рег.: 14.12.2005

Сообщений: 916

Из: Moscow

Рейтинг: 622

Re: Математические методы сборки пятнашек [re: teonik]
27.03.2007 21:20

Есть простые алгоритмы складывания головоломки, когда это возможно. Грубо говоря, нужно в начале поставить на свое место единицу, затем двойку и.т.д. (есть определенные сложности с последним квадратом в ряду и с последними двумя рядами разумеется) Полиномиальных алгоритмов, которые находят минимальное решение на сколько мне известно нет. В прочем, эвристические алгоритмы с этой задачей не плохо справляются.

sonte

Рег.: 29.08.2002

Сообщений: 1077

Из: this country

Рейтинг: 461

Re: Математические методы сборки пятнашек [re: teonik]
28.03.2007 18:52

Ian Parberry, A Real-Time Algorithm for the (n²-1)-Puzzle, Inf. Process. Lett., 1995, 56(1):23-28, and references there.

Страницы: 1

General Discussion >> Study (Archive)

Дополнительная информация
1 зарегистрированных и 0 анонимных пользователей просматривают этот форум. Модераторы: Basilio, The_Nameless_One Печать темы	Права Вы можете создавать новые темы Вы можете отвечать на сообщения HTML отключен UBBCode включен	Рейтинг: Просмотров темы:
		Переход в