Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
Есть простая и специфичная виртуалная машина (Для проверки регекспов). Она умеет только простые операции, безусловный переход и операцию деления процесса. И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. Если один из процессов достигает любой точки выхода то все процессы заверщаются. Заранее известно что код может быть не оптимальным. Задача этот код оптимизировать. Очевидно что если некоторые команды никогда не выполняются их можно удалить. Но естъ ещё бесконечные циклы. Так-как они не видут к результату их тоже нужно оптимизировать.
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.
13 окт 21, 17:05    [22383241]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

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

группу регулярок довольно легко можно объединить в 1, тут всё от задачи зависит

используемые для оптимизации алгоритмы:
переход от НКА к ДКА - Subset construction
для минимизации ДКА, как вариант, есть простой алгоритм - Алгоритм Бржозовско
13 окт 21, 18:41    [22383298]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 52569
А почему там - бесконечные циклы?
13 окт 21, 18:52    [22383303]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan),

Я не вижу как алгоритм минимизации ДКА применим к изложенной задаче. Задачи то совершенно разные.
13 окт 21, 20:54    [22383348]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

вот, для начала, и сформулируйте задачу

автор
И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода.

есть State, есть множественные переходы, если предположить что есть ещё условия переходов, то если мой хрустальный шар не сломался, то это и есть НКА
а значит из него можно сделать ДКА

Сообщение было отредактировано: 13 окт 21, 21:01
13 окт 21, 21:10    [22383350]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

если действия вашей "машины" можно описать наподобие этого кода
то ваш "специфичный код" и есть скомпилированные регулярки
13 окт 21, 21:24    [22383353]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan)
_дух_,
вот, для начала, и сформулируйте задачу


Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.

Вот моя задача. Всё остальное - так немного лирики.
13 окт 21, 22:53    [22383373]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал
13 окт 21, 23:12    [22383380]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
White Owl
Member

Откуда:
Сообщений: 12861
[quot _дух_#22383373]
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения.
У графов не бывает точек старта и точек завершения. Вообще не бывает.
То о чем ты думаешь это не граф а "конечный автомат". В графическом выражении конечный автомат похож на граф, но только похож.
Регулярные выражения можно с легкостью представить в виде "недетерменированного конечного автомата" (НКА), любой НКА можно превратить в "детерминированный конечный автомат" (ДКА). На любой ДКА можно натравить алгоритмы Мили, Мура или уже упомянутого Бржозовского.

_дух_
Вот моя задача. Всё остальное - так немного лирики.
В "лирике" часто и кроется решение задачи. Не надо ее забывать.
14 окт 21, 03:43    [22383414]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
White Owl
пропущено...
У графов не бывает точек старта и точек завершения. Вообще не бывает.

Но нам ничто не мешает взять граф и сказать что одна из вершин точка старта или начала пути и также задать набор вершин - точек завершения или конечных точек пути. Такая постановка задачи корекектна.
14 окт 21, 08:14    [22383440]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan)
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал

К такому доктору я бы не обращался. Это разные задачи.
Давайте на простом примере покажу.
Пусть граф задан таким образом:

[[1],[2],[3],FINISH]


Какой результат нам даст Алгоритм Бржозовско?
14 окт 21, 08:23    [22383444]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

тынц - оч хорошая статья, на пальцах, так сказать
14 окт 21, 08:24    [22383445]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan),

Я рад что вы знаете методы оптимизации ДКА но я повторяю - это не моя задача.
во первых не это не ДКА, во вторых мне ненужно уменьшать количество состояний.
14 окт 21, 09:56    [22383476]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 775
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?
14 окт 21, 10:07    [22383482]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
Имя пользователя1
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

Рёбра - это действия виртуальной машины. Состояния - не материальны. Просто число.
14 окт 21, 10:21    [22383488]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
Имя пользователя1
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.
14 окт 21, 10:34    [22383497]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 52569
_дух_
Имя пользователя1
пропущено...
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.

Вроде стандартный алгоритм. Поиск минимального дерева. Или остовного.
14 окт 21, 12:50    [22383584]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_
kealon(Ruslan)
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал

К такому доктору я бы не обращался. Это разные задачи.
Давайте на простом примере покажу.
Пусть граф задан таким образом:

[[1],[2],[3],FINISH]


Какой результат нам даст Алгоритм Бржозовско?

FINISH и даст, переходы то у вас безусловные
а какой результат вы ожидаете?
14 окт 21, 13:25    [22383615]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
14 окт 21, 13:52    [22383639]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54281
А переходы между состояниями автомата - граф.
14 окт 21, 13:54    [22383641]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
ваши намёки интереса не представляют, вы же доктору не говорите "догодайся сам, а я посижу" ? вот на форуме тоже самое.
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?
14 окт 21, 15:05    [22383696]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 18
kealon(Ruslan)
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?


Для вас третий раз повторю:
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Если вам что-то непонятно задавайте вопрос.
Подозреваю студент до вопроса не созрел но про вшей билет выучил.
14 окт 21, 15:52    [22383747]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6569
_дух_,

я вам и задал вопрос

22383615

а ответ на ваш вопрос тот же самый
22383380
только чуть упростить его: "отжиг" с выходов, потом отжиг со входа по оставшемся переходам
14 окт 21, 16:05    [22383755]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54281
_дух_
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Форд-Фалкерсон и его модификации. Ищет кратчайшие пути из заданной вершины графа в любую другую. Рекомендую.
15 окт 21, 14:02    [22384222]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 775
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.
15 окт 21, 15:42    [22384260]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить