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

#c #алгоритм

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

Ответы

Ответ 1

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


Ответ 2

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


Ответ 3

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