Задали написать программу или веб-приложение, решающее следующую задачу (скрин): 

Реально ли уложиться в условие - время выполнение 10 сек? 
Язык - желательно php, поэтому здесь и пишу... Однако, возможно и на С/С++
Натолкните на идею, если такую задачу можно решить     

Если переведешь на русский, то наверняка появятся куча советов, как решить задачу

Задача М. Эффективный процесс.

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

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

что обозначают условия запуска подпроцесса: если, например, стоит условие "-5", то это значит что подпроцесс должен быть запущен перед подпроцессом №5, а положительное число - подпроцесс должен быть запущен после подпроцесса с указанным номером.

Воник вопрос, запускаем мы 6й процесс который совместим с 3м.

На втором шаге мы запускаем 3й процесс, который совместим с 6.

На третем шаге что? Другие процессы не совместимы? Ждем ?

Если ждем, тогда о каких нарушениях идет речь в условиях? Если не ждем, то нарушаем процесс ? или как?

awdev, 
условия: (-8) - процесс должен быть запущен после 8-го, (5) - перед 5-м. 

На совместимость можно забить, проверял вручную, что с ней, что без нее, результаты те же. то есть, суть в том, чтобы выбрать все числа из диапазона 12345678-88888888, в которых нет нарушения условий совместимости, и потом  с ними уже посчитать показатель эффективности...
но перебор банальным for($i=12345678; $i<88888889;$i++){}
это зло, в 10 сек не уложится ни за что...

NFL, 
у тебя 8! перестановок с учетом ограничений еще меньше.
Цикл тебе нужен по перестановкам. И 40к комбинаций уложить в 10с более чем реально

Simpliest, пример можно?  что то туплю...

12345678
21345678
23145678
...
87654321

Simpliest, не... я о примере кода, как регулярку или что прописать?
чтоб получить, например, массив или еще что то из нужных мне значений... 
зы: делаю без повторений, тоесть, 40320 комбинаций надо перебрать...

Не совсем ясны условия задачи.
1. То что подпроцессы могут быть совмещены по времени - это означает, что совместимые подпроцессы могут быть запущены одновременно (т.е. суммарное время их выполнения всегда равно max(T1, T2))? Или же все-таки учитывается  условие, что подпроцесс может быть запущен не ранее чем через 1 ед. времени (т.е. суммарное время max(T1,T2+1) или max(T2,T1+1) в зависимости от порядка)?
2. Условие запуска означает, что подпроцесс должен быть выполнен непосредственно перед/после указанного подпроцесса? Или же между ними могут быть выполнены другие подпроцессы без нарушения условия процесса?
3. Могут ли быть взаимнопротиворечащие друг другу условия? Т.е. когда в принципе невозможно завершить процесс без нарушения хотя бы одного условия?
4. Пример в задаче какой-то совсем абсурдный, даже если исправить опечатки и предположить, что взаимнопротиворечащие условия возможны, то все равно как не крути, но эффективность 3.4 для первой строки и 3.3 для второй ну никак не получается.


Это не интересно  


Я думаю, что тут суть не в том, что бы уложить решение задачи во времени в 10с, а в том, что бы найти более оптимальный алгоритм, нежели полный перебор всех возможных вариантов.

Это сообщение отредактировал(а) sTa1kEr - 2.12.2009, 00:57

sTa1kEr, 

