2014 dxdy logo

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

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




 
 Модифицированные версии задачи о 8 ферзях
Сообщение12.10.2014, 10:03 
Добрый день народ. Сегодня наверное день, которого многие из нас ждут всю неделю.
Все занимаются своим любимым делом в том числе я. Сегодня я запасся огромным
количеством еды, и до упаду буду решать задачи соревнований по спортивному
программированию. Но здесь не об этом. Все, наверное, знают известную задачу о восьми
ферзях http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%BE%D1%81%D1%8C%D0%BC%D0%B8_%D1%84%D0%B5%D1%80%D0%B7%D1%8F%D1%85

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

Мутант 1, задачи о восьми ферзях.
Вам дано начальное положение ферзей на доске, а именно в каждом столбце стоит
ровно по одному ферзю. Столбцов 8 штук, но ферзи возможно стоят так, что могут
атаковать друг друга по горизонтали или диагонали. Чтобы исправить это, вы можете
каждого ферзя перемещать вертикально (только). Ваша задача определить
минимальное количество ферзей, которых надо переместить чтобы получилось
расположение в котором никакой ферзь не атакует другого.

Изображение

Мутант 2, задачи о восьми ферзях.
Дана доска размера $20x20$, определите минимальное количество
ферзей, которые покроют всю доску, т. е. после их расположения не останется
неатакованных клеток, разрешается ставить их так, что они могут атаковать друг друга.

Изображение

 
 
 
 Posted automatically
Сообщение12.10.2014, 10:24 
Аватара пользователя
 i  Тема перемещена из форума «Беседы на околонаучные темы» в форум «Программирование»
Причина переноса: данная тема больше подходит к этому разделу.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение14.10.2014, 14:53 
Аватара пользователя
frankenstein в сообщении #917872 писал(а):
Мутант 2, задачи о восьми ферзях.

Жадный алгоритм + перебор с возвратом не поможет ли? Для досок размером до 8 не врет. Для 20 получилось 13 ферзей.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 09:14 
alex7851 в сообщении #918863 писал(а):
frankenstein в сообщении #917872 писал(а):
Мутант 2, задачи о восьми ферзях.

Жадный алгоритм + перебор с возвратом не поможет ли? Для досок размером до 8 не врет. Для 20 получилось 13 ферзей.

На каждом шаге ставить ферзя в клетку, так чтобы он бил как можно больше клеток - отличное решение.
Можете дать оценку сложности вашего решения?
Так же цель темы, собрать разные версии этой задачи, поэтому буду очень благодарен если предложите свою измененную версию задачи.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 13:06 
Линейное программирование - 12 ферзей

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 13:33 
mserg в сообщении #921847 писал(а):
Линейное программирование - 12 ферзей

Очень интересно, думаю вы тоже применили жадину.
Но, тут у меня возник другой вопрос: "как доказать что решение оптимально?",
хотя в этом можно убедиться перебрав все варианты.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 14:45 
Нет, не жадину. Линейное программирование. Нижняя граница - не менее 8-ми. Для повышения оценки нужно много-много памяти.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 16:03 
Можете рассказать про свой метод?

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение22.10.2014, 17:15 
Могу. Формулируется задача линейного программирования и решается с помощью готового математического пакета.

Пример можно найти тут:
http://np-soft.ru/npproject/projects/pu ... vering.htm
Описание ("программа") сделано на NP-языке, в качестве решателя в программе Quick NP использовался в CPLEX.

 
 
 
 Re: Модифицированные версии задачи о 8 ферзях
Сообщение23.10.2014, 15:43 
Цель которой я хотел достигнуть этом темой - собрать много разных версий задачи о восьми ферзях.
Ребята, очень круто, что вы решили задачи ( Признаюсь они очень скучные ).
Давайте собирать тут задачи о восьми ферзях.
Ведь интересно придумывать свою задачу, а тут еще узкая тематика. :D

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group