寻找最短路径的递归算法 [英] Recursive algoritme for finding the shortest path

问题描述

嗨！


我作为工业工程师（信息学）工作的第一年


我们有一个任务要做：

....创建一个游戏区域（矩阵[DIM] [DIM]）。该领域的一些地方被封锁了，因此你无法通过它们。其他人可以自由地过去......


（我已找到那部分）

- > http://users.pandora.be/hebbrecht/jochen/ c ++ / test.cpp


现在我需要找到一个algoritme来找到该字段中随机

点之间的最短路径。我有很多可能性......但有些被封锁了

（因为你不能通过它们）......有些太长了！


这应该是algoritme：


四种可能性（东，南，西，北）{

如果步骤可行{//当你不要离开游戏场

新点//执行步骤

距离= distance_from_next_point +1

如果距离为''n'不知道在新点还是距离是

小于距离{

记住新点的干扰

从新点开始步骤

}

}

}


这是伪代码...但我不能在C ++中找到代码。它应该是一个递归的... ...谁可以帮助我:-（？

Hi!

I running my first year as industrial engineer (informatics)

We have an assignment to do :
.... create a playfield (matrix[DIM][DIM]). Some places in that field are
blocked, so you can''t pass them. The others are free to go over ...

(I already found that part)
-> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp

Now I need the find an algoritme to find the shortest way between to random
points in that field. I have a a lot possibilities ... But some are blocked
(because you can''t pass them) ... Some are way too long!

This should be the algoritme:

for the four possibilities (east, south, west, north) {
if step is possible {// when you don''t leave the playfield
make new point // execute step
distance = distance_from_next_point +1
if distance is''n''t know in the new point OR distance is
smaller then distance {
remember distrance for new point
make step from new point
}
}
}

This is Pseudo code ... But I can''t find the code in C++. It should be a
recursive one ... Who can help me out :-(?

推荐答案

Webdad写道：

Webdad wrote:

嗨！

我作为工业工程师（信息学）工作了第一年

我们有一个任务执行：
...创建一个playfield（矩阵[DIM] [DIM]）。该字段
中的某些地方被阻止，所以你不能通过它们。其他地方可以自由地通过......

（我已找到那部分）
- > http://users.pandora.be/hebbrecht/jochen/c++/test.cpp

嗯，你可能需要一个和你的导师谈谈他的C ++课程的质量。你不应该处理数组。

现在我需要找到一个algoritme来找到最短路径在该字段中随机点之间的
。我有很多可能性...但是有些是
被阻止（be因为你不能通过它们......有些太长了！

这应该是算法：

四种可能性（东，南，西） ，北）{
如果步骤可行{//当你不离开游戏场时
提出新点//执行步骤
距离= distance_from_next_point +1
如果距离是不知道在新点或距离
小于距离{
记住新点的干扰
从新点开始步骤
}
}
}

Hi!

I running my first year as industrial engineer (informatics)

We have an assignment to do :
... create a playfield (matrix[DIM][DIM]). Some places in that field are blocked, so you can''t pass them. The others are free to go over ...

(I already found that part)
-> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp
Well, you probably need to have a word with your tutor about the
quality of his C++ course. You shouldn''t be dealing with arrays.
Now I need the find an algoritme to find the shortest way between to random points in that field. I have a a lot possibilities ... But some are blocked (because you can''t pass them) ... Some are way too long!

This should be the algoritme:

for the four possibilities (east, south, west, north) {
if step is possible {// when you don''t leave the playfield
make new point // execute step
distance = distance_from_next_point +1
if distance is''n''t know in the new point OR distance is smaller then distance {
remember distrance for new point
make step from new point
}
}
}

听起来像Dijkstra算法，所有距离的特殊情况都是

+1。
www.boost.org 有图库，其中包含此算法：
http://www.boost.org/libs/graph/doc/...ry_review.html

听起来你可以使用广度优先搜索。


当然，对于这样一个简单的情况，使用boost :: graph可能比编码它有点困难

。


此致，

Michiel Salters

Sounds like the Dijkstra algorithm, special case with all distances are
+1.
www.boost.org has the graph library, which contains this algorithm:
http://www.boost.org/libs/graph/doc/...ry_review.html
Sounds like you can use Breadth-First Search.

Of course, using boost::graph may be somewhat harder than coding it
yourself, for such a simple case.

Regards,
Michiel Salters

Webdad写道：

嗨！

我们有一个任务要做：
...创建一个游戏场（矩阵[DIM] [DIM]）。该字段
中的某些地方被阻止，因此您无法通过它们。其他人可以自由地过去......

（我已经找到那部分）
- > http://users.pandora.be/hebbrecht/jochen/ c ++ / test.cpp

好​​吧，你可能需要和你的导师谈谈他的C ++课程的质量。你不应该处理数组。

现在我需要找到一个algoritme来找到该字段中
随机点之间的最短路径。我有很多可能性...但有些是
被阻止（因为你不能通过它们）......有些太长了！

这应该是算法：

四种可能性（东，南，西，北）{
如果步骤可行{//当你不离开游戏场时
提出新观点//执行步骤
distance = distance_from_next_point +1
如果距离在新点不知道或距离
小于距离{
记住新点的干扰<从新点开始步骤
}
}
}

Hi!

I running my first year as industrial engineer (informatics)

We have an assignment to do :
... create a playfield (matrix[DIM][DIM]). Some places in that field are blocked, so you can''t pass them. The others are free to go over ...

(I already found that part)
-> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp
Well, you probably need to have a word with your tutor about the
quality of his C++ course. You shouldn''t be dealing with arrays.
Now I need the find an algoritme to find the shortest way between to random points in that field. I have a a lot possibilities ... But some are blocked (because you can''t pass them) ... Some are way too long!

This should be the algoritme:

for the four possibilities (east, south, west, north) {
if step is possible {// when you don''t leave the playfield
make new point // execute step
distance = distance_from_next_point +1
if distance is''n''t know in the new point OR distance is smaller then distance {
remember distrance for new point
make step from new point
}
}
}

听起来像Dijkstra算法，所有距离的特殊情况都是

+1。
www.boost.org 有图表库，包含此算法：
http://www.boost.org/libs/graph/doc/...ry_review.html

听起来你可以使用广度优先搜索。


当然，使用boost :: graph可能比编码更困难

你自己，对于这么简单的案例。


问候，

Michiel Salters

Sounds like the Dijkstra algorithm, special case with all distances are
+1.
www.boost.org has the graph library, which contains this algorithm:
http://www.boost.org/libs/graph/doc/...ry_review.html
Sounds like you can use Breadth-First Search.

Of course, using boost::graph may be somewhat harder than coding it
yourself, for such a simple case.

Regards,
Michiel Salters

" msalters" schreef：

"msalters" schreef:

www.boost.org 图表库，包含此算法：
http ：//www.boost.org/libs/graph/doc/...ry_review.html
听起来你可以使用广度优先搜索。

当然，对于这样一个简单的案例，使用boost :: graph可能比编码它有点困难。

www.boost.org has the graph library, which contains this algorithm:
http://www.boost.org/libs/graph/doc/...ry_review.html
Sounds like you can use Breadth-First Search.

Of course, using boost::graph may be somewhat harder than coding it
yourself, for such a simple case.

嗯，我看得非常贴近网站..但是对于像我这样的新手来说，很难理解...

也许数组并不是那么好，但是你会想到什么？ ？

Hmm, I looked the site very closefully ... But it''s rather hard to
understand for a newbie as me ...
Maybe arrays aren''t so good, but what would you take in mind?

这篇关于寻找最短路径的递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！