Разминка для моска.

[ASokol]

Разминка для моска.

Взял из начального задания конкурса Посилання видалено.

Минимальный штраф
Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).
Известно, что 1 <= n <= 1000, 1 <= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 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

input.txt
3 1
3
4
1

Соответствующие выходные данные:

output.txt
8
4 1 2 1

output.txt
8
3 4 1

 

[solor2001]

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

 

[Therion]

Надо найти путь с самым минимальным штрафом во всей матрице или просто пройти с минимальным штрафом из конкретной начальной в конечную позицию?

 

[ASokol]

Да не парься: это явно не для тебя задача.

 

[Prior]

Когда-то давно делал курсовой на паскале похожий.
Однонаправленные графы, если мне не изменяет память, это называется. Довольно интересная задачка.

 

[Orshansky]

Взял из начального задания конкурса Посилання видалено.

Минимальный штраф
Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).
Известно, что 1 <= n <= 1000, 1 <= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 1.

Это частный случай задачи коммивояжёра. Выбирайте любой быстрый алгоритм ее решения.

 

[Shwartz]

Я вижу достаточно простое решение. Со второй по последнюю строчку проделываем следующие дейтвия. Для каждой клетки пишем минимальный штраф, с которым можно в нее прийти (выбрать из трех вариантов или двух - для крайних) и запоминаем направление. после этого выбираем в нижней строке минимальное число и восстанавливаем обратное направление. Потребуется порядка 3*m*n сравнений. Или можно изначально идти снизу вверх, тогда в конце не придется переворачивать результат.

 

[Mr. Q]

Shwartz
а если все соседние клетки имеют одинаковый штраф? или чтобы пройти минимальный путь, нужно сначала пройти через клетку с самым большим штрафом?
можно решать методом ветвей. без рекурсии вряд ли, но есть эвристические методы, оптимизирующие решение.

 

[Shwartz]

Shwartz
а если все соседние клетки имеют одинаковый штраф? или чтобы пройти минимальный путь, нужно сначала пройти через клетку с самым большим штрафом?
можно решать методом ветвей. без рекурсии вряд ли, но есть эвристические методы, оптимизирующие решение.

Возможно я не совсем ясно изложил свою идею. Не нужно здесь никаких рекурсий, иначе решения задачи разве что внуки дождутся (при размере 1000x1000). Предложенный мной вариант найдет самый оптимальный вариант, но возможно, что будет еще один или несколько вариантов с тем же штрафом. Если соседние клетки имеют одинаковый штраф (я подразумиваю минимальный суммарный штраф, с которым можно в нее прийти), то выбираем любой из них.

 

[Sefiroth]

Самое очевидное - динамика.
Как вариант - перелопатить Дейкстру/А*. Он ищет кратчайшие пути из одной клетки во все.

PS: Не забывайте, что любую рекурсию можно заменить циклом. )

 

[Mr. Q]

Shwartz
я ж о том и говорю: ваш вариант выберет любой из них, а этот любой, в итоге, может оказаться не оптимальным.

 

[Orshansky]

PS: Не забывайте, что любую рекурсию можно заменить циклом. )

Бред. Сведите к циклу функцию Аккермана!

К циклу сводится только хвостовая рекурсия. Существует класс примитивно-рекурсивных функций которые можно свести к хвостовой рекурсии. Но существет ряд общерекурсивных функций, которые невозможно свести к циклу, одной из таких общерекурсивных функция является функция Аккермана.

 

[Shwartz]

...а этот любой, в итоге, может оказаться не оптимальным.

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

Как же мне еще объяснить решение? Когда вы рассматриваете очередную клетку, у вас есть три варианта как в неё прийти и понятное дело нужно выбрать самый выгодный. До самого конца не известно где пройдет оптимальный путь, но на каждом шаге известно как прийти в клетку с наименьшим штрафом. Для первой строки все просто - суммарный штраф состоит только из штрафа в самой клетке - другого не дано. Для всех последующих строк суммарный штраф складывается из минимального суммарного штрафа из верхней клетки (выбираем наименьший из трех) плюс штраф в ней самой. Что из этого не понятно?

Сложность задачи возросла бы многократно, если бы начало и конец были зафиксированы.

 

[Orshansky]

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

Как же мне еще объяснить решение? Когда вы рассматриваете очередную клетку, у вас есть три варианта как в неё прийти и понятное дело нужно выбрать самый выгодный. До самого конца не известно где пройдет оптимальный путь, но на каждом шаге известно как прийти в клетку с наименьшим штрафом. Для первой строки все просто - суммарный штраф состоит только из штрафа в самой клетке - другого не дано. Для всех последующих строк суммарный штраф складывается из минимального суммарного штрафа из верхней клетки (выбираем наименьший из трех) плюс штраф в ней самой. Что из этого не понятно?

Сложность задачи возросла бы многократно, если бы начало и конец были зафиксированы.

Ну так реализуйте ваш алгоритм на С/С++/Java/псевдокоде, а я уже подготовил вам контр-пример на котором ваш алгоритм будет выдавать неоптимальный маршрут

 

[Shwartz]

я уже подготовил вам контр-пример на котором ваш алгоритм будет выдавать неоптимальный маршрут

Мне код писать лень, тем более на не используемых мной языках. Если пример небольшой, то я пошагово распишу работу алгоритма на нём.

 

[Orshansky]

Мне код писать лень, тем более на не используемых мной языках. Если пример небольшой, то я пошагово распишу работу алгоритма на нём.

Вы уже написали столько сообщений и с завидным упрямством доказываете правильность своего даже не реализованного алгоритма!

Напишите на псевдокоде! Я реализую на С.

 

[Mr. Q]

поддерживаю человека с интересным ником Orshansky.

 

[Shwartz]

В общем, не совсем псевдокод, но напишу все необходимое для реализации.

Для решения понадобится еще две матрицы n x m:
* Fee - суммарные штрафы
* Ind - индексы, указывающие предыдущую клетку (по горизонтали, так как по вертикали всегда на единицу меньше текущего)

Первую строчку копируем из A в Fee без изменений.

Далее рассматриваем все клетки, начиная со второй строки слева-направо и сверху-вниз (не обязательно, но так проще для понимания).


Так бы я никогда не написал, но описать процесс так проще:

Для i = 1..n
  Для j = 0..m
    // тут придется еще дописать, чтобы рассматривать всего две клетки на крайних
    Если a[i - 1, j - 1] < a[i - 1, j] < a[i - 1, j + 1]
      Ind[i, j] = j - 1;
    Если a[i - 1, j] < a[i - 1, j - 1] < a[i - 1, j + 1]
      Ind[i, j] = j;
    Если a[i - 1, j + 1] < a[i - 1, j] < a[i - 1, j - 1]
      Ind[i, j] = j + 1;
    Fee[i, j] = A[i, j] + Fee[i - 1, Ind[i, j]]

После этого выбираем в нижней строке матрицы Fee минимальное число и восстанавливаем оптимальный маршрут - для этого есть матрица Ind. Тут я уже не стану писать, как это сделать, думаю, и так понятно.

 

[Тыемураз]

Да не парься: это явно не для тебя задача.

На проекте Украина мае талант,который пройдет по Харькову 14 листопада я видел в списках заявленных участников подобную задачу
от некоего Переперделкина Сокола Прямодуевича.
Не вы ли это,достопримечательный ASokol?

 

[ASokol]

Уважаемый бот Тыемураз, к сожалению, к Переперделкину Соколу Прямодуевичу (не менее уважаемому) я не имею ни малейшего отношения. Может сгенеришь какой-нить хитрый алгоритм выбора маршрута?