How to find whole graph coverage path in dynamic state-flow diagram?
- by joseph
Hello, As I've been researching algorithms for path finding in graph, I found interesting problem.
Definition of situation:
1)State diagram can have p states, and s Boolean Fields, and z Int Fields
2)Every state can have q ingoing and r outgoing transitions, and h Int fields (h belongs to z - see above)
3)Every transition can have only 1 event, and only 1 action
4)every action can change n Boolean Fields, and x Int Fields
5)every event can have one trigger from combination of any count of Boolean Fields in diagram
6)Transition can be in OPEN/CLOSED form. If the transition is open/closed depends on trigger2 compounded from 0..c Boolean fields.
7) I KNOW algorithm for finding shortest paths from state A to state B.
8) I KNOW algorithm for finding path that covers all states and transitions of whole state diagram, if all transitions are OPEN.
Now, what is the goal:
I need to find shortest path that covers all states and transitions in dynamically changing state diagram described above. When an action changes some int field, the algorithm should go through all states that have changed int field.
The algorithm should also be able to open and close transition (by going through transitions that open and close another transitions by action) in the way that the founded path will be shortest and covers all transitions and states.
Any idea how to solve it? I will be really pleased for ANY idea. Thanks for answers.
