【2D图形编程】请大家帮忙看看这个算法的实现难度~

panchan

在下是一名业余策划，只懂得诸如“1+1加10次后写屏幕”等程序基础，没有编程能力。
目前我在做一个求职策划案，里面涉及到一个算法
我想请大家帮忙分析一下这套算法的实现难度~ [em13]
　
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
　
如下图：
　
Ａ──Ｂ
│　　│
│　　│
Ｃ　　Ｄ──Ｅ─────Ｆ
│　　│　　│　　　　　│
│　　│　　│　　　　　│
Ｇ──Ｈ──Ｉ──Ｊ──Ｋ
　　
图上的英文字母称为节点
２个相临节点间的线段为单位行程，行程值为１（E到F间也是１个行程值）
由于N条单位行程首尾衔接而成的２端为节点的线段是路径
路径经过了N+1次节点（如：ＤＥＩＨＤＥＦ）
与路径上某节点前后相临的２个节点不能为同一节点（如：ＤＥＤ错）
　
　
　　　
程序要求：
　
①任意指定一个节点为起点， 再任意指定一个起点之外的节点为终点。
　
②计算并显示出从起点到终点的最短行程值、有几种移动方法、具体的移动步骤（如：右下右右...）和经过节点（如：ＡＢＤＥ...）
　
③随机生成一个大于等于1、小于等于32的整数α，判定若以α作为起点到终点间的行程值是否合适。
　
④如何合适，显示行程值α、有几种移动方法、具体移动步骤以及所经过的节点。如果不合适，回到③。
　
⑤程序结束
　
　
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
　
　
　

为了避免因描述不明确造成的理解偏差
我下面举例说明一下这套程序的功能
　
　
　
======================================================
　

Ａ──Ｂ
│　　│
│　　│
Ｃ　　Ｄ──Ｅ─────Ｆ
│　　│　　│　　　　　│
│　　│　　│　　　　　│
Ｇ──Ｈ──Ｉ──Ｊ──Ｋ
　
模拟运行：
　
①选定了节点Ａ为起点，选定了节点Ｅ为终点。
　
　
　
②从Ａ到Ｅ的最短行程值为３
　　
　有１种移动方法

　⑴移动步骤：右下右
　　经过节点：ＡＢＤＥ
　
　
　
③生成α＝５。经判定，５可以做为Ａ到Ｅ间的行程值。
　
　
　
④当行程值为５时
　
　有３种移动方法
　
　⑴移动步骤：下下右右上
　　经过节点：ＡＣＧＨＩＥ
　
　⑵移动步骤：下下右上右
　　经过节点：ＡＣＧＨＤＥ

　⑶移动步骤：右下下右上
　　经过节点：ＡＢＤＨＩＥ
　
　
　
⑤程序结束
　
　
======================================================
　
　
基本算法就是这样了~
请大家帮忙分析一下吧
实现起来会不会很困难？
具体思路是什么？
虽然自己不会编程
但我想，如果能在求职策划案里稍微喷那么一下
把考官喷晕了，我也就圆满了
这年头找工作太不容易了~
各位大大帮个忙吧~ m(_  _)m

Utunnels

唉，想起了数据结构里面那题……实在忘光了。

panchan

Utunnels: Re:【2D图形编程】请大家帮忙看看这个算法的实现难度~

唉，想起了数据结构里面那题……实在忘光了。

哈~
这很像习题吗？
这下心就放在肚子里了~
不过还是希望大家能给点概念性的东西~

PS：我还以为就我没睡呢 [em3]

fromhell

图论里面的最短路径算法。
如果你的节点数不多，那么可以直接使用
forid算法，也就是将图中相邻节点间的距
离用矩阵表示，然后求矩阵n次方。得到
的矩阵是每两点间的最短距离，不过时间
复杂度为n^3。如果节点比较多，可以使
用djs什么的算法（忘名字了），作用是求
得某点到其他点的最短距离。时间复杂度
为n^2。

dany99

好象叫dejastra(德 加 斯特拉.)算法,实现起来也并不是特别复杂,但
相对比较慢.
求最短路径在高档一点的GIS里用得比较多,在即时战略游戏里也常用,
一般来讲,对游戏而言,没有必要用那么完美的东西,接近或者比较短就
可以满足需要了. 你看联众的工兵飞的水平多低呀,从北京飞到上海要绕道
广州,成都.  

警察抓小偷和坦克转向的那种,接近最短就可以了,再加一个辅助的决策函数就
可以满足需要.完美的最短算法耗时间,除非是直接求解最短问题,仅游戏的搜索转向,
用户通常也看不出完美和欠完美的差别.

isxuzhu

我有一本书，对这个讲的非常好，可以到我的BLOG下载：http://www.8k41.com

panchan

实际游戏中，节点会有300个左右

wdz_77

那就遍历哟

有很多最短路径的算法的，不过象你这种，还是遍历比较好。

panchan

策划案中“程序需求”这块基本就完成了~
谢谢大家~

下面就是“美工需求”和“音乐需求”了
其实问来问去的真不如美工、程序、音乐、主管都凑在一起开个会直接
一个人怎么可能面面俱到呢？
可这年头，带泥的青菜没人买
非得是洗干净、切割好、套上保鲜膜、称重打价签的青菜才让上货架...