Cool Folders ® :: Форум Игротека :: алгоритмическая задача

алгоритмическая задача

Автор: Урод и мразь
Дата : 14-11-04, Вск, 08:29:43

N индейцев решили выйти на охоту за скальпами. У них есть M томогавков (M >= N). Индеец i, вооруженный томогавком j, может добыть A[i,j] скальпов. Написать программу, которая, получив массив А, максимизирует общее число скальпов. Каждый индеец должен получить ровно один томогавк, и делить один и тот же томогавк между разными индейцами нельзя.

Есть ли полиномиальный алгоритм?

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"

алгоритмическая задача

№ 2

Автор: Tarlog
Дата : 14-11-04, Вск, 13:15:58

Очень тупой, полиномиальный алгоритм. Возможно я чего-то не понял.
Итак даешь самому крутому индейцу, самый крутой томогавк O(M*N).
Теперь из оставшихся индейцев и томогавков выбераешь самых крутых O(M*N)
И так далее, в общей сложности получается O(M*N*N)=O(M^3) - полиномиальное решение.

алгоритмическая задача

№ 3

Автор: Урод и мразь
Дата : 14-11-04, Вск, 13:53:23

Простой контрпример.

A[0,0]=3 A[0,1]=2
A[1,0]=2 A[1,1]=0

Даёшь самому крутому индейцу самый крутой томогавк - индеец 0 получает томогавк 0.
Теперь из оставшихся индейцев и томогавков выбераешь самых крутых - индеец 1 получает томогавк 1. В итоге 3 скальпа.

Правильное решение - индейцу 0 дать томогавк 1, а индейцу 1 - томогавк 0 (4 скальпа)

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"
[ 14-11-04, Sun, 20:54:34 Отредактировано: Урод и мразь ]

алгоритмическая задача

№ 4

Автор: Tarlog
Дата : 14-11-04, Вск, 14:03:03

Ага, мне тоже показалось, что-то не то...

Щас еще подумаю.

алгоритмическая задача

№ 5

Автор: Tarlog
Дата : 14-11-04, Вск, 14:18:08

Тьфу тебя, с дурацкими задачами. Миллион не заработаешь

Я в нее сделал редукцию из задачи "Сохен-носеа", а значит полиномиального решения скорее всего нет.
Зато есть алгоритм идетерминисти, а значит задача в NPC.
Короче если решу, то миллион мой!

алгоритмическая задача

№ 6

Автор: Урод и мразь
Дата : 14-11-04, Вск, 14:24:25

Задача коммивояжера NP-полная. А как задача коммивояжера сводится к этой?

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"

алгоритмическая задача

№ 7

Автор: Tarlog
Дата : 14-11-04, Вск, 14:31:07

Задача коммивояжера это та же матрица M на N, только с ценами. Тебе надо найти самый дешевый вариант. Ну а в твоей задаче ишешь самый дорогой. Кажись разницы нет. Или есть?
А меня computability был самый ненавистный курс

[ 15-11-04, Mon, 6:43:48 Отредактировано: Tarlog ]

алгоритмическая задача

№ 8

Автор: Урод и мразь
Дата : 14-11-04, Вск, 14:46:11

В задаче коммивояжера тоже есть матрица, но задача совершенно другая.

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"
[ 14-11-04, Sun, 21:46:46 Отредактировано: Урод и мразь ]
[ 14-11-04, Sun, 21:46:57 Отредактировано: Урод и мразь ]

алгоритмическая задача

№ 9

Автор: Большой Грызь
Дата : 14-11-04, Вск, 23:25:55

А меня computability был самый ненавистный курс

у меня тоже...

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

алгоритмическая задача

№ 10

Автор: Урод и мразь
Дата : 15-11-04, Пнд, 07:39:04

Это задача из олимпиады по программированию, не знаю - для школьников или студентов.

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"

алгоритмическая задача

№ 11

Автор: Лапоть
Дата : 15-11-04, Пнд, 07:46:57

Можно тупо посчитать минорами, но O(n!). Я ещё подумаю...

Bозможно Бог не любит вас. Может быть, Господь даже ненавидит нас всех. Но это не худшее из того, что могло бы произойти.

алгоритмическая задача

№ 12

Автор: Урод и мразь
Дата : 15-11-04, Пнд, 08:07:53

Автор: Большой Грызь
Дата : 15-11-04, Mon, 6:25:55
А меня computability был самый ненавистный курс

у меня тоже...

А у меня один из любимых.

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"
[ 15-11-04, Mon, 15:20:52 Отредактировано: Урод и мразь ]

алгоритмическая задача

№ 13

Автор: Lisopoval
Дата : 15-11-04, Пнд, 08:41:43

(примечание - разделом будем называть сочетание N пар (i, j), харакетеризуеещее один из возможных вариантов раздачи одного из M томагавков (j) каждому из N индейцев (i); качеством раздела назовем сумму конкретных пар отдельно взятого раздела, т.е. кол-во скальпов, добываемых при данном разделе дикарями)

Кол-во возможных комбинаций разделения томагавков при M>=N:
M!/(M-N)!

