Mixing
Farmer, hex, fox and grain problem. Creating an admissible heuristic via Graph Search?
$begingroup$
I'm having troubles trying to think of an admissible heuristic for this problem. Currently I've represented this problem as follows.
My graph for this is as follows. Graph
0 means left side of the river
1 means right side of the river
The problem:
A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right side of the river using a raft.
The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft.
The hen cannot be left alone with the grain, or it will eat the grain.
The fox cannot be left alone with the hex, or it will eat the hen.
Right now i'm attempting to think of a way to create an admissible heuristic through euclidean distance.
graph-theory puzzle
asked Feb 2 at 0:30
user8738587user8738587
31
$endgroup$
add a comment |
$begingroup$
I'm having troubles trying to think of an admissible heuristic for this problem. Currently I've represented this problem as follows.
My graph for this is as follows. Graph
0 means left side of the river
1 means right side of the river
The problem:
A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right side of the river using a raft.
The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft.
The hen cannot be left alone with the grain, or it will eat the grain.
The fox cannot be left alone with the hex, or it will eat the hen.
Right now i'm attempting to think of a way to create an admissible heuristic through euclidean distance.
graph-theory puzzle
asked Feb 2 at 0:30
user8738587user8738587
31
$endgroup$
add a comment |
$begingroup$
I'm having troubles trying to think of an admissible heuristic for this problem. Currently I've represented this problem as follows.
My graph for this is as follows. Graph
0 means left side of the river
1 means right side of the river
The problem:
A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right side of the river using a raft.
The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft.
The hen cannot be left alone with the grain, or it will eat the grain.
The fox cannot be left alone with the hex, or it will eat the hen.
Right now i'm attempting to think of a way to create an admissible heuristic through euclidean distance.
graph-theory puzzle
asked Feb 2 at 0:30
user8738587user8738587
31
$endgroup$
I'm having troubles trying to think of an admissible heuristic for this problem. Currently I've represented this problem as follows.
My graph for this is as follows. Graph
0 means left side of the river
1 means right side of the river
The problem:
A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right side of the river using a raft.
The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft.
The hen cannot be left alone with the grain, or it will eat the grain.
The fox cannot be left alone with the hex, or it will eat the hen.
Right now i'm attempting to think of a way to create an admissible heuristic through euclidean distance.
graph-theory puzzle
graph-theory puzzle
asked Feb 2 at 0:30
user8738587user8738587
31
asked Feb 2 at 0:30
user8738587user8738587
31
asked Feb 2 at 0:30
user8738587user8738587
31
asked Feb 2 at 0:30
user8738587user8738587
31
asked Feb 2 at 0:30
user8738587user8738587
31
31
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves
So, in terms of your defined variables, we have as a lower bound for the cost:
$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
$endgroup$
add a comment |
Your Answer
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%2f3096904%2ffarmer-hex-fox-and-grain-problem-creating-an-admissible-heuristic-via-graph-s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves
So, in terms of your defined variables, we have as a lower bound for the cost:
$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
$endgroup$
add a comment |
$begingroup$
Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves
So, in terms of your defined variables, we have as a lower bound for the cost:
$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
$endgroup$
add a comment |
$begingroup$
Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves
So, in terms of your defined variables, we have as a lower bound for the cost:
$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
$endgroup$
Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves
So, in terms of your defined variables, we have as a lower bound for the cost:
$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
edited Feb 2 at 19:31
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
answered Feb 2 at 19:26
Bram28Bram28
64.5k44793
64.5k44793
add a comment |
add a comment |
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%2f3096904%2ffarmer-hex-fox-and-grain-problem-creating-an-admissible-heuristic-via-graph-s%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
