|
|
|
Задача оптимизации
|
|||
|---|---|---|---|
|
#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 |
|
||
|
|
start [/forum/moderation_log.php?user_name=skachkovgd]: |
0ms |
get settings: |
7ms |
get forum list: |
15ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
182ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
69ms |
get tp. blocked users: |
2ms |
| others: | 447ms |
| total: | 771ms |
| 0 / 0 |
