Шахматный конь, рекурсия, максимумы

Рейтинг: 3Ответов: 3Опубликовано: 21.12.2014

Имеется шахматная доска 8х8. Предположим в каждой клетке доски содержится некоторое количество яблок. Шахматная фигура “конь” может ходить по классическим правилами хода коня. Оказываясь в очередной клетке, конь собирает все яблоки, которые в ней находятся. Имеется ограничения на количество ходов. Ваша программа должна принимать на вход следующие аргументы: максимальное число ходов, имя файла, содержащего схему заполнения шахматной доски яблоками. Строки в файле соответствуют строкам шахматной доски, строки разделяются переносами. Числа в строках разделяются пробелами. Ваша программа должна вывести максимально возможное количество собираемых яблок конем, при заданном ограничении ходов и произвольном выборе начальной позиции.

Собственно, хотелось бы понять, каким образом/методом следует решать эту задачу. Сам код мне, конечно, нужен, но думаю и сам смогу написать программу, если пойму её основную идею. Была идея решать через жадный алгоритм, передвигаясь в клетку, содержащую в себе максимально возможное число яблок (сравнивал количество яблок в каждой из клеток, доступных в данный момент и шел в клетку с максимальным числом), но, как мне кажется, это решение, мягко говоря, не совсем верное. Задача должна содержать в себе рекурсию. Подайте идею решения данной проги или посоветуйте литературы по этой теме, пожалуйста. Заранее благодарю! :D

c# алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 7Принят

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

Специалисты могут решат задачу другим способом. Шахматная доска для коня - это граф. Кол-во яблок в клетке - это значение в вершине. Задача сводиться к поиску цепочки с максимальной суммой. В теории графов есть много алгоритмов для поиска кратчайшего пути, но думаю, они легко "перевернутся".

▲ 4

Ну и, помимо упомянутого графа, так же стоит добавить, что Ваш вариант с жадный алгоритмом неверен. Просто потому, что путь 2-1 даст меньше, чем путь 1-9, который будет проигнорирован подобным жадным алгоритмом.

Стоит заметить, что конь ходит в любую точку доски за 4-5 ходов, поэтому хороший граф будет очень запутанным в данной задаче и достаточно сложен в построении и анализе. Поэтому, для упрощения можно воспользоваться его частным видом - неориентированным восьминарным (по числу ходов коня) деревом высотой в ограничение ходов коня.

▲ 1

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