Remmarguts' Date | Time Limit: 4000MS | | Memory Limit: 65536K | | Total Submissions: 12450 | | Accepted: 3422 |
Description "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate. Input The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000). Output A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead. Sample Input 2 2
1 2 5
2 1 4
1 2 2
Sample Output 14 Source |
第K短路問題，大概意思就是給你N個點(diǎn)，M條邊，邊是有向的，給你每條邊的邊權(quán)，給你一個S起始點(diǎn)，T結(jié)束點(diǎn)，和一個K，求S到T的第K短路。
SPFA+A*啟發(fā)式搜索。
說說啟發(fā)式搜索吧：
通常在解決問題的時候，我們需要用到搜索算法，由已知狀態(tài)推出新的狀態(tài)，然后檢驗(yàn)新的狀態(tài)是不是就是我們要求的最優(yōu)解。檢驗(yàn)完所有的狀態(tài)實(shí)際上就相當(dāng)于遍歷了一張隱式圖。遺憾的是，所有的狀態(tài)組成的狀態(tài)空間往往是成指數(shù)級別增長的，也就造成了遍歷需要用到指數(shù)級別的時間，因此，純粹的暴力搜索，時空效率都比較低。當(dāng)然，我們在生活中遇到了類似于搜索的問題，我們并不會盲目地去搜尋每一種狀態(tài)，我們會通過我們的思維，選擇一條最接近于目標(biāo)的路徑或者是近似于最短的路徑去完成搜索任務(wù)。當(dāng)我們想要計算機(jī)去完成這樣一項(xiàng)搜索任務(wù)的時候，就得讓計算機(jī)像人一樣能夠區(qū)分盡量短的路徑，以便高效地找到最優(yōu)解。這時可以把計算機(jī)看作是一種智能體(agent)可以實(shí)現(xiàn)由初始狀態(tài)向目標(biāo)狀態(tài)的轉(zhuǎn)移。
有一種貪心策略，即每一步轉(zhuǎn)移都由計算機(jī)選擇當(dāng)前的最優(yōu)解生成新的狀態(tài)，一直到達(dá)目標(biāo)狀態(tài)為止。這樣做的時間效率雖然較高，但是貪心的策略只是用到了局部的最優(yōu)解，并不能保證最后到達(dá)目標(biāo)狀態(tài)得到的是全局最優(yōu)解。在能保證全局最優(yōu)解的范圍內(nèi)，貪心算法還是很有用的。比如說我們熟知的Dijkstra算法求單源最短路。每次選擇距離源節(jié)點(diǎn)最短距離的待擴(kuò)展節(jié)點(diǎn)進(jìn)行擴(kuò)展，最后就能生成源節(jié)點(diǎn)到所有節(jié)點(diǎn)的最短路徑。下面會講到Dijkstra的擴(kuò)展，當(dāng)理解了這個算法之后，我想，你會對Dijkstra有更深入的理解。
這就是A*算法。定義初始狀態(tài)S，目標(biāo)狀態(tài)t，g(s)是由初始狀態(tài)轉(zhuǎn)移到當(dāng)前狀態(tài)s所經(jīng)過的路徑長度，h*(s)是當(dāng)前狀態(tài)s距離目標(biāo)狀態(tài)t的實(shí)際長度，但是一般情況下我們是不知道h*(s)的值的，所以還要定義一個估價函數(shù)h(s)，是對h*(s)函數(shù)值的下界的估計，也就是有h(s)<=h*(s)，這樣需要一個條件，使得由s1生成的每狀態(tài)s2，都有h(s1)<=h(s2)，這是一個相容的估價函數(shù)。再定義f(s)=g(s)+h(s)為啟發(fā)函數(shù)，因?yàn)?/span>h(s)是單調(diào)遞增的，所以f(s)也是單調(diào)遞增的。這樣f(s)就估計出了由初始狀態(tài)的總體代價。A*算法就通過構(gòu)造這樣一個啟發(fā)函數(shù)，將所有的待擴(kuò)展?fàn)顟B(tài)加入到隊(duì)列里，每次從隊(duì)列里選擇f(s)值最小的狀態(tài)進(jìn)行擴(kuò)展。由于啟發(fā)函數(shù)的作用，使得計算機(jī)在進(jìn)行狀態(tài)轉(zhuǎn)移的時候盡量避開了不可能產(chǎn)生最優(yōu)解的分支，而選擇相對較接近最優(yōu)解的路徑進(jìn)行搜索，提高了搜索效率。
講到這里，可能已經(jīng)對A*算法的概念有點(diǎn)眉目了。下面我再來做一個比較，就用上面講到的Dijkstra的例子。Dijkstra算法說的是每次選擇距離源點(diǎn)最短距離的點(diǎn)進(jìn)行擴(kuò)展。當(dāng)然可以看做事先將源點(diǎn)到所有節(jié)點(diǎn)距離的值保存在一個優(yōu)先隊(duì)列里，每次從優(yōu)先隊(duì)列里出隊(duì)最短距離的點(diǎn)擴(kuò)展，每個點(diǎn)的擴(kuò)展涉及到要更新隊(duì)列里所有待擴(kuò)展節(jié)點(diǎn)的距離值，每個節(jié)點(diǎn)只能進(jìn)隊(duì)一次，就需要有一個表來記錄每個節(jié)點(diǎn)的入隊(duì)次數(shù)（就是算法中用到的標(biāo)記數(shù)組）。將Dijkstra求最短路的方法擴(kuò)展，這道題目要求的是兩點(diǎn)間第k短路。類比于Dijkstra算法可以首先確定下面幾個搜索策略：
1、用優(yōu)先隊(duì)列保存節(jié)點(diǎn)進(jìn)行搜索。
2、放開每個節(jié)點(diǎn)的入隊(duì)次數(shù)，求k短路，每個節(jié)點(diǎn)可以入隊(duì)k次。
首先看第一個策略，在A*算法中用優(yōu)先隊(duì)列就是要用到啟發(fā)函數(shù)f(s)確定狀態(tài)在優(yōu)先隊(duì)列里面的優(yōu)先級。其實(shí)Dijkstra用到的優(yōu)先隊(duì)列實(shí)際上就是估價函數(shù)值為0，啟發(fā)函數(shù)f(s)=g(s)，即是選取到源點(diǎn)距離最近的點(diǎn)進(jìn)行擴(kuò)展。因?yàn)?/span>h(s)=0滿足了估價函數(shù)相容這個條件。這題求k短路就不能單純的使用h(s)=0這個估價函數(shù)。解決這道題的時候選取h(x)=dt(x), dt(x)是x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短距離。最短距離可以開始由Dijkstra直接求得。
再看第二個策略，控制每個節(jié)點(diǎn)的入隊(duì)（或出隊(duì)）次數(shù)為k次，可以找到第k短路徑。可能這樣想有點(diǎn)主觀的套用，那么我就先來證明這樣一個結(jié)論：
如果x是s到t的第k短路徑上的一個節(jié)點(diǎn)，那么由這條路徑s到x是s到x的第m短路徑，則不可能有m>k。用反證法很容易得出：如果這條路徑是s到x的第m短路徑，如果m>k，那么經(jīng)過x到t的路徑就有m-1條比當(dāng)前路徑要短，不符合當(dāng)前路徑是s到t的第k短路徑。
代碼：
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAXN 10005 //邊數(shù)
#define inf 1 << 25
using namespace std;
int dis[MAXN];
struct node
{
int v, dis;
};
struct edge
{
int v, w;
friend bool operator < (edge a, edge b)
{
return (a.w + dis[a.v]) > (b.w + dis[b.v]);
}
};
vector <node> map[MAXN];
vector <node> remap[MAXN];
int n, m; //n是節(jié)點(diǎn)數(shù)，m是邊數(shù)。
int s, t, k; //s是起始點(diǎn)，t是結(jié)束點(diǎn)，k是第k小。
void init()
{
int i;
for (i = 0; i < MAXN; ++i)
map[i].clear();
for (i = 0; i < MAXN; ++i)
remap[i].clear();
}
void spfa(int s)
{
int i;
bool used[MAXN];
memset(used, 0, sizeof(used));
for (i = 0; i < MAXN; ++i)
dis[i] = inf;
dis[s] = 0;
used[s] = true;
queue <int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
used[u] = false;
for (i = 0; i < remap[u].size(); ++i)
{
node p = remap[u][i];
if (dis[p.v] > dis[u] + p.dis)
{
dis[p.v] = dis[u] + p.dis;
if (!used[p.v])
{
used[p.v] = true;
q.push(p.v);
}
}
}
}
}
int a_star()
{
if (s == t)
k++; //注意，起始和結(jié)束一樣，k要+1；
if (dis[s] == inf)
return -1;
int i, x, len, cnt[MAXN];
edge n1, n2;
priority_queue <edge> q;
memset(cnt, 0, sizeof(cnt));
n1.v = s;
n1.w = 0;
q.push(n1);
while (!q.empty())
{
n2 = q.top();
q.pop();
x = n2.v;
len = n2.w;
cnt[x]++;
if (cnt[t] == k)
return len;
if (cnt[x] > k)
continue;
for (i = 0; i < map[n2.v].size(); ++i)
{
n1.v = map[n2.v][i].v;
n1.w = len + map[n2.v][i].dis;
q.push(n1);
}
}
return -1;
}
int main()
{
int i;
node p;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
int a, b, l;
for (i = 1; i <= m; ++i)
{
scanf("%d%d%d", &a, &b, &l);
p.v = b;
p.dis = l;
map[a].push_back(p);
p.v = a;
remap[b].push_back(p);
}
scanf("%d%d%d", &s, &t, &k);
spfa(t);
int ans = a_star();
printf("%d\n", ans);
}
return 0;
}
posted on 2011-10-17 15:19
LLawliet 閱讀(669)
評論(0) 編輯 收藏 引用 所屬分類:
圖論