|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Есть простая и специфичная виртуалная машина (Для проверки регекспов). Она умеет только простые операции, безусловный переход и операцию деления процесса. И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. Если один из процессов достигает любой точки выхода то все процессы заверщаются. Заранее известно что код может быть не оптимальным. Задача этот код оптимизировать. Очевидно что если некоторые команды никогда не выполняются их можно удалить. Но естъ ещё бесконечные циклы. Так-как они не видут к результату их тоже нужно оптимизировать. Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить. Вот собственно ищю идею быстрого алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 17:05 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, всё что касается регулярных выражений известно давно и исследовано вдоль и поперёк (если там действительно регулярки) темы называются регулярные языки , конечные автоматы при правильном подходе асимптотика проверки любой регулярки пропорциональна длине входной строки группу регулярок довольно легко можно объединить в 1, тут всё от задачи зависит используемые для оптимизации алгоритмы: переход от НКА к ДКА - Subset construction для минимизации ДКА, как вариант, есть простой алгоритм - http://sovietov.com/txt/minfa/minfa.html] Алгоритм Бржозовско ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 18:41 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
А почему там - бесконечные циклы? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 18:52 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), Я не вижу как алгоритм минимизации ДКА применим к изложенной задаче. Задачи то совершенно разные. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 20:54 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, вот, для начала, и сформулируйте задачу автор И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. есть State, есть множественные переходы, если предположить что есть ещё условия переходов, то если мой хрустальный шар не сломался, то это и есть НКА а значит из него можно сделать ДКА ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 21:10 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, если действия вашей "машины" можно описать наподобие этого кода то ваш "специфичный код" и есть скомпилированные регулярки ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 21:24 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan) _дух_, вот, для начала, и сформулируйте задачу Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить. Вот собственно ищю идею быстрого алгоритма. Вот моя задача. Всё остальное - так немного лирики. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 22:53 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, Алгоритм Бржозовско это и есть то, что доктор прописал ... |
|||
:
Нравится:
Не нравится:
|
|||
13.10.2021, 23:12 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
[quot _дух_#22383373]Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения.У графов не бывает точек старта и точек завершения. Вообще не бывает. То о чем ты думаешь это не граф а "конечный автомат". В графическом выражении конечный автомат похож на граф, но только похож. Регулярные выражения можно с легкостью представить в виде "недетерменированного конечного автомата" (НКА), любой НКА можно превратить в "детерминированный конечный автомат" (ДКА). На любой ДКА можно натравить алгоритмы Мили, Мура или уже упомянутого Бржозовского. _дух_ Вот моя задача. Всё остальное - так немного лирики. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 03:43 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
White Owl пропущено... У графов не бывает точек старта и точек завершения. Вообще не бывает. Но нам ничто не мешает взять граф и сказать что одна из вершин точка старта или начала пути и также задать набор вершин - точек завершения или конечных точек пути. Такая постановка задачи корекектна. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 08:14 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan) _дух_, Алгоритм Бржозовско это и есть то, что доктор прописал К такому доктору я бы не обращался. Это разные задачи. Давайте на простом примере покажу. Пусть граф задан таким образом: Код: python 1.
Какой результат нам даст Алгоритм Бржозовско? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 08:23 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), Я рад что вы знаете методы оптимизации ДКА но я повторяю - это не моя задача. во первых не это не ДКА, во вторых мне ненужно уменьшать количество состояний. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 09:56 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_ мне ненужно уменьшать количество состояний. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 10:07 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить? Рёбра - это действия виртуальной машины. Состояния - не материальны. Просто число. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 10:21 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 _дух_ мне ненужно уменьшать количество состояний. В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 10:34 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_ Имя пользователя1 пропущено... после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить? В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения. Вроде стандартный алгоритм. Поиск минимального дерева. Или остовного. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 12:50 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_ kealon(Ruslan) _дух_, Алгоритм Бржозовско это и есть то, что доктор прописал К такому доктору я бы не обращался. Это разные задачи. Давайте на простом примере покажу. Пусть граф задан таким образом: Код: python 1.
Какой результат нам даст Алгоритм Бржозовско? FINISH и даст, переходы то у вас безусловные а какой результат вы ожидаете? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 13:25 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), я как бы издалека намекал что это граф - не автомат. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 13:52 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
А переходы между состояниями автомата - граф. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 13:54 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_ kealon(Ruslan), я как бы издалека намекал что это граф - не автомат. мы пока от вас даже внятного условия задачи не видим, как же вам помочь то? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 15:05 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan) мы пока от вас даже внятного условия задачи не видим, как же вам помочь то? Для вас третий раз повторю: Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения. Если вам что-то непонятно задавайте вопрос. Подозреваю студент до вопроса не созрел но про вшей билет выучил. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 15:52 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, я вам и задал вопрос 22383615 а ответ на ваш вопрос тот же самый 22383380 только чуть упростить его: "отжиг" с выходов, потом отжиг со входа по оставшемся переходам ... |
|||
:
Нравится:
Не нравится:
|
|||
14.10.2021, 16:05 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_ Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения. Форд-Фалкерсон и его модификации. Ищет кратчайшие пути из заданной вершины графа в любую другую. Рекомендую. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.10.2021, 14:02 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Ищет кратчайшие пути из заданной вершины графа в любую другую. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.10.2021, 15:42 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.10.2021, 17:03 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 как я понял, нужны все пути в заданные вершины, а не только кратчайшие. Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 13:56 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 Dimitry Sibiryakov Ищет кратчайшие пути из заданной вершины графа в любую другую. "всех" путей может оказаться бесконечно много. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 16:01 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Если хороводы кругами не не накручивать, бесконечностей не будет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 22:21 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
exp98 Если хороводы кругами не не накручивать, бесконечностей не будет. Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.10.2021, 00:09 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Сделал примерно так: Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке. При прохождении вершины в ней запоминается глубина стека. На каждом шаге сначала проверяем это значение для новой вершины - В. Если вершину не посещали - запоминаем глубину и продолжаем. Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**) И специальные значения если через вершину (не) проходит путь ведущий к выходу. Проблематично как мне видится действие (**). Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2) Можно ли сделать быстрее? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 09:12 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
В коде нагляднее. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 09:25 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, вот вы упёртый, почитайте описание Алгоритм Бржозовского, это всего лишь модифицированный алгоритм распрастранения в вашем случае он выполняется за O(N) выполняется он максимум в 4 цикла, каждый из которых имеет асимптотику O(N) 1 цикл - ищите все переходы в ассоциативный массив <куда, откуда> 2 цикл - на старте помещаете в стек\очередь все результатные состояния и с помощью ассоциативного массива из первого цикла "обжигаете" пока стек не исчезнет, на выходе должны получиться "обожжённые пути" 3 цикл : из "обожённых" путей со второго цикла, нужно составить ассоциативный массив <откуда, куда> (его можно заполнить и во втором цикле) 4 цикл фактически тот же алгоритм что и во 2-м, но уже с использованием мапы<откуда, куда> от точек старта PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 10:15 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), Для начала вы описываете здесь какой-то "отжигной" алоритм, но не алгоритм Бржозовского. Или я чего-то не вижу? Про Бржозовского цитата из текста, на который вы линкнули: С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. Уже это уже противоречит вашему утверждению про "всего 4 цикла". Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 11:23 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), про Алгоритм Бржозовского - применим для НКА и ДКА. Из вики про КАПри работе на вход КА поступают последовательно входные воздействия, а на выходе КА формирует выходные сигналы. В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 11:47 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan) _дух_, вот вы упёртый вы можете вести диалог на уровне, без оскорблений и перехода на личности? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 12:34 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, есть такой анекдот авторЗадача I Пусть у нас есть пустой чайник, кран с водой, спички, газовая конфорка. Перед физиком и математиком ставят задачу вскипятить воду. Действуют они одинаково. 1. Наливают воду в чайник. 2. Зажигают конфорку. 3. Ставят чайник на огонь и ждут, пока закипит. Модифицируем Задачу I в Задачу II. У нас уже есть чайник, наполненный водой и зажженная конфорка. Цель та же: вскипятить воду. Физик ставит чайник на огонь и ждет, пока вода закипит. Математик выключает огонь, выливает воду из чайника и говорит: теперь задача сводится к предыдущей. (В некоторых интерпретациях математик после этого ждет, пока придет физик и вскипятит воду))) Доказывается применимость очень просто, вот давайте сделаем как математики у вас есть набор путей <откуда, куда> а давай туда условие перехода добавим инкрементально (1, 2, 3 и т.д), т.е. на каждый переход у нас получится единственное неповторимое условие и что мы увидим? КА причём, ДКА, так как условия переходов у нас уникальные а дальше что делать? - мы знаем ... теперь по асимптотике, говорится, что алгоритм может быть экспоненциальным, но в самом алгоритме мы видим только циклы по количеству элементов O(N). Экспоненциальность получается в subset construction, при преобразовании из НКА в ДКА. Но у нас уже ДКА, следовательно количество элементов может только уменьшаться!!! следовательно алгоритм O(N) для нашего случая Всё просто? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 13:20 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), А есть ещё поговорка - если у бабушки есть член то он уже дедушка. Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 19:26 |
|
|
start [/forum/topic.php?all=1&fid=16&tid=1339622]: |
0ms |
get settings: |
11ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
166ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
69ms |
get tp. blocked users: |
2ms |
others: | 246ms |
total: | 531ms |
0 / 0 |