Weighted digraph with AND-OR vertices, search algorithm - independent solution from a vertex for which each involved vertex has same sub-solution? The Next CEO of Stack OverflowModified Shortest Path ProblemA tree graph - find how many pairs of vertices, for which the sum of edges on a path between them is CReference request: maximize the total weight along the path on the graph.Finding a circuit in a weighted graph with weight closest to desired valueWhat is the total weight of the minimal spanning tree?Finding minimum edge weight given the path lengths?Traversing a complete graphFinding the number of unlabeled graphs with $n$ vertices such that each vertex has degree 2Find a largest graph with ten vertices, such that each vertex has even degree.Sol'n in directed weighted cyclic graph to terminating vertex: such that all vertices along path have same independently given solution?
Fastest way to shutdown Ubuntu Mate 18.10
Should I tutor a student who I know has cheated on their homework?
What does this shorthand mean?
Why is there a PLL in CPU?
Is a stroke of luck acceptable after a series of unfavorable events?
Putting a 2D region plot under a 3D plot
Trouble understanding the speech of overseas colleagues
Horror movie/show or scene where a horse creature opens its mouth really wide and devours a man in a stables
How do we know the LHC results are robust?
If I blow insulation everywhere in my attic except the door trap, will heat escape through it?
How do I solve this limit?
Term for the "extreme-extension" version of a straw man fallacy?
What do "high sea" and "carry" mean in this sentence?
Why didn't Khan get resurrected in the Genesis Explosion?
What does "Its cash flow is deeply negative" mean?
WOW air has ceased operation, can I get my tickets refunded?
Why did we only see the N-1 starfighters in one film?
Is HostGator storing my password in plaintext?
When did Lisp start using symbols for arithmetic?
How to write papers efficiently when English isn't my first language?
Why here is plural "We went to the movies last night."
How do scammers retract money, while you can’t?
I believe this to be a fraud - hired, then asked to cash check and send cash as Bitcoin
Implement the Thanos sorting algorithm
Weighted digraph with AND-OR vertices, search algorithm - independent solution from a vertex for which each involved vertex has same sub-solution?
The Next CEO of Stack OverflowModified Shortest Path ProblemA tree graph - find how many pairs of vertices, for which the sum of edges on a path between them is CReference request: maximize the total weight along the path on the graph.Finding a circuit in a weighted graph with weight closest to desired valueWhat is the total weight of the minimal spanning tree?Finding minimum edge weight given the path lengths?Traversing a complete graphFinding the number of unlabeled graphs with $n$ vertices such that each vertex has degree 2Find a largest graph with ten vertices, such that each vertex has even degree.Sol'n in directed weighted cyclic graph to terminating vertex: such that all vertices along path have same independently given solution?
$begingroup$
I have a weighted digraph (with cycles) search problem where, given a known starting vertex, I wish to find the 'least weighted' solution to terminating vertices (there may be multiple solutions). In this graph:
- There are three types of vertex in this graph: "OR", "AND" and "END".
- Terminating vertices are "END" vertices.
- An "END" vertex can only be reached from an "OR" vertex
- Otherwise, vertices always alternate between "OR" and "AND", and solutions start with an "OR"
- All edges going out of "OR" vertices are positively weighted.
- Each edge from an "OR" vertex has a weight different from other edges from the same vertex (though, if it makes the problem simpler, it would be possible to have equal weights).
- There are cycles possible everywhere.
- An edge between "OR" and "END" vertices may be weighted 0 (no cost) otherwise it will be weighted high†.
- There should be a solution from every "OR" vertex to the "END" vertices, if any path exists between them.
Questions:
- Is there a name for this type of graph?
- Given any starting "OR" vertex, is there an effective search algorithm that will find the least-weighted paths to the terminating "END" vertices (presumably one can be conceived, but is there an efficient, known algorithm like the Leyzorek variant of Dijkstra's)?
- Given that such an algorithm in (2) can find any solution from e.g. vertex A, is it the case that starting from any "OR" vertex B that appears in the solution to A, the algorithm can/will find the same path from B to the same set of terminating "END" vertices that are "downstream" of it in the solution to A? It is critical that the algorithm will guarantee this property, without having to solve from every vertex to verify this property.
EXAMPLE: (NOTE - weights on BLUE edges are not shown!)
In the image above (note weights are missing), all the "OR" (blue) vertices can solve to the two "END" (red) vertices, if they are solved independently of each other (i.e. if each solution from "OR" is ignorant of its path-vertices' own solutions to the "END" vertices) - it is unknown if there is a solution for each "OR" vertex to the "END" vertices such that every path-vertex along the solution gives the same (sub) solution from itself, and this is the critical property described above in (3).
† the reason for them being weighted high is that they were originally "OR" vertices that had no other solution than to something very simplistic, not all "OR" vertices have this option, and other "OR" vertices that didn't even have this simplistic solution are eliminated from the graph on a previous round. It is perhaps a separate question as to what the high weight to these "END" vertices ought to be...
graph-theory directed-graphs searching
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
$endgroup$
add a comment |
$begingroup$
I have a weighted digraph (with cycles) search problem where, given a known starting vertex, I wish to find the 'least weighted' solution to terminating vertices (there may be multiple solutions). In this graph:
- There are three types of vertex in this graph: "OR", "AND" and "END".
- Terminating vertices are "END" vertices.
- An "END" vertex can only be reached from an "OR" vertex
- Otherwise, vertices always alternate between "OR" and "AND", and solutions start with an "OR"
- All edges going out of "OR" vertices are positively weighted.
- Each edge from an "OR" vertex has a weight different from other edges from the same vertex (though, if it makes the problem simpler, it would be possible to have equal weights).
- There are cycles possible everywhere.
- An edge between "OR" and "END" vertices may be weighted 0 (no cost) otherwise it will be weighted high†.
- There should be a solution from every "OR" vertex to the "END" vertices, if any path exists between them.
Questions:
- Is there a name for this type of graph?
- Given any starting "OR" vertex, is there an effective search algorithm that will find the least-weighted paths to the terminating "END" vertices (presumably one can be conceived, but is there an efficient, known algorithm like the Leyzorek variant of Dijkstra's)?
- Given that such an algorithm in (2) can find any solution from e.g. vertex A, is it the case that starting from any "OR" vertex B that appears in the solution to A, the algorithm can/will find the same path from B to the same set of terminating "END" vertices that are "downstream" of it in the solution to A? It is critical that the algorithm will guarantee this property, without having to solve from every vertex to verify this property.
EXAMPLE: (NOTE - weights on BLUE edges are not shown!)
In the image above (note weights are missing), all the "OR" (blue) vertices can solve to the two "END" (red) vertices, if they are solved independently of each other (i.e. if each solution from "OR" is ignorant of its path-vertices' own solutions to the "END" vertices) - it is unknown if there is a solution for each "OR" vertex to the "END" vertices such that every path-vertex along the solution gives the same (sub) solution from itself, and this is the critical property described above in (3).
† the reason for them being weighted high is that they were originally "OR" vertices that had no other solution than to something very simplistic, not all "OR" vertices have this option, and other "OR" vertices that didn't even have this simplistic solution are eliminated from the graph on a previous round. It is perhaps a separate question as to what the high weight to these "END" vertices ought to be...
graph-theory directed-graphs searching
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
$endgroup$
add a comment |
$begingroup$
I have a weighted digraph (with cycles) search problem where, given a known starting vertex, I wish to find the 'least weighted' solution to terminating vertices (there may be multiple solutions). In this graph:
- There are three types of vertex in this graph: "OR", "AND" and "END".
- Terminating vertices are "END" vertices.
- An "END" vertex can only be reached from an "OR" vertex
- Otherwise, vertices always alternate between "OR" and "AND", and solutions start with an "OR"
- All edges going out of "OR" vertices are positively weighted.
- Each edge from an "OR" vertex has a weight different from other edges from the same vertex (though, if it makes the problem simpler, it would be possible to have equal weights).
- There are cycles possible everywhere.
- An edge between "OR" and "END" vertices may be weighted 0 (no cost) otherwise it will be weighted high†.
- There should be a solution from every "OR" vertex to the "END" vertices, if any path exists between them.
Questions:
- Is there a name for this type of graph?
- Given any starting "OR" vertex, is there an effective search algorithm that will find the least-weighted paths to the terminating "END" vertices (presumably one can be conceived, but is there an efficient, known algorithm like the Leyzorek variant of Dijkstra's)?
- Given that such an algorithm in (2) can find any solution from e.g. vertex A, is it the case that starting from any "OR" vertex B that appears in the solution to A, the algorithm can/will find the same path from B to the same set of terminating "END" vertices that are "downstream" of it in the solution to A? It is critical that the algorithm will guarantee this property, without having to solve from every vertex to verify this property.
EXAMPLE: (NOTE - weights on BLUE edges are not shown!)
In the image above (note weights are missing), all the "OR" (blue) vertices can solve to the two "END" (red) vertices, if they are solved independently of each other (i.e. if each solution from "OR" is ignorant of its path-vertices' own solutions to the "END" vertices) - it is unknown if there is a solution for each "OR" vertex to the "END" vertices such that every path-vertex along the solution gives the same (sub) solution from itself, and this is the critical property described above in (3).
† the reason for them being weighted high is that they were originally "OR" vertices that had no other solution than to something very simplistic, not all "OR" vertices have this option, and other "OR" vertices that didn't even have this simplistic solution are eliminated from the graph on a previous round. It is perhaps a separate question as to what the high weight to these "END" vertices ought to be...
graph-theory directed-graphs searching
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
$endgroup$
I have a weighted digraph (with cycles) search problem where, given a known starting vertex, I wish to find the 'least weighted' solution to terminating vertices (there may be multiple solutions). In this graph:
- There are three types of vertex in this graph: "OR", "AND" and "END".
- Terminating vertices are "END" vertices.
- An "END" vertex can only be reached from an "OR" vertex
- Otherwise, vertices always alternate between "OR" and "AND", and solutions start with an "OR"
- All edges going out of "OR" vertices are positively weighted.
- Each edge from an "OR" vertex has a weight different from other edges from the same vertex (though, if it makes the problem simpler, it would be possible to have equal weights).
- There are cycles possible everywhere.
- An edge between "OR" and "END" vertices may be weighted 0 (no cost) otherwise it will be weighted high†.
- There should be a solution from every "OR" vertex to the "END" vertices, if any path exists between them.
Questions:
- Is there a name for this type of graph?
- Given any starting "OR" vertex, is there an effective search algorithm that will find the least-weighted paths to the terminating "END" vertices (presumably one can be conceived, but is there an efficient, known algorithm like the Leyzorek variant of Dijkstra's)?
- Given that such an algorithm in (2) can find any solution from e.g. vertex A, is it the case that starting from any "OR" vertex B that appears in the solution to A, the algorithm can/will find the same path from B to the same set of terminating "END" vertices that are "downstream" of it in the solution to A? It is critical that the algorithm will guarantee this property, without having to solve from every vertex to verify this property.
EXAMPLE: (NOTE - weights on BLUE edges are not shown!)
In the image above (note weights are missing), all the "OR" (blue) vertices can solve to the two "END" (red) vertices, if they are solved independently of each other (i.e. if each solution from "OR" is ignorant of its path-vertices' own solutions to the "END" vertices) - it is unknown if there is a solution for each "OR" vertex to the "END" vertices such that every path-vertex along the solution gives the same (sub) solution from itself, and this is the critical property described above in (3).
† the reason for them being weighted high is that they were originally "OR" vertices that had no other solution than to something very simplistic, not all "OR" vertices have this option, and other "OR" vertices that didn't even have this simplistic solution are eliminated from the graph on a previous round. It is perhaps a separate question as to what the high weight to these "END" vertices ought to be...
graph-theory directed-graphs searching
graph-theory directed-graphs searching
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
edited Mar 18 at 15:13
Steve Pike
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
asked Mar 18 at 10:52
Steve PikeSteve Pike
1013
1013
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152641%2fweighted-digraph-with-and-or-vertices-search-algorithm-independent-solution-f%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152641%2fweighted-digraph-with-and-or-vertices-search-algorithm-independent-solution-f%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
