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

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

Все темы | Новая тема  Стр.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 Сообщений: 4602	На: Решение задачки Добавлено: 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)