T*********r
发帖数: 2953 | 1 给定MxN二维数组表示地图
用0表示可通行 1表示是障碍
给定两辆坦克a,b 起始坐标
坦克各自可上下左右移动 一次走一格
两坦克行进中至少相隔一格距离！
再给定两个目标A，B坐标
请设计一个算法：
输入地图，以及坦克a,b, 和目标A, B 的坐标
输出：两辆坦克都抵达目标， 最小所需步数
注：
非码工索南，给出任意解法即可。
码工索南，要求线性时间复杂度。
example：
b 0 0 A 1 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 a 0 0 0
0 0 B 0 0 0 0 0 |
T*********r
发帖数: 2953 | 2 我看 所谓锁男擅长做题是假的！ 也只擅长初中几何而已！
稍微需要动脑筋的，估计就没人会做了 |
h*********g
发帖数: 4934 | |
T*********r
发帖数: 2953 | 4 不要数字答案 图只是个 例子
要算法！
【在 h*********g 的大作中提到】
: 15+9=23
|
e*g
发帖数: 4981 | |
a****n
发帖数: 3082 | 6 两坦克同时走的话，在最狭小处相遇，这是要避免的
【在 T*********r 的大作中提到】
: 给定MxN二维数组表示地图
: 用0表示可通行 1表示是障碍
: 给定两辆坦克a,b 起始坐标
: 坦克各自可上下左右移动 一次走一格
: 两坦克行进中至少相隔一格距离！
: 再给定两个目标A，B坐标
: 请设计一个算法：
: 输入地图，以及坦克a,b, 和目标A, B 的坐标
: 输出：两辆坦克都抵达目标， 最小所需步数
: 注：
|
T*********r
发帖数: 2953 | 7 要讲究效率的话是比较难
有好的解法是线性复杂度的
【在 e*g 的大作中提到】
: 太难了
|
T*********r
发帖数: 2953 | 8 不仅是狭小处
但凡各自独立的最短路径 在相同时刻有接近交叉到 都要考虑
【在 a****n 的大作中提到】
: 两坦克同时走的话，在最狭小处相遇，这是要避免的
|
a****n
发帖数: 3082 | 9 那你题里没说清楚，应该是至上相隔两个格子
【在 T*********r 的大作中提到】
: 不仅是狭小处
: 但凡各自独立的最短路径 在相同时刻有接近交叉到 都要考虑
|
T*********r
发帖数: 2953 | 10 这不是重点。题目改成至少相隔n个格子也可以。反正要考虑互相影响就是了。
【在 a****n 的大作中提到】
: 那你题里没说清楚，应该是至上相隔两个格子
|
|
|
T*********r
发帖数: 2953 | 11 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题
原型来自 机器人，无人车路径规划问题。 |
p*********r
发帖数: 7944 | |
p*********r
发帖数: 7944 | 13 第二部，把能走的路的远面都mark了。
这样范围就很小了。
recursive。 |
p*********r
发帖数: 7944 | |
a****n
发帖数: 3082 | 15 If a b距离小于一个数，让b改变路线，不要让a改变，a改变会导致步子数增加
【在 T*********r 的大作中提到】
: 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题
: 原型来自 机器人，无人车路径规划问题。
|
T*********r
发帖数: 2953 | 16 观察到小距离再调整 是局部优化的做法
但我们要一个全局优化解
有的时候，也许出发的时候就该选择完全不同的一条路径
【在 a****n 的大作中提到】
: If a b距离小于一个数，让b改变路线，不要让a改变，a改变会导致步子数增加
|
a****n
发帖数: 3082 | 17 全局的话，a要13步都是0并且到达A是最优选择。同样的道理对b是9步
【在 T*********r 的大作中提到】
: 观察到小距离再调整 是局部优化的做法
: 但我们要一个全局优化解
: 有的时候，也许出发的时候就该选择完全不同的一条路径
|
a****n
发帖数: 3082 | 18 所以就是循环
【在 a****n 的大作中提到】
: 全局的话，a要13步都是0并且到达A是最优选择。同样的道理对b是9步
|
r******i
发帖数: 1445 | 19 思路大概是动态规划。
首先找出坦克各自的路径和步数。
再看是否路径时间有冲突。
有冲突的时候路近的让路远的。 |
T*********r
发帖数: 2953 | 20 先找独自路径无意义
我给你个简单的例子
a B 0 0 0
0 0 0 0 0
0 1 1 1 0
0 1 0 0 0
0 1 0 0 0
...
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
b A 0 0 0
独自路径都是沿着第一列走
走了很久才会发现全白走了
【在 r******i 的大作中提到】
: 思路大概是动态规划。
: 首先找出坦克各自的路径和步数。
: 再看是否路径时间有冲突。
: 有冲突的时候路近的让路远的。
|
|
|
p****b
发帖数: 3 | |
T*********r
发帖数: 2953 | 22 你是码工吗
马工好意思给出这种复杂度的解 ？
【在 p****b 的大作中提到】
: BFS 状态是两个坦克的位置而已。
|
h*********g
发帖数: 4934 | 23 关键看那辆车是领导的，社会不能只讲效率，还要明确长幼尊卑 |
s******r
发帖数: 5309 | 24 非马工非cs给个最不动脑子的算法
1. 列出所有起始到终点的路径 。
2. 杀掉所有路上有1的路径。
3. 杀掉所有可能相撞的路径。
4.找最短。
【在 T*********r 的大作中提到】
: 给定MxN二维数组表示地图
: 用0表示可通行 1表示是障碍
: 给定两辆坦克a,b 起始坐标
: 坦克各自可上下左右移动 一次走一格
: 两坦克行进中至少相隔一格距离！
: 再给定两个目标A，B坐标
: 请设计一个算法：
: 输入地图，以及坦克a,b, 和目标A, B 的坐标
: 输出：两辆坦克都抵达目标， 最小所需步数
: 注：
|
T*********r
发帖数: 2953 | 25 哦 忘了说了，有时坦克也可以原地不动 避让
【在 s******r 的大作中提到】
: 非马工非cs给个最不动脑子的算法
: 1. 列出所有起始到终点的路径 。
: 2. 杀掉所有路上有1的路径。
: 3. 杀掉所有可能相撞的路径。
: 4.找最短。
|
m*****n
发帖数: 4015 | 26 这个要是实际问题 比如 大到一个城市的 traffic control 的优化的话 不可能算出来
实际的全局最优。我觉得如果真是实际问题 还要单独算局部最优 然后在 做collision
detection 然后再来修正。 肯定不是一个 pass 能搞定。 |
T*********r
发帖数: 2953 | 27 说的也是啊。那我改改标题。
collision
【在 m*****n 的大作中提到】
: 这个要是实际问题 比如 大到一个城市的 traffic control 的优化的话 不可能算出来
: 实际的全局最优。我觉得如果真是实际问题 还要单独算局部最优 然后在 做collision
: detection 然后再来修正。 肯定不是一个 pass 能搞定。
|
m*****n
发帖数: 3644 | 28 夹逼法。
1，坦克a不动，找出b最短的第1，2，3，k路径。
2，b不动，找出a最短路径假设a的路径小，那么a等待让路。
3，b还是按原路竞走。动态障碍坐标为x,y,t.看a的路径是否遇到动态block。
4，如果遇到，a停1，2，3,n1步，再走，看是否遇到（假设b需要的距离长）。
5，检查是否有检查是否有只能通过一个坦克的峡谷。如果有，检查另一个坦克山包绕
路走另一条路。峡谷的定义是，长度超过b的最短的第1，2路径之差的只能过一个tank
的通道。 |
m*****n
发帖数: 3644 | 29 1，分别找出ab的最短路径
2，找出ab最短路径上的相撞点
3，相撞点记p0点，检查是否单通道。如果p0是，那么倒退1,2...k步，只到至少一方不
是。
4，检查不是单通道那方的第二路线，看绕路走多少步。
5，让不是单通道的那方等待，另一方前进，直至通过，然后等待的继续前进
6，比较4，5，看谁短。
7，如果p0不是单通道，让路径短的一方躲开2格，再回去。多走4格。 |
b*******8
发帖数: 37364 | 30 初中几何题 可以难到不用坐标法大数学家都证明不出
★ 发自iPhone App: ChineseWeb 16
【在 T*********r 的大作中提到】
: 我看 所谓锁男擅长做题是假的！ 也只擅长初中几何而已！
: 稍微需要动脑筋的，估计就没人会做了
|
|
|
b*******8
发帖数: 37364 | 31 别抬举算法了 过一千年人类还在学习平面几何公理体系 但没人搞计算机算法了 类似
宋元时代大量珠算算法都丢尽了垃圾堆
★ 发自iPhone App: ChineseWeb 16
【在 T*********r 的大作中提到】
: 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题
: 原型来自 机器人，无人车路径规划问题。
|
