|
|
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
Вопросик по алгоритмам и программированию в целом. Есть некая структура отобращающая логику работы конечного автомата. Это последовательность логических состояний, которые ссылаются друг на друга определенным образом. Надо как то отобразить все это в виде дерева. Т.к состояния могут ссылаться друг на друга и может получиться бесконечная взяимная ссылка, то последовательность в дереве надо где то обрывать. Вопрос: Есть какой то алгоритм общеизвестный, или может хоть пример в работающей программе какой то? Я что то не могу сообразить как это сделать. Получается совершенно не то что надо. По идее же у меня тут какой то особый вид сортировки. У дерева есть начальный начальный узел, а совокупность состояний такого начала не имеет. Может делать проход в две итерации? Сначала переупорядочивать состояния, но непонятно правда по какому критерию. А потом уже заполнять ими дерево. И искать по какому то критерию это начало дерева. что то прям совсем в голове полный раздрай. P.S. Конкретно все реализуется на C#, и отображаться должно в компоненте TreeView Net2.0. Это не принципиально, поэтому пишу в общий форум. P.P.S Извините что такое путанное объяснение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2009, 16:44:52 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2009, 16:53:07 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
тьфу :) клинит под вечер складывай вершины в мапу, напорешься на цикл - сразу заметишь :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2009, 16:54:52 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
vlad2010, Вам нужно поточнее сформулировать что вы хотите. То есть если в графе зависимостей есть цикл, то это уже не дерево. А вопрос как отобразить не дерево в виде дерева большлго смысла не имеет... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.08.2009, 23:00:08 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
it4kp, да в голове у меня не устаканилось ну это требование такое отобразить все в дереве... я бы сам не стал бы так делать. я пока вообще не занимался этим с тех пор как вопрос запостил сюда ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.08.2009, 14:13:00 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
все никак не закончу с этим вот как выгладит схема которую я пытаюсь представить деревом Схема отмечу что в файле все эти квадратики лежат вразнобой, т.е непонятно с какого начать если первым попадется допустим k200 из левого верхнего угла .. еще куда ни шло. а если нет. и вот какие утверждения я нашел авторОчевидно, что не любой граф можно отсортировать топологически. Можно доказать, что топологическая сортировка существует для ацеклических графов и не существует для цикличестких. вообще у меня мнение сложилось что это вообще невозможно сделать. у кого какое мнение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 11:55:18 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
А в чем соль? Удалить (ориентированные) ребра, приводящие к циклам? 1 -> 2 2 -> 3 3 -> 1 и оставить только первые 2 ребра? Могу накодить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 12:46:02 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
соль в том что на картинке что то совершенно непредставляемое на мой взгляд в виде дерева вы ссылку посмотрели? я ни с чем подобным раньше не сталкивался просто ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:15:28 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
> вы ссылку посмотрели? конечно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:22:50 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
vlad2010соль в том что на картинке что то совершенно непредставляемое на мой взгляд в виде дерева Не только на твой взгляд. Представленный на картинке граф не является "деревом" (ориентированным) чисто с математической точки зрения. Циклов, вроде, нету, зато "корней" много (а должен быть один) и у некоторых вершин более одного "предка". Как один из возможных вариантов преобразования такого графа в ориентированное дерево: 1. ввод фиктивной вершины -- "корня" -- из которой дуги будут вести во все вершины, которые изначально не имеют предков; 2. размножение вершин, имеющих более одного "предка"; например, если вершина имеет двух предков, то она разбивается на две вершины, первая является потомком первого родителя, а вторая -- второго родителя; дети, соответственно, тоже в итоге раздвоятся. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:40:54 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
junior idiotЦиклов, вроде, нету А, вру, циклы есть. Тогда вообще без толку пытаться к дереву преобразовать даже "примерно". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:45:01 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
соль еще в том что неизвестно где начало дерева т.е прочитались все эти квадратики из файла... и как бы непонятно с какого начинать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:51:53 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
vlad2010неизвестно где начало дерева Какого дерева-то? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 14:53:12 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
junior idiot, ну вот того дерева к которому я хочу все привести... его действительно там и нет... поэтому состояния и лежат беспорядочно... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.10.2009, 15:22:07 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
vlad2010junior idiot, ну вот того дерева к которому я хочу все привести... его действительно там и нет... поэтому состояния и лежат беспорядочно... Для начала найдите точку входа, если она есть. То есть, состояние, у которого нет входа из других состояний. Не факт, что оно найдется, как и не факт, что оно будет единственным. А потом от него перебором, что бы узлы не повторялись. И получите "дерево". Да, судя по схеме из ссылки, там HSM с набором ортогональных состояний (или мне кажется? - нотация странная). Если так, то деревьев будет больше одного. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.10.2009, 02:41:13 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
vlad2010и как бы непонятно с какого начинать Начинать с чтения теории графов и изучения методик обхода узлов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.10.2009, 02:44:44 |
|
||
|
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
|
|||
|---|---|---|---|
|
#18+
Представить в виде дерева структуру, которая не может быть представлена в виде дерева? автор...- Г-голубчики, - сказал Федор Симеонович озадаченно, разобравшись в почерках. - Это же п-проблема Бен Б-бецалая. К-калиостро же доказал, что она н-не имеет р-решения. - Мы сами знаем, что она не имеет решения, - сказал Хунта, немедленно ощетиниваясь. - Мы хотим знать, как ее решать. - К-как-то ты странно рассуждаешь, К-кристо... К-как же искать решение, к-когда его нет? Б-бесмыслица какая-то... - Извини, Теодор, но это ты странно рассуждаешь. Бессмыслица - искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.10.2009, 15:13:20 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36132801&tid=1344153]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
225ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
59ms |
get tp. blocked users: |
1ms |
| others: | 229ms |
| total: | 557ms |

| 0 / 0 |
