java - 数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？
能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用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

Answer 1

これは比較的未解決の問題であり、個人的にはまだグラフ理論の一部であると考えていますが、SPFA やダイクストラ アルゴリズムなどの既存の最短経路関連のアルゴリズムでは解決できません。 Zeng Jin さんは友人から、ファーウェイにとってどのような競争問題があるのか​​と尋ねられたようです。この質問に対して A* アルゴリズムを使用することは間違いなく可能です。重要なのは、このヒューリスティック関数をどのように設計するかです。
関連するナレッジを検索できます
1. 指定された一連の中間ノードを介した最短経路アルゴリズム
2.

Answer 2

この質問には多項式の解があるとは思いません。 (顔を平手打ちすることへようこそ)
点の数が n、エッジの数が m、通過する必要があるエッジの数が k、n<=500、m<=5000、k<=500 であるとします。
強引なアプローチを考えてみましょう。O(n^3) で任意の 2 点間の最短経路を前処理します (もちろん、n 回のヒープでダイクストラを最適化することもできますが、これはボトルネックではありません)。O(k!) でArrange によって渡された k 個のエッジを列挙して答えを計算すると、合計の複雑さは O(k!*k) となり、これは明らかに許容できません。
必ずしもすべての順列を列挙して最適解を取得する必要はないことに注意してください。適切なパラメーターを使用すると、シミュレーテッド アニーリングなどのランダム化アルゴリズムを使用して、ほとんどの場合最適解を取得できます。
この質問が NPC か NPH であるかを証明したいと思います。
元の問題の m エッジを from[i] から to[i] として記録します。
k 個の点を持つ新しいグラフを作成します。k 個の指定されたエッジの i 番目と j 番目について、to[i] が from[j] に到達できる場合は、新しいグラフの i から j に dis[ を接続します。 to[i]][from[j]] のエッジ。したがって、元の問題は、多項式時間における新しい問題に縮小されます。つまり、経路長を最小化するために、k 点のグラフ内のすべての点を通る反復可能な経路を見つけます。この新しい問題は NPC や NPH によく似ています。 (面白い)
しかし、新しい問題を元の問題に戻す方法がわかりません。現在の考え方は、新しい問題の各点 i について、元の問題の i<<1 と (i<<1)|1 の間の +inf エッジを接続し、新しい問題の各エッジ i-> を接続するというものです。問題;j、元の問題の (i<<1)|1 から j<<1 に disi エッジを接続するのですが、いくつか問題があるようで、まだはっきりと考えていません。

Answer 3

アルゴリズムは理解できませんが、この種の CSP 問題を解決するための一般的なフレームワークは知っています。Optaplanner をご覧ください。