Стоимость подсчета качества одного конкретного раздела томагавков:
O(N)

На каждый вариант раздела подсчет качества необходим, т.к. ни один из возможных вариантов а-приори не может быть отсечен (вдруг последняя из пар в этом разделе попадёт на такое значение А(i,j), которое самый некачественный раздел превратит в самый качественный). Следовательно, нахождение лучшего варианта раздела (без дополнительных к условиям допущений) неизбежно требует оценки качества (O(N)) каждого из возможных вариантов (коих M!/(M-N)!), и его стоимость будет O(N*M!/(M-N)!).

Однако: подсчет качества можно вести по ходу дела, так что к момену формирования каждого раздела его качество уже будет подсчитано. Это сокращает решение ровно в О(N) раз, что оставляет никак не меньше О(M!/(M-N)!). Я ничего не упустил?

Судите сами, насколько полиномиально это решение. И, как я уже сказал, дешевле не существует в границах приведенных условий задачи.
______________________________________

______________________________________________
"Ёльки-пальки! - сказал Иосыф ВИссарионович СтАлин, когда впервие увидел ЛIСОПОВАЛ"
[ 15-11-04, Mon, 15:43:26 Отредактировано: Lisopoval ]
[ 15-11-04, Mon, 16:01:14 Отредактировано: Lisopoval ]

алгоритмическая задача

№ 14

Автор: Урод и мразь
Дата : 15-11-04, Пнд, 09:40:29

Не доказано, что дешевле не существует.

> вдруг последняя из пар в этом разделе попадёт на такое значение А(i,j), которое самый некачественный раздел превратит в самый качественный

Неявно предполагается, что мы перебираем пары, причём перебираем тупо.

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"

алгоритмическая задача

№ 15

Автор: lev bulochkin
Дата : 15-11-04, Пнд, 16:49:04

Что такое "computability" не знаю,
поэтому мы с Чингачгуком решали так:
Строим N индейцев вдоль реки, раскладываем M томагавков на песочке поперек.
Рисую матрицу N(индейцев) x M(томагавков). На пересечениях кладем соответствующее число скальпов.
Дальше первый индеец идет вдоль своего столбца, выбирает лучший томагавк и подсчитывает относительный выигрыш: на сколько скальпов этот Т (для меня) лучше любого другого, а потом - вдоль строки - считает коллективный проигрыш: на сколько скальпов этот Т принес бы больше в других руках.
Если выигрыш больше проигрыша - берет оружие и оба выходят из игры. Если нет - переходит ко второму по качеству Т и т.д. пока не минимизирует проигрыш.
Следующий, естественно, делает то же самое.
Я предполагаю (но не доказал), что число скальпов будет максимальным,
явно есть экономия перебора по всем возможным вариантам.
Важно подчеркнуть условия:
1)число скальпов не может быть отрицательным,
2)нет "крутых томагавков" - один и тот же может быть и хорошим, и плохим - в разных руках.

Можно ли считать это решением и лучше ли оно перебора всех вариантов?

..Нет-нет!Не надо сразу соглашаться! Давайте лучше подумаем...

алгоритмическая задача

№ 16

Автор: Lisopoval
Дата : 15-11-04, Пнд, 20:35:19

УиМ - не явно и не неявно ничего про перебор пар нет, иначе бы ты увидел M*N.

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

______________________________________________
"Ёльки-пальки! - сказал Иосыф ВИссарионович СтАлин, когда впервие увидел ЛIСОПОВАЛ"

алгоритмическая задача

№ 17

Автор: Сергуня
Дата : 15-11-04, Пнд, 21:44:26

Автор: lev bulochkin
Дата : 15-11-04, Mon, 23:49:04

Если выигрыш больше проигрыша - берет оружие и оба выходят из игры. Если нет - переходит ко второму по качеству Т и т.д. пока не минимизирует проигрыш.

Допустим лучший томагавк ему приносит 10 скальпов, а кому то 8, выигрыш - 2,
А второй по качеству томагавк ему принес бы 7 скальпов, но остальным максимум 4, выигрыш - 3. Надо мозговать. По моему без полного перебора хоть как не обойтись.

алгоритмическая задача

№ 18

Автор: Сергуня
Дата : 15-11-04, Пнд, 21:45:41

Как то не так отправил

Прошу прощенья.

алгоритмическая задача

№ 19

Автор: Урод и мразь
Дата : 16-11-04, Втр, 07:24:16

Lisopoval :

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

Вот это утверждение и не доказано. Причем если ты его докажешь, и этого будет следовать, что полиномиального алгоритма к данной задаче нет. Поскольку задача из NP, ты тем самым докажешь, что P != NP. Не думаю, чтобы это получилось

Эвристики, сокращающие перебор, есть, я потом напишу.

Сергуня:

> число скальпов не может быть отрицательным
Да.

> нет "крутых томагавков" - один и тот же может быть и хорошим, и плохим - в разных руках.
Могут и быть.

Если первое слово Гагарина было: "Поехали!", то последнее слово Икара - "Приплыли!"

