Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[54.159.116.24] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Без раскачки переходим к делу!
Вот условие задачи: Есть шахматная доска размера N x M (N, M из отрезка [1 .. 350]). На некоторых клетках стоят черные фигуры (может быть ни одной черной фигуры). Нужно на свободные клетки доски расставить максимальное количество красных коней (их кол-во предполагается бесконечным), чтобы они не били друг друга. Обязательное требование: решить при помощи графов (графовых алгоритмов) ----------------------------------------------- На что обратил внимание после анализа: 1. речь про черные ФИГУРЫ, а не про коней. 2. красные кони должны не бить ДРУГ ДРУГА, а не черные фигуры. 3. привязка к шахматам - для отвода глаз, от шахмат здесь лишь возможный код коней (буквой "Г"). ИМХО, удобнее вместо "шахматной доски" рассматривать прямоугольную сетку. Какие проблемы получил: 1. У меня абсолютно не получается сформулировать эту задачу в терминах графов...Подскажите эту формулировку, плз. В целом связка шахматы-графы обычно вызывает концептуальные проблемы/непонимание (за себя говорю!). ---------------------------------------------- Тут надо подключить графы. С др.стороны графы в памяти иногда представляются матрицами (например, матрица смежности). Заданная сетка уже может служить неким представлением графа, но это НЕ факт. То есть один из вариантов - использование графов здесь - как бы лишняя надстройка, только мешающая алгоритмизации. Граф напрашивается планарным. Этот подход мне не нравится, но я ни на грамм не уверен, что он неправильный. 2 подход. Нумеруем ячейки заданной сетки слева направо и снизу вверх натуральными числами. Например, если сетка размера 7 х 7, то будет так: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 .... 43 44 45 46 47 48 49 Можно нумеровать по-другому, на итоговый алгоритм НЕ повлияет. Наверное) Рассмотрим более простой пример на заданной сетке размера 3 х 3 (БЕЗ черных фигур) и сразу построим граф (визуально, а не с тз памяти): Прикреплённая картинка
В памяти такой граф вроде хранить в формате матрицы смежности неоптимально (слишком разреженная будет, т к макс.степень вершины = 8 --> 8 возможных прыжков у коня может быть), поэтому придется юзать список смежности (но это неточно). Ядро алгоритма. 1. Когда ставится черная фигура, то из графа удаляется эта вершина, т к в эту ячейку красного коня уже НЕ поставить. 2. Когда ставится красный конь, то из графа удаляется эта вершина + все смежные вершины, т к на смежные вершины НЕЛЬЗЯ ставить др.красных коней (они будут бить друг друга). Единственная проблема: понять, в какую ячейку (др.словами, какую вершину удалять и все смежные с ней) ставить красного коня на очередном "ходе" алгоритма... Только 1 мысль: отбирать ту вершину графа, которая имеет наименьшую степень. Но я ни на грамм не уверен, что это то, что нужно. Если несколько вершин в графе с одинаковой мин.степенью - берем любую (тоже не факт). То есть получается смысл задачи в том, чтобы итеративно удалять вершины из графа со всеми смежными и максимизировать кол-во таких удалений. Подскажите как быть-то? спс за внимание |
Сообщ.
#2
,
|
|
|
Иогу расставить 18 коней
Добавлено Больше ничем помочь не могу |
Сообщ.
#3
,
|
|
|
Цитата MIF @ Иогу расставить 18 коней ну, неплохо) У меня тоже вроде 18 получалось в одном из вариантов, но ответ другой Цитата MIF @ Больше ничем помочь не могу , ну, и на этом спс кстати, нашел на забугорном сайте задачу очень похожую (не копия, но близкую вроде, а может и не близкую) и там есть какие-то выкладки и речь ушла В БИГРАФЫ...и там все сложно оказывается и нет здесь простого подхода...мда уж...какие же графы коварные по своей сути. Т е в этой задаче, возможно, надо подключить двудольные графы - ничего себе, в век бы на них здесь не подумал! |
Сообщ.
#4
,
|
|
|
Решение задачи: на одной доске расставляем коней на черные клетки, на второй - на белые. Выбираем лучшее решение из двух.
Теперь сюда надо бы графы прикрутить . |
Сообщ.
#5
,
|
|
|
Вообще-то это решение не всегда лучшее.
Если черные фигуры разбивают поле на несколько несвязанных областей, то каждую область надо оптимизировать независимо. Маленькие области, например 2х2, могут быть полностью заставлены красными конями. |
Сообщ.
#6
,
|
|
|
Цитата FasterHarder @ Кому не лень, можете попробовать расставить красных коней на этой сетке. Ответ у меня есть, но у меня не получается расставить коней в макс.количестве, всегда получается меньше. 23 штуки. Прикреплённая картинка
|
Сообщ.
#7
,
|
|
|
Цитата Akina @ 23 штуки. браво! |