数据结构的图要求经过指定一些边,求最优解?
能帮忙指点一下应该怎么去网上找资料吗,比如和哪个问题类似,应该用什么算法?这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用A*算法求最优解.
这是输入:
花费 360 Sydney 到 Wagga
花费 200 Sydney 到 Bathurst
花费 200 Dubbo 到 Grafton
花费 240 Dubbo 到 Bathurst
花费 480 Grafton 到 Wagga
花费 440 Grafton 到 Bathurst
花费 400 Wagga 到 Bathurst
要求必须经过:
Grafton 到 Wagga
Dubbo 到 Grafton
Sydney 到 Wagga
Sydney 到 Bathurst
结果是:
Sydney 到 Bathurst
Bathurst 到 Dubbo
Dubbo 到 Grafton
Grafton 到 Wagga
Wagga 到 Sydney
Sydney 到 Wagga
总花费 1840
这个是一类比较开放的问题,个人认为还是属于图论的一个部分,但是他不能用现有的最短路径的相关算法比如SPFA,dijkstra算法来解决。曾今好像一个朋友问过我,是华为的一个什么比赛题目。这个题目用A*算法肯定可以,关键是在于如何去设计这个启发式函数?
相关知识你可以搜索
1.经过指定的中间节点集的最短路径算法
2.启发式搜索算法 A*