алгоритмическая задача

№ 20

Автор: Lisopoval
Дата : 16-11-04, Втр, 12:19:28

Ок, давайте думать коллективно. Вчера ночью на трассе было пол-часа, подумал, и пришел к выводу, что таки есть эвристики. Как минимум одна.

Сильно "отстающие" комбинации можно вырубать уже на ранней стадии, когда ясно, что за оставшиеся шаги нельзя набрать достаточно, чтобы перекрыть лучший вариант. Как? А вот как:

Для каждого отморозка (i) находим для всех возможных топоров (j) значение отставания от лучшего топора для данного отморозка (max[i=const,0<=jj<M](A(i,jj)) - A(i,j)), и пришпиливаем это значение к каждой паре (i,j) - B(i,j) (Разумеется, лучший топор для данного отморозка сам получит значение B(i,jj)=0). Этот алгоритм включает серию сортировок и несложно доказать, что он полиномиальный.

Далее, начинаем "умно" перебирать, начиная от самого удачного для каждого дикаря (минимальный B(i,j), сначала 0, потом 2-й минимум, потом третий и т.д.). Каждый выбор, разумеется, вычеркивает данный томагавк для выбора другим претендентом. Если накопившийся штраф (сумма отставаниий B(i,j) от начала комбинации) превышает этот же у лучшего из законченных комбинаций, то данная комбинация херится на месте без продолжения.

Ясно, что лучшая комбинация будет среди первых, а чем дальше от оптимального, тем скорее будут убиваться на раннем этапе бесперспективные комбинации.

Все элементы алгоритма полиномиальные, кроме самого перебора - тут вопрос, как посчитать эффект от оптимизации на кол-во пермутаций. Если еще пол-часа поездить, думаю, это можно будет решить.

______________________________________________
"Ёльки-пальки! - сказал Иосыф ВИссарионович СтАлин, когда впервие увидел ЛIСОПОВАЛ"

алгоритмическая задача

№ 21

Автор: lev bulochkin
Дата : 16-11-04, Втр, 16:13:22

Уважаемый Сергуня,
Вы соверили две ошибки в толковании индейского метода:
2)Обсчет второго по качеству томагавка должен начинаться с потери 3 скальпов относительно первого, так что коллективный выигрыш на нем равен нулю, а не трем.
1)И самое главное: Если первый, самый лучший, дает абсолютный выигрыш (2,или 1,или даже 0)-
то НИКТО НЕ БУДЕТ ОБСЧИТЫВАТЬ ВТОРОЙ. Берем первый и идем воевать без всяких полиномиальных пермутаций!

Максимальныое Число обсчитываемых "раздач":
MxN + (M-1)x(N-1) + (M-2)x(N-2) + (M-3)x(N-3) + ...+ (M-N)x0 .

..Нет-нет!Не надо сразу соглашаться! Давайте лучше подумаем...
[ 16-11-04, Tue, 23:34:21 Отредактировано: lev bulochkin ]
[ 16-11-04, Tue, 23:38:26 Отредактировано: lev bulochkin ]

алгоритмическая задача

№ 22

Автор: Lisopoval
Дата : 17-11-04, Срд, 05:20:20

Лев, контрпример:

A[0,0]=4 A[0,1]=2
A[1,0]=3 A[1,1]=0

Относительный выигрыш 2 = 4 - 2
Коллективный проигрыш -1 = 3 - 4
2 > -1, стало быть первый индеец берет первый топор, а второй берет 2-й, в сумме добывают 4 скальпа, а могли бы 5 при другом раскладе.

______________________________________________
"Ёльки-пальки! - сказал Иосыф ВИссарионович СтАлин, когда впервие увидел ЛIСОПОВАЛ"

алгоритмическая задача

№ 23

Автор: Урод и мразь
Дата : 30-01-05, Вск, 00:55:22

Мне сказали, что есть полиномиальный алгоритм.

Не играйте с пианистом - он стреляет, как умеет.

алгоритмическая задача

№ 24

Автор: DimaS
Дата : 25-06-05, Сбт, 02:02:47

Ясен палец, есть...
(кстати типичная задача для нахождения maximum flow)
Значится так:
1) Создаем N узлов, каждый узел помечаем номером от Ind1 до IndN
2) Создаем M узлов, каждый узел помечаем номером от Tom1 до TomM
3) Создаем узел S (source), Т (sink)
4) Соединяем узел S с узлами помеченными цифрами от Ind1 до IndN. Даем каждому такому edge infinite capacity.
5) Соединяем каждии узел Indi со всеми узлами Tomj, где 1<=j<=M. Каждому такому edge даем capcity А[i,j]
6) Соединиам узлы ,помеченные тсифрами от Том1 до ТомМ с узлом Т. Каждому такому edge даем capcity infinite

Запускаем алгоритм Едмондс-Карп ( Томас Кормен ,Algorithms, part 27 ) - находим maximum flow с complexity O(VE^2) = O( (M+N+2)*(M*N)^2) = O(M^3 * N^2) - polynomial