|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
12.10.2009, 16:13 | #1 |
Регистрация: 12.10.2009
Сообщений: 4
|
Подскажите в какую сторону думать )
Вот незнаю в каком направлении мне думать Коды писать не обязательно, просто подскажите пожалуйста способ(сам алгоритм) или на что обратить внимание.. Вот условие:
Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо). (с ниже описанным я сам справлюсь, просто дал для примера) Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов. Примеры входных данных input.txt 4 5 3 2 8 6 4 4 7 12 9 1 55 8 3 2 8 20 7 4 9 1 Соответствующие выходные данные output.txt 8 4 1 2 1 |
12.10.2009, 16:26 | #2 |
Старожил
Регистрация: 06.08.2009
Сообщений: 2,992
|
Нужна рекурсия.
Должна быть глобальная переменная с минимальным штрафом. Рекурсивная функция принимает на входе текущую координату и запускает себя 3 раза. Если координата - последняя, то сравниваем получившийся штраф с минимальным. |
12.10.2009, 17:07 | #3 |
Регистрация: 12.10.2009
Сообщений: 4
|
Вот!.. ) Спасибо огромное за четкий ответ.. Жаль что я сам не додумался(( Еще раз спасибо!
|
12.10.2009, 18:53 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Рекурсия - зло. Запомните это.
В данной задаче нужно использовать ДП за О(n*m) (на матрице значений). Потом просто выбираем минимальное из значений в искомой строке матрицы за O(n). По поводу вывода пути - самым оптималыным мне кажется массив указателей, но здесь есть разные мнения. |
13.10.2009, 01:20 | #5 |
Регистрация: 12.10.2009
Сообщений: 4
|
LeBron, то что рекурсия зло я знаю. Но нахожу в ней самый оптимальный вариант для этой задачи.. Ибо твой путь решения я не совсем понимаю, не так я опытен в этом. Если не сложно, можешь объяснить? Мне было бы интересно знать еще один путь решения данной задачи. (хотяб поверхностно)
|
13.10.2009, 08:51 | #6 |
Старожил
Регистрация: 06.08.2009
Сообщений: 2,992
|
|
13.10.2009, 17:10 | #7 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Объясняю. При небольших ограничениях рекурсия, возможно, самый оптимальный варант для тех, кто ее любит и умеей быстро и качественно ею пользоватся. А для более-менее приличных ограничений - не прокатит. Мое решение (оптимальное) работает в пределах секунды и для ограничений 1000*1000. А рекурсия красиво и громко упадет. Первое - это само количество операций. Если говорить об неоптимизированной и простой для понимания функции, то вообще завал - каждая не крайняя ячейка (я так для себя клетку массива назвал, в рекурсии это как-то лучше звучит) первой строки порождает 3 функции, каждая из этих 3 порождает еще 3 во второй ячейке, и так далее. Понятно, что работать это будет дольше по времени, так как уже во втором ряду на обработку некрайних ячеек идет больше операций, чем при линейно организированном решении. Вообще, в ряду с большим номером на любую ячейку уйдет минимум 6 запросов - так как она будет вызвана из 2 клеток, верхней и верхней боковой (если не крайняя - таких боковых будет 2), а если еще и учесь, сколько раз эти клетки будут вызваны... Рост ведь ограничевается ниже экспоненицального только краями массива.
Второе - память. Мне жалко тот стек, который будет убит такой рекурсией. Ее, конечно, можно оптимизировать. Подозреваю даже, что если оптимизировать в полупрерывный бэктрекинг, то будет укладыватся в оптимальные ограничения. Только вот это уже не будет чистая "голая" рекурсия, и сама задача построения такого алгоритма на порядок сложнее. |
13.10.2009, 17:22 | #8 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Теперь объясняю динамическое решение. Заводим еще 1 массив. Можно и на этом все делать, не юзая лишнюю память, но для начале лучше тренироватся делать такие стандартные задачи на динамику стандартным методом с заведением отдельного массива. Каждому элементу в массиве на входе будет отвечать в нашем новом массиве значение минимальной суммы, которую можно набрать, пройдя через эту клетку. Теперь начинаем заполнение. Понятно, что минимальные штрафы для клеток первой строки - это само значение этой ячейки массива. Для второй и последующих строк каждой ячейке присваиваем сумму ее значения в начальном массиве и минимального из значений тех ячеек массива сум, из которых можно перейти в эту ячейку. Потом просто в последней строке выбираем минимальное значение. Извлечение пути - с помощью массива указателей пути.
Пример: 3 2 8 6 4 6 9 14 13 5 61 17 12 7 13 - так, если не ошибаюсь (считал "на глаз") будут выглядеть 3 первые строки массива сум для инпута из примера. |
13.10.2009, 18:50 | #9 |
Старожил
Регистрация: 06.08.2009
Сообщений: 2,992
|
LeBron, такой вариант, вероятно, оптимальнее, но и значительно сложнее. После небольшой практики в 9-м классе я больше никогда не путался в рекурсии. А на счет стека - верно замечено.
:) |
13.10.2009, 19:13 | #10 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Эх... сложнее - это когда читаеш разбор задачи и не понимаеш в нем половины символов. Здесь десяток строк кода... И если человек собирается в будущем заниматся программированием дальше, то ему надо уметь решать такие базовые задачи, которые чаще выступают как подзадачи при решении натоящих задач, правильно. А рекурсия сдесь займет минимум 50-70 строк, так что не вопрос, что проще. Ну разве что, опять таки, говорить в очередной раз о "пародии на решение" - полном рекурсивом переборе, который загибается даже быстрее, чем кажется. Проверил програмно - уже при массиве 20*20 (ни об учебных 100*100, ни об соревновательных 1000*1000 речь не идет) на центральные элементы последней строки будет по 1155067303 запросов.
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Подскажите чайнику(мне) какую прогу написать? | BETONOMESHALKA | Свободное общение | 23 | 26.10.2011 12:27 |
Остановился в развитии, направьте в какую сторону идти дальше! | iukash | Свободное общение | 43 | 02.09.2009 19:16 |
Подскажите, какую программу выбрать... | Лена Брусникина | Помощь студентам | 0 | 19.06.2009 21:10 |
Подскажите пожалуйста какую функцию необходимо использовать... | Андрю)(@ | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 10.12.2008 00:03 |
Подскажите пожалуйста какую функцию необходимо использовать... | Андрю)(@ | Помощь студентам | 1 | 09.12.2008 23:53 |