GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (1)   Поиск:  
 Автор Тема: Решение задачки
queendetta
Сообщений: 4
Решение задачки
Добавлено: 30 ноя 08 13:40
Есть такая задачка :Какое максимальное количество коней можно разместить на доске размером N*N, чтобы они не угрожали друг другу?
пожалуйста подскажите как написать программу, которая сама решает эту задачу
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Решение задачки
Добавлено: 30 ноя 08 16:00
Не нужна никакая программа. Дело в том, что конь при ходе меняет цвет поля. Расставляете коней на поля одного цвета (того цвета, полей которого больше)- вот вам и решение задачи.
[Ответ][Цитата]
MadGod
Сообщений: 413
На: Решение задачки
Добавлено: 30 ноя 08 17:08
Вряд ли тут имелось ввиду реализация верного решения.

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


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

[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Решение задачки
Добавлено: 30 ноя 08 18:28
Цитата:
Автор: гость 195.93.160.*

Вряд ли тут имелось ввиду реализация верного решения.

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


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


Все понятно: нормальные герои всегда идут в обход. Удачи в изысканиях.
[Ответ][Цитата]
MadGod
Сообщений: 413
На: Решение задачки
Добавлено: 30 ноя 08 19:15
Ну, в таком случае, пусть автор темы нас рассудит (и я как всегда окажусь неправ).

Автору нужен был ответ-как-разместить-коней-на-доске
ИЛИ
текст-программы-которая-находит-оптимальное-решение-размещения-коней-на-доске-исключая-программы-которые-задают-вопросы-онлайн
?
[Ответ][Цитата]
daner
Сообщений: 4593
На: Решение задачки
Добавлено: 30 ноя 08 21:35
вообще-то есть классическая задача подобного типа, правда в ней не кони, а королевы.
надо разместить 8 королев.
Есть разные способы решения, в интернете не сложно найти. Причем, куча решений имеют еще и объяснение того, как к этому решению пришли.
Но лично я, сталкивался с этой задачей, когда Генетические Алгоритмы проходил. Уж больно она (задача) для примера использования ГА подходит (фитнес функция просто интуитивная).
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Решение задачки
Добавлено: 01 дек 08 0:03
В задачах с ферзями трудность в нахождении конкретного решения, но нет трудности в определении максимального числа фигур - на каждой линии одна фигура, всего восемь. В задаче с конями нет трудности ни в определении количества, ни в расстановке - ясно, что, например, для обычной шахматной доски можно расставить 32 коня на белые (или черные) поля и ни один из них не будет под боем. 33-го уже некуда сунуть, 32 максимум - это легко доказывается. Так что я не понимаю, что там Мадгод собирается программировать.
[Ответ][Цитата]
MadGod
Сообщений: 413
На: Решение задачки
Добавлено: 01 дек 08 13:49
>ясно, что, например, для обычной шахматной доски можно расставить 32 коня на белые >(или черные) поля и ни один из них не будет под боем

Ну, если так условия поставить, то может и прокатит...

Но как математически доказать что данный вариант решения лучший?
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Решение задачки
Добавлено: 01 дек 08 16:01
Цитата:
Автор: гость 195.93.160.*
Но как математически доказать что данный вариант решения лучший?

Если стороны доски больше трех (кроме доски 4 на 4) существует непрерывный обход конем всех полей. Очевидно, что на такой цепочке не должно попадаться стоящих рядом коней, между ними должно быть как минимум одно пустое поле. Отсюда и следует, что число коней для досок с четным числом полей равно n/2, где n - число полей. Для нечетных досок(n+1)/2. А это и есть вышеописанная расстановка по полям одного цвета. Для меньших досок возможны аномалии, (типа доска шириной 1 заполняется полностью), тут нужно рассматривать конкретные типы досок, но это уже не интересно.
[Ответ][Цитата]
queendetta
Сообщений: 4
На: Решение задачки
Добавлено: 08 дек 08 16:02
Ответ на эту задачку таков: N^2 /2 для N>=4, не могу сообразить как программу написать, которая сама решать будет

если кто-нибудь встретит что-нибудь похожее в интернете(описание решения или код) скиньте please
[Ответ][Цитата]
queendetta
Сообщений: 4
На: Решение задачки
Добавлено: 08 дек 08 16:27
Помогите составить программу
Очень срочно нужно
выручайте
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Решение задачки
Добавлено: 08 дек 08 16:44
Цитата:
Автор: queendetta

Ответ на эту задачку таков: N^2 /2 для N>=4, не могу сообразить как программу написать, которая сама решать будет

если кто-нибудь встретит что-нибудь похожее в интернете(описание решения или код) скиньте please

Если уж так нужно сделать программу, попробуйте выбрать поле и для него построить дерево достижимых полей (на которые может конь попасть за один или несколько ходов так, чтобы поля не повторялись). Если дерево построено, а поля не исчерпаны (для узких досок и досок неправильной формы), берете одно из оставшихся полей и поторяете процедуру. Затем раскрашиваете получившиеся деревья в два цвета так, чтобы принадлежащие одному ребру были раскрашены в разные цвета. Из каждого дерева выбираете поля того цвета, которых больше. Эти поля по всем деревьям и есть искомая расстановка.
Только ради бога, скажите, зачем это вам нужно?
[Ответ][Цитата]
queendetta
Сообщений: 4
На: Решение задачки
Добавлено: 08 дек 08 19:37
Спасибо!это мне для учебы нужно
[Ответ][Цитата]
 Стр.1 (1)