powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм формирования дерева из неупорядоченной кучи логических состояний
17 сообщений из 17, страница 1 из 1
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36132786
vlad2010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Вопросик по алгоритмам и программированию в целом.

Есть некая структура отобращающая логику работы конечного автомата.
Это последовательность логических состояний, которые ссылаются друг на друга определенным образом.

Надо как то отобразить все это в виде дерева.
Т.к состояния могут ссылаться друг на друга и может получиться бесконечная взяимная ссылка,
то последовательность в дереве надо где то обрывать.

Вопрос:
Есть какой то алгоритм общеизвестный, или может хоть пример в работающей программе какой то?
Я что то не могу сообразить как это сделать.
Получается совершенно не то что надо.

По идее же у меня тут какой то особый вид сортировки.
У дерева есть начальный начальный узел, а совокупность состояний такого начала не имеет.
Может делать проход в две итерации? Сначала переупорядочивать состояния, но непонятно правда по какому критерию.
А потом уже заполнять ими дерево. И искать по какому то критерию это начало дерева.

что то прям совсем в голове полный раздрай.


P.S.
Конкретно все реализуется на C#, и отображаться должно в компоненте TreeView Net2.0.
Это не принципиально, поэтому пишу в общий форум.


P.P.S
Извините что такое путанное объяснение.
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36132801
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36132807
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тьфу :) клинит под вечер
складывай вершины в мапу, напорешься на цикл - сразу заметишь :)
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36133747
it4kp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vlad2010,

Вам нужно поточнее сформулировать что вы хотите. То есть если в графе
зависимостей есть цикл, то это уже не дерево. А вопрос как отобразить не дерево в виде дерева
большлго смысла не имеет...
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36161731
vlad2010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
it4kp,

да в голове у меня не устаканилось
ну это требование такое отобразить все в дереве...
я бы сам не стал бы так делать.

я пока вообще не занимался этим с тех пор как вопрос запостил сюда
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36252660
login_member
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
все никак не закончу с этим

вот как выгладит схема которую я пытаюсь представить деревом
Схема

отмечу что в файле все эти квадратики лежат вразнобой, т.е непонятно с какого начать
если первым попадется допустим k200 из левого верхнего угла .. еще куда ни шло. а если нет.


и вот какие утверждения я нашел
авторОчевидно, что не любой граф можно отсортировать топологически. Можно доказать, что топологическая сортировка существует для ацеклических графов и не существует для цикличестких.

вообще у меня мнение сложилось что это вообще невозможно сделать.
у кого какое мнение?
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36252864
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А в чем соль?
Удалить (ориентированные) ребра, приводящие к циклам?

1 -> 2
2 -> 3
3 -> 1

и оставить только первые 2 ребра? Могу накодить.
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253216
vlad2010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
соль в том что на картинке что то совершенно непредставляемое на мой взгляд в виде дерева
вы ссылку посмотрели?

я ни с чем подобным раньше не сталкивался просто
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253241
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> вы ссылку посмотрели?

конечно
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253288
junior  idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vlad2010соль в том что на картинке что то совершенно непредставляемое на мой взгляд в виде дерева
Не только на твой взгляд. Представленный на картинке граф не является "деревом" (ориентированным) чисто с математической точки зрения. Циклов, вроде, нету, зато "корней" много (а должен быть один) и у некоторых вершин более одного "предка".
Как один из возможных вариантов преобразования такого графа в ориентированное дерево:
1. ввод фиктивной вершины -- "корня" -- из которой дуги будут вести во все вершины, которые изначально не имеют предков;
2. размножение вершин, имеющих более одного "предка"; например, если вершина имеет двух предков, то она разбивается на две вершины, первая является потомком первого родителя, а вторая -- второго родителя; дети, соответственно, тоже в итоге раздвоятся.
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253305
junior  idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
junior idiotЦиклов, вроде, нету
А, вру, циклы есть. Тогда вообще без толку пытаться к дереву преобразовать даже "примерно".
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253330
vlad2010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
соль еще в том что неизвестно где начало дерева

т.е прочитались все эти квадратики из файла...
и как бы непонятно с какого начинать
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253337
junior  idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vlad2010неизвестно где начало дерева
Какого дерева-то?
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36253431
vlad2010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
junior idiot,

ну вот того дерева к которому я хочу все привести...
его действительно там и нет... поэтому состояния и лежат беспорядочно...
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36254531
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vlad2010junior idiot,

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

Для начала найдите точку входа, если она есть. То есть, состояние, у которого нет входа из других состояний. Не факт, что оно найдется, как и не факт, что оно будет единственным. А потом от него перебором, что бы узлы не повторялись. И получите "дерево". Да, судя по схеме из ссылки, там HSM с набором ортогональных состояний (или мне кажется? - нотация странная). Если так, то деревьев будет больше одного.
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36254533
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vlad2010и как бы непонятно с какого начинать Начинать с чтения теории графов и изучения методик обхода узлов.
...
Рейтинг: 0 / 0
Алгоритм формирования дерева из неупорядоченной кучи логических состояний
    #36269333
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Представить в виде дерева структуру, которая не может быть представлена в виде дерева?

автор...- Г-голубчики, - сказал Федор Симеонович озадаченно, разобравшись в почерках. - Это же п-проблема Бен Б-бецалая. К-калиостро же доказал, что она н-не имеет р-решения.

- Мы сами знаем, что она не имеет решения, - сказал Хунта, немедленно ощетиниваясь. - Мы хотим знать, как ее решать.

- К-как-то ты странно рассуждаешь, К-кристо... К-как же искать решение, к-когда его нет? Б-бесмыслица какая-то...

- Извини, Теодор, но это ты странно рассуждаешь. Бессмыслица - искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет...
...
Рейтинг: 0 / 0
17 сообщений из 17, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм формирования дерева из неупорядоченной кучи логических состояний
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]