1.  max(T1,T2+1) или max(T2,T1+1
2. Нет. Главное, чтобы именно перед или после.
3. Нет
4. Ну у меня 3.4 получилось, а 3.3 тоже никак(

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

NFL, 
Найти все комбинации

Добавлено через 1 минуту и 58 секунд

Не прикалывайся. 
Я за свою недолгую жизнь не смог придумать ни одного нового алгоритма. Максимум заново открывал уже существующие.

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

Добавлено через 2 минуты и 26 секунд

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

Не всех возможных, а всех разрешеных.

Но, да.
Для задачи "найти оптимальный вариант из всех комбинаций", полный перебор будет единственным вариантом.

Разрешены абсолютно все комбинации.


Да неужели? Я уже вижу как можно решить задачу с перебором в лучшем случае только двух вариантов  

Это сообщение отредактировал(а) sTa1kEr - 3.12.2009, 07:26

Если задача все-таки в переборе всех перестановок, то вот класс, реализующий интерфейс Iterator

Использование:


Добавлено через 8 минут и 52 секунды
Плюс класса в том, что никакого массива реально не создается, но значения можно получить по порядку.
Если увидите косяки, сделайте замечания, писал, чтобы размяться

Добавлено через 5 минут и 5 секунд
Нет, класс грамотно написан. Просто метод полного перебора тут ну никак не подходит.

Добавлено через 8 минут и 13 секунд
Хотя операций с массивами что-то многовато...

да вы гоните.

Нет, тут однозначно проще при помощи рекурсии перебор делать.

Добавлено через 1 минуту и 12 секунд

Это результат, который получился на моем компе. Класс NewDima я скопировал один в один.

Да я вроде как не возражаю. 
Но такие результаты - значит конкретная реализация не годится.
Блин, сейчас сяду посмотрю

Не понял, почему 40300
результат
40320:2.52513289452 
Вполне сносный результат

Так, ну во-первых, этот же код у меня выполнился за  
40300
OK.  2.217719078064

sTa1kEr, что у тебя за машина?

Во-вторых, буду смотреть дальше.

Core 2 Duo E8500 3,16Ghz 3,25 ОЗУ

потому что у него данные выводятся каждые 100 тактов цикла

Полагаю, какие-то методы ведут себя по-разному в разных версиях php?
У меня правильное количество результатов и я их посматривал 

Добавлено через 14 секунд
Понял, не заметил

Вот мой вариант на скорую руку:


Это сообщение отредактировал(а) sTa1kEr - 5.12.2009, 15:16

Completed. 40320 iterations. 0.307599067688 sec

AMD Athlon™ X2 Dual Core Processor BE-2400 Вообще-то у меня netbeans компилиться  

Но это все не имеет значения, т.к.
1. Мы не знам на каком компе будет выполнятся программа, вполне вероятно, что задача составлялась когда еще БК'шки были
2. Преподаватель всегда может сказать: "ну ок, а теперь сделай то же самое для 12 процессов"

Добавлено через 9 минут и 43 секунды
Блин, AMD - ### =\

sTa1kEr, сижу и не могу сообразить, как вашим скриптом вывести генерируемые значения по порядку?

Соррь, не большой баг. Не подумал, что array_merege объединяет по ключу

Добавлено через 2 минуты и 46 секунд
Исправил 
bruteforce($array, $result + (array)$n);
на 
bruteforce($array, $result + array($n => $n));

Мне удалось согнать мой вариант только до 1.60964894295 =(

Добавлено через 28 секунд
при вашем 0.521440029144 

Все это фигня. Там сам подсчет эффективности достаточно замороченный 

Добавлено через 7 минут и 20 секунд

Раз так, то я тоже оптимизировал слегка  
1. Убрал статическую переменную
2. Вынес в переменную count($array)
3. Поменял местами if и for, что бы сэкономить на проверке внутри цикла
4. Заменил счетчик мз цикла $total++, на $total += $count вне цикла.. Был не прав. В связи с п.3 - это уже не нужно, заменил на return $count; Почему не на return 1? Можно было бы и так, но в случае return $count PHP не придется создавать дополнительную переменную, что бы вернуть 1.
Я тормоз... Там вообще цикл не нужен... Все, теперь конечный вариант.

Итого:



NewDima, если не сложно, проверь какой теперь у тебя результат?

Добавлено @ 15:59

Извини, не понял, что ты этим хотел сказать?

Добавлено @ 16:01

Из-за этого бага, если разкомментировать echo, выводилось только последние 2 цифры.

Это сообщение отредактировал(а) sTa1kEr - 5.12.2009, 16:12

отлично   
Completed. 40320 iterations. 0.249315023422 sec

Добавлено через 1 минуту и 50 секунд
В моем варианте время выполнения скрипта растет просто бешеными темпами при увеличении размера массива, так-что какашка у меня=(

Еще одно место оптимизировал, убрал второй цикл   

Все, больше не знаю, что еще можно оптимизировать... Если увидите, скажите  

я про рассчет эффективности комбинации согласно задаче ТС 


Я дал профайлинг. посмотри методы которые вызываются по 273к раз
один из них сортировка 

Все... вот последняя экстримальная оптимизация за счет уменьшения рекурсии на 2уровня и ухудшения читабельности   :
Так


Добавлено через 5 минут и 46 секунд
Да... этот метод даже на моем тормазнутом AMD'шнике меньше секунды выполняется...
Но это все равно не true way!   

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

Бггг, я же говорил 

Simpliest, что то тему прочитал видимо невнимательно  
ща перечитаю  

В общем, я от нечего делать добил твою задачу  Комментировать было лень




Если использовать вместо класса Sub массив, то можно увеличить производительность на ~20-30%

Можно будет на досуге решить ее алгоритмом без перебора.

sTa1kEr, спс огромное, преподу хватит      

Пара не очевидных моментов:

Sub::$depends - это процессы, которые по условию должны предшествовать текущему процессу
Sub::$bonus - это время, которое мы экономим, если предшествует совместимый процесс
Process:$nominalTime - это время, затрачиваемое на процесс без учета совместимости процессов

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

Добавлено через 1 минуту и 18 секунд

Я не для препода ее решал, а для себя  Так сказать разминка для мозгов  

sTa1kEr,     

да ну его, для себя такие задачи решать, никому не нужные  

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

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