私は最近問題を見つける代替パスに取り組んでおり、ルート結果の多様性を高めようとしています。しかし、インターネット上には資料がほとんどないようです (または、何かを見落としている可能性があります)。得られるのは、既に見つかったパス上のセグメントの削除またはペナルティ コストの追加などのアルゴリズムであり、複数回の再ルーティングが必要です。
現在、双方向の A* アルゴリズムを使用して順方向および逆方向の最短パス ツリーを構築しており、これら 2 つのツリーが交わるポイントごとに代替パスが生成されます。
ただし、ルートから各合流点までの最適なパスは1 つしか存在しないため、代替パスの多様性は依然として制限されています。この問題に取り組むために、道路網の各ノードに 2 番目の親 (次善の親である可能性があります) を追加しようとしていますが、この方法で問題を解決できるかどうかはわかりません。
Google マップや Baidu マップなど、工業用マップの作成で使用される代替パスを見つけるアルゴリズムについて何か考えがある人はいますか? 任意の提案または参照リンクをいただければ幸いです。