Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

一个供Prolog爱好者学习与交流的地方


您没有登录。 请登录注册

我也来试着出一题:我很喜欢的一个案例---民主的海盗

浏览上一个主题 浏览下一个主题 向下  留言 [第1页/共1页]

这是我很喜欢的一个案例,
是以前我做关于博奕论(Game Theory)的报告时看到的,
一直觉得结论挺有意思的,
现在我把它作为prolog的一个题目写出来,
我不知道程序好写还是不好写(感觉要完全写对好像也不是很简单),
总之这是我自己出的题目,并不是什么国际prolog竞赛题目,
出得不好的话请多包含。


题目内容:

有一群民主的海盗,这里先假设为5个,
他们要瓜分他们抢来的金子,这里先假设为100个,
他们在如何瓜分抢来的东西这个问题上采用自己定下的特有的民主方式,
规则如下:

1. 由最凶狠到最懦弱的5个海盗依次轮流提案如何分配这100个金子,
最凶狠的是海盗1号,次凶狠的是海盗2号,最懦弱的是海盗5号,
每个人提出的议案为5个数字的数组,比如像[24, 22, 20, 18, 16]的形式,
表式提案人提议给海盗1拿24个金子、海盗2拿22个金子……,依此类推。
2. 如果提出的议案获得剩余海盗数量的至少半数的支持(看完本项规则你会知道为什么是"剩余"),
(总人数5个人的话,2.5个人算半数,也就是至少要3个人支持才算过半数),
则提案通过,海盗们按照此提案去分配金子;但若支持人数不足一半,
提案的海盗会被其他海盗合力丢进海里去喂鲨鱼,并由下一顺位海盗继续提案,
规则还是一样,如此循环下去。

规则主要就是这两点,不难,下面要说的是这个案例的2个重要假设:

1. 所有海盗都是追求本身利益极大化的,也就是说对任何一位海盗来说,
A议案和B议案比较,如果自己能从A议案获得的金子多于B议案,
那肯定支持A议案而不支持B议案。
并且,获得0个金子也好过被丢进海里喂鲨鱼。
(如果某海盗P从A议案得到的金子与B议案一样多,而A议案是目前最凶狠的海盗提出的议案,
那海盗P会投反对票,因为海盗都乐于看到比自己凶狠强悍的同伴被丢下海。)

2. 所有海盗相互之间都知道彼此是"极其聪明"的(看来这个行业门槛很高哈哈),
这意谓着对任意两个海盗A和B,A知道轮到B时B会提怎样的分配案,
而B也知道A知道轮到B时B会如何提案。


请试着编写ending/3谓词用来算出这些海盗最后的下场,
比如ending(Gold, Pirate, Get),
使得给定金子个数Gold与海盗人数Pirate后,
传回ListGet,Get的第i项代表第i个海盗最终会获得多少个金子,
第i项如果为-1代表第i个海盗下场是被丢进海里喂鲨鱼。


当海盗人数太多时,Get会变得很长无法一次显示出来,
可以多编写一个ending/4谓词,比如ending(Gold, Pirate, Index, Get),
多加一个参数Index,传回第Index个海盗最终获得的金子数Get。


例:

?- ending(100, 5, Get).
Get = [98, 0, 1, 0, 1].

如果不跑程序,自己用想的,想得出为什么答案是(98, 0, 1, 0, 1)吗?


?- ending(100, 201, 1, Get).
Get = 0.

?- ending(100, 203, 1, Get).
Get = -1.

?- ending(100, 204, 1, Get).
Get = 0.

?- ending(100, 205, 1, Get).
Get = -1.

?- ending(100, 216, 1, Get).
Get = 0.

?- ending(100, 500, 44, Get).
Get = -1.




由Mercury Liao于周二 四月 03, 2012 10:46 am进行了最后一次编辑,总共编辑了1次

查阅用户资料 http://prolog.longluntan.net
代码:

:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).

代码说明:
谓词 gen_list(-L, +N, +X): 将L合一为由N个X组成的列表。
谓词 payoff(+N, +L0, -L1, -P):需要收买的人数为N,当前海盗死后的金子分布为L0,以最小代价收买到N个海盗之后的分布为L1,收买所需金子数为P

查阅用户资料
wdx04 写道::
代码:

:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).

代码说明:
谓词 gen_list(-L, +N, +X): 将L合一为由N个X组成的列表。
谓词 payoff(+N, +L0, -L1, -P):需要收买的人数为N,当前海盗死后的金子分布为L0,以最小代价收买到N个海盗之后的分布为L1,收买所需金子数为P

这几天我出去玩了,还没写完呢!
我检查了一下你写的,写得没错啊!
而且代码还挺短的,厉害。

要是之后我写完了我再把我写的发上来。
这里先附上答案:


  10名海盜搶得了窖藏的100塊金子,並打算瓜分這些戰利品。這是一些講民主的海盜(當然是他們自己特有的民主),他們的習慣是按下面的方式進行分配:最厲害的一名海盜提出分配方案,然後所有的海盜(包括提出方案者本人)就此方案進行表決。如果50%或更多的海盜贊同此方案,此方案就獲得通過並據此分配戰利品。否則提出方案的海盜將被扔到海裡,然後下提名最厲害的海盜又重複上述過程。
  所有的海盜都樂於看到他們的一位同夥被扔進海裏,不過,如果讓他們選擇的話,他們還是寧可得一筆現金。他們當然也不願意自己被扔到海裏。所有的海盜都是有理性的,而且知道其他的海盜也是有理性的。此外,沒有兩名海盜是同等厲害的——這些海盜完全按照厲害的等級排好了座次,並且每個人都清楚自己和其他所有人的等級。這些金塊不能再分,也不允許幾名海盜共有金塊,因為任何海盜都不相信他的同夥會遵守關於共用金塊的安排。這是一夥每人都只為自己打算的海盜。最凶的一名海盜應當提出什麼樣的分配方案才能使他獲得最多的金子呢?
  為方便起見,我們按照這些海盜的怯懦程度來給他們編號。最怯懦的海盜為1號海盜,次怯懦的海盜為2號海盜,如此類推。這樣最厲害的海盜就應當得到最大的編號,而方案的提出就將倒過來從上至下地進行。
  分析所有這類策略遊戲的奧妙就在於應當從結尾出發倒推回去。遊戲結束時,你容易知道何種決策有利而何種決策不利。確定了這一點後,你就可以把它用到倒數第2次決策上,如此類推。如果從遊戲的開頭出發進行分析,那是走不了多遠的。其原因在於,所有的戰略決策都是要確定:“如果我這樣做,那麼下一個人會怎樣做?”
  因此在你以下海盜所做的決定對你來說是重要的,而在你之前的海盜所做的決定並不重要,因為你反正對這些決定也無能為力了。
  記住了這一點,就可以知道我們的出發點應當是遊戲進行到只剩兩名海盜——即1號和2號——的時候。這時最厲害的海盜是2號,而他的最佳分配方案是一目了然的:100塊金子全歸他一人所有,1號海盜什麼也得不到。由於他自己肯定為這個方案投贊成票,這樣就占了總數的50%,因此方案獲得通過。
  現在加上3號海盜。1號海盜知道,如果3號的方案被否決,那麼最後將只剩2個海盜,而1號將肯定一無所獲——此外,3號也明白1號瞭解這一形勢。因此,只要3號的分配方案給1號一點甜頭使他不至於空手而歸,那麼不論3號提出什麼樣的分配方案,1號都將投贊成票。因此3號需要分出盡可能少的一點金子來賄賂1號海盜,這樣就有了下面的分配方案: 3號海盜分得99塊金子,2號海盜一無所獲,1號海盜得1塊金子。
  4號海盜的策略也差不多。他需要有50%的支援票,因此同3號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是1塊金子,而他可以用這塊金子來收買2號海盜。因為如果4號被否決而3號得以通過,則2號將一文不名。因此,4號的分配方案應是:99塊金子歸自己,3號一塊也得不到,2號得1塊金子,1號也是一塊也得不到。
  5號海盜的策略稍有不同。他需要收買另兩名海盜,因此至少得用2塊金子來賄賂,才能使自己的方案得到採納。他的分配方案應該是:98塊金子歸自己,1塊金子給3號,1塊金子給1號。
  這一分析過程可以照著上述思路繼續進行下去。每個分配方案都是唯一確定的,它可以使提出該方案的海盜獲得盡可能多的金子,同時又保證該方案肯定能通過。照這一模式進行下去,10號海盜提出的方案將是96塊金子歸他所有,其他編號為偶數的海盜各得1塊金子,而編號為奇數的海盜則什麼也得不到。這就解決了10名海盜的分配難題。
  Omohundro的貢獻是他把這一問題擴大到有500名海盜的情形,即500名海盜瓜分100塊金子。顯然,類似的規律依然成立——至少是在一定範圍內成立。事實上,前面所述的規律直到第200號海盜都成立。 200號海盜的方案將是:從1到199號的所有奇數號的海盜都將一無所獲,而從2到198號的所有偶數號海盜將各得1塊金子,剩下的1塊金子歸200號海盜自己所有。
  乍看起來,這一論證方法到200號之後將不再適用了,因為201號拿不出更多的金子來收買其他海盜。但是即使分不到金子,201號至少還希望自己不會被扔進海裏,因此他可以這樣分配:給1到199號的所有奇數號海盜每人1塊金子,自己一塊也不要。
  202號海盜同樣別無選擇,只能一塊金子都不要了——他必須把這100塊金子全部用來收買100名海盜,而且這100名海盜還必須是那些按照201號方案將一無所獲的人。由於這樣的海盜有101名,因此202號的方案將不再是唯一的——賄賂方案有101種。
  203號海盜必須獲得102張贊成票,但他顯然沒有足夠的金子去收買101名同夥。因此,無論提出什麼樣的分配方案,他都註定會被扔到海裏去喂魚。不過,儘管203號命中註定死路一條,但並不是說他在遊戲進程中不起任何作用。相反,204號現在知道,203號為了能保住性命,就必須避免由他自己來提出分配方案這麼一種局面,所以無論204號海盜提出什麼樣的方案,203號都一定會投贊成票。這樣204號海盜總算僥倖揀到一條命:他可以得到他自己的1票、203號的1票、以及另外100名收買的海盜的贊成票,剛好達到保命所需的50%。獲得金子的海盜,必屬於根據202號方案肯定將一無所獲的那101名海盜之列。
  205號海盜的命運又如何呢?他可沒有這樣走運了。他不能指望203號和204號支持他的方案,因為如果他們投票反對205號方案,就可以幸災樂禍地看到205號被扔到海裏去喂魚,而他們自己的性命卻仍然能夠保全。這樣,無論205號海盜提出什麼方案都必死無疑。206號海盜也是如此——他肯定可以得到205號的支持,但這不足以救他一命。類似地,207號海盜需要104張贊成票——除了他收買的100張贊成票以及他自己的1張贊成票之外,他還需3張贊成票才能免於一死。他可以獲得205號和206號的支援,但還差一張票卻是無論如何也弄不到了,因此207號海盜的命運也是下海喂魚。
  208號又時來運轉了。他需要104張贊成票,而205、206、207號都會支援他,加上他自己一票及收買的100票,他得以過關保命。獲得他賄賂的必屬於那些根據204號方案肯定將一無所獲的人(候選人包括2到200號中所有偶數號的海盜、以及201、203、204號)。
  現在可以看出一條新的、此後將一直有效的規律:那些方案能過關的海盜(他們的分配方案全都是把金子用來收買100名同夥而自己一點都得不到)相隔的距離越來越遠,而在他們之間的海盜則無論提什麼樣的方案都會被扔進海裏——因此為了保命,他們必會投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚腹的海盜包括201、202、204、208、216、232、264、328、456號,即其號碼等於200加2的某一方冪的海盜。
  現在我們來看看哪些海盜是獲得賄賂的幸運兒。分配賄賂的方法是不唯一的,其中一種方法是讓201號海盜把賄賂分給1到199號的所有奇數編號的海盜,讓202號分給2到200號的所有偶數編號的海盜,然後是讓204號賄賂奇數編號的海盜,208號賄賂偶數編號的海盜,如此類推,也就是輪流賄賂奇數編號和偶數編號的海盜。
  結論是:當500名海盜運用最優策略來瓜分金子時,頭44名海盜必死無疑,而456號海盜則給從1到199號中所有奇數編號的海盜每人分1塊金子,問題就解決了。由於這些海盜所實行的那種民主制度,他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚,不過有時他們也會覺得自己很幸運——雖然分不到搶來的金子,但總可以免於一死。只有最怯懦的200名海盜有可能分得一份髒物,而他們之中又只有一半的人能真正得到一塊金子,的確是怯懦者繼承財富。

查阅用户资料 http://prolog.longluntan.net
wdx04 写道::
代码:

:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).

代码说明:
谓词 gen_list(-L, +N, +X): 将L合一为由N个X组成的列表。
谓词 payoff(+N, +L0, -L1, -P):需要收买的人数为N,当前海盗死后的金子分布为L0,以最小代价收买到N个海盗之后的分布为L1,收买所需金子数为P

能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?

查阅用户资料 http://prolog.longluntan.net
Mercury Liao 写道::
能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?
首先确定需要收买多少人(NP=除自己以外的海盗数//2),然后递归计算“假如我被扔进海里,下一个人如何分配金子”(下一方案)。如果希望某人支持你,就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子,因此就把所有人在下一方案下获得的金子数量由低到高排序,只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了,所以我这里采用的是一种简化算法,排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象,正确性有待论证),其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时,方案成立,你可以得到剩余的金子;如果这个和大于金子总数,也就是说钱不够收买足够多的海盗,那就只能被扔进海里了。

查阅用户资料
wdx04 写道::
Mercury Liao 写道::
能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?
首先确定需要收买多少人(NP=除自己以外的海盗数//2),然后递归计算“假如我被扔进海里,下一个人如何分配金子”(下一方案)。如果希望某人支持你,就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子,因此就把所有人在下一方案下获得的金子数量由低到高排序,只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了,所以我这里采用的是一种简化算法,排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象,正确性有待论证),其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时,方案成立,你可以得到剩余的金子;如果这个和大于金子总数,也就是说钱不够收买足够多的海盗,那就只能被扔进海里了。

那我的思路跟你的是一样的,
但是…我的程序跑得慢得多,
不晓得我的代码哪里有多余计算,
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题,按我的代码,
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...],
而执行ending(100, 204, Get2)时,得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...],
也就是说,当海盗数为204人时我的程序是错的,
因为程序如果正确的话,应该后面202名海盗在Get1与Get2获得的金子数要是不一样的,
也就是说,在Get1能得到金子的海盗,在Get2得不到金子,
(因为当只有203名海盗时,海盗1必死无疑,剩下的202名海盗可以按Get1分配;
而当总数有204名海盗时,如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多,
那按照规则,后面202名全会投反对票,
因为得到的金子数一样的话,他们乐于见到比自己强悍的海盗被丢下海。)
不晓得你的程序是多了什么条件,使其能在这个问题上得到正确的解?


代码:
%算出除自己以外,还需要多少赞成票。Pirate是剩余海盗数。
need_support(Pirate, Need_Vote) :- N is Pirate - 1, Need_Vote is N // 2.

%将List中,最大的Delete个元素修改为0,并返还为List_Out。
delete_max(List, Delete, List_Out) :-
  Delete > 0 ->
  max_list(List, Max), nth1(N, List, Max), replace(List, N, 0, Newlist), D is Delete - 1, delete_max(Newlist, D, List_Out);
  List_Out = List.

list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

%当只剩2个海盗时,所有的金子都是海盗1的。
proposal(Gold, 2, [Gold, 0]).

proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, proposal(Gold, Surplus, NextProposal), list_plus(NextProposal, Pricelist, []),
  need_support(Pirate, Need), Delete is Surplus - Need,
  delete_max(Pricelist, Delete, Paylist), sumlist(Paylist, Pay),
  (Pay > Gold -> Proposal = [-1|Paylist] ; Get is Gold - Pay, Proposal = [Get|Paylist]).


ending(Gold, Pirate, Get) :-
  proposal(Gold, Pirate, Proposal), nth1(1, Proposal, G),
  (G \= -1 -> Get = Proposal ; P is Pirate - 1, ending(Gold, P, NextProposal), Get = [-1|NextProposal]).

ending(Gold, Pirate, Index, Get) :- ending(Gold, Pirate, Get_list), nth1(Index, Get_list, Get).

%将List中第Index个元素以With替换,并输出为ListOut。
replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).

查阅用户资料 http://prolog.longluntan.net
Mercury Liao 写道::
那我的思路跟你的是一样的,
但是…我的程序跑得慢得多,
不晓得我的代码哪里有多余计算,
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题,按我的代码,
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...],
而执行ending(100, 204, Get2)时,得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...],
也就是说,当海盗数为204人时我的程序是错的,
因为程序如果正确的话,应该后面202名海盗在Get1与Get2获得的金子数要是不一样的,
也就是说,在Get1能得到金子的海盗,在Get2得不到金子,
(因为当只有203名海盗时,海盗1必死无疑,剩下的202名海盗可以按Get1分配;
而当总数有204名海盗时,如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多,
那按照规则,后面202名全会投反对票,
因为得到的金子数一样的话,他们乐于见到比自己强悍的海盗被丢下海。)
不晓得你的程序是多了什么条件,使其能在这个问题上得到正确的解?
我估计第二个问题是delete_max的实现有问题,我自己写了一个delete_max和你的其它代码合起来运行结果是对的。
思路是先给列表的每个元素打上位置标记,然后排序,选取最大的Delete个元素的标记,按标记删除。
代码:

label_list([H|L1], [H-N|L2], N) :- NewN is N + 1, !, label_list(L1, L2, NewN).
label_list([], [], _).
label_list(L, La) :- label_list(L, La, 1).

first_n_labels(_, 0, Labels, LabelsAc) :- !, msort(LabelsAc, Labels).
first_n_labels([_-V|Las], N, Labels, LabelsAc) :- NewN is N - 1, first_n_labels(Las, NewN, Labels, [V|LabelsAc]).
first_n_labels(Las, N, Labels) :- first_n_labels(Las, N, Labels, []).

delete_labeled([_|L1], [N|Labels], [0|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L, [], L, _) :- !.
delete_labeled([H|L1], Labels, [H|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L1, Labels, L2) :- delete_labeled(L1, Labels, L2, 1).

delete_max(L, 0, L) :- !.
delete_max(L1, Delete, L2) :-
label_list(L1, La),
keysort(La, Las),
reverse(Las, Lasv),
first_n_labels(Lasv, Delete, Labels),
delete_labeled(L1, Labels, L2).
这个delete_max也可以解决500个海盗时out of local stack的问题,只不过速度还是比较慢。
引起栈溢出的主要原因就是递归深度太高,而减少递归深度的办法就是使用尾递归优化,像我的代码里面只在ending/3里面有一处递归调用不能尾递归优化,而你在proposal/3里面还有一处,对性能影响可能比较大。

查阅用户资料
wdx04 写道::
Mercury Liao 写道::
能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?
首先确定需要收买多少人(NP=除自己以外的海盗数//2),然后递归计算“假如我被扔进海里,下一个人如何分配金子”(下一方案)。如果希望某人支持你,就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子,因此就把所有人在下一方案下获得的金子数量由低到高排序,只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了,所以我这里采用的是一种简化算法,排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象,正确性有待论证),其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时,方案成立,你可以得到剩余的金子;如果这个和大于金子总数,也就是说钱不够收买足够多的海盗,那就只能被扔进海里了。

感觉上,"排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象",
这句话好像有时会有问题,比如如果<=M-1的有NP-1个,
<=M的有NP+X个,那你收买所有<=M的应该会多收买到不必要的X个人。

查阅用户资料 http://prolog.longluntan.net
wdx04 写道::
Mercury Liao 写道::
那我的思路跟你的是一样的,
但是…我的程序跑得慢得多,
不晓得我的代码哪里有多余计算,
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题,按我的代码,
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...],
而执行ending(100, 204, Get2)时,得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...],
也就是说,当海盗数为204人时我的程序是错的,
因为程序如果正确的话,应该后面202名海盗在Get1与Get2获得的金子数要是不一样的,
也就是说,在Get1能得到金子的海盗,在Get2得不到金子,
(因为当只有203名海盗时,海盗1必死无疑,剩下的202名海盗可以按Get1分配;
而当总数有204名海盗时,如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多,
那按照规则,后面202名全会投反对票,
因为得到的金子数一样的话,他们乐于见到比自己强悍的海盗被丢下海。)
不晓得你的程序是多了什么条件,使其能在这个问题上得到正确的解?
我估计第二个问题是delete_max的实现有问题,我自己写了一个delete_max和你的其它代码合起来运行结果是对的。
思路是先给列表的每个元素打上位置标记,然后排序,选取最大的Delete个元素的标记,按标记删除。
代码:

label_list([H|L1], [H-N|L2], N) :- NewN is N + 1, !, label_list(L1, L2, NewN).
label_list([], [], _).
label_list(L, La) :- label_list(L, La, 1).

first_n_labels(_, 0, Labels, LabelsAc) :- !, msort(LabelsAc, Labels).
first_n_labels([_-V|Las], N, Labels, LabelsAc) :- NewN is N - 1, first_n_labels(Las, NewN, Labels, [V|LabelsAc]).
first_n_labels(Las, N, Labels) :- first_n_labels(Las, N, Labels, []).

delete_labeled([_|L1], [N|Labels], [0|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L, [], L, _) :- !.
delete_labeled([H|L1], Labels, [H|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L1, Labels, L2) :- delete_labeled(L1, Labels, L2, 1).

delete_max(L, 0, L) :- !.
delete_max(L1, Delete, L2) :-
label_list(L1, La),
keysort(La, Las),
reverse(Las, Lasv),
first_n_labels(Lasv, Delete, Labels),
delete_labeled(L1, Labels, L2).
这个delete_max也可以解决500个海盗时out of local stack的问题,只不过速度还是比较慢。
引起栈溢出的主要原因就是递归深度太高,而减少递归深度的办法就是使用尾递归优化,像我的代码里面只在ending/3里面有一处递归调用不能尾递归优化,而你在proposal/3里面还有一处,对性能影响可能比较大。

感谢回复,我当初想了一下为什么自己的程序在204个海盗时是错的,
我没想到会是delete_max的问题,
因为我认为的问题是发生在:

(为了方便说明,这里定义一下"相反提案":比如A提案[1,0,1,0,1],B提案[0,1,0,1,0],
则A与B为相反提案。)
我的程序做法是:
当总数为204个海盗时,
1号海盗会参考2号海盗的提案,
而2号海盗的提案(在我的程序里)必定跟3号海盗是相反提案,
注意这里3号海盗其实就是当总数为202个海盗时的1号海盗,
既然2号海盗与3号海盗是相反提案,1号海盗又与2号海盗是相反提案,
那1号海盗与3号海盗就是同向提案,所以204总数时的1号海盗提案就与202总数时的1号海盗是同向提案。

但正确答案应该是204总数时的1号海盗与202总数时的1号海盗是反向提案,
关键在于204总数时的1号海盗若下海了,2号海盗也必死无疑(只有203个海盗时第1位必死),
所以如果204总数时的1号海盗与202总数时的1号海盗是同向提案,同向提案就是指后面的人获得的金子是一样多的,
那当总数有204时,大家把1号丢下海,2号又必死无疑,剩下3号还可以获得同样多的金子,何乐而不为?

我当初是觉得我的程序是在这个地方逻辑没写全,
然后又很好奇你的程序是怎么避开这个问题的。

查阅用户资料 http://prolog.longluntan.net
Mercury Liao 写道::
wdx04 写道::
Mercury Liao 写道::
能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?
首先确定需要收买多少人(NP=除自己以外的海盗数//2),然后递归计算“假如我被扔进海里,下一个人如何分配金子”(下一方案)。如果希望某人支持你,就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子,因此就把所有人在下一方案下获得的金子数量由低到高排序,只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了,所以我这里采用的是一种简化算法,排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象,正确性有待论证),其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时,方案成立,你可以得到剩余的金子;如果这个和大于金子总数,也就是说钱不够收买足够多的海盗,那就只能被扔进海里了。

那我的思路跟你的是一样的,
但是…我的程序跑得慢得多,
不晓得我的代码哪里有多余计算,
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题,按我的代码,
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...],
而执行ending(100, 204, Get2)时,得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...],
也就是说,当海盗数为204人时我的程序是错的,
因为程序如果正确的话,应该后面202名海盗在Get1与Get2获得的金子数要是不一样的,
也就是说,在Get1能得到金子的海盗,在Get2得不到金子,
(因为当只有203名海盗时,海盗1必死无疑,剩下的202名海盗可以按Get1分配;
而当总数有204名海盗时,如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多,
那按照规则,后面202名全会投反对票,
因为得到的金子数一样的话,他们乐于见到比自己强悍的海盗被丢下海。)
不晓得你的程序是多了什么条件,使其能在这个问题上得到正确的解?


代码:
%算出除自己以外,还需要多少赞成票。Pirate是剩余海盗数。
need_support(Pirate, Need_Vote) :- N is Pirate - 1, Need_Vote is N // 2.

%将List中,最大的Delete个元素修改为0,并返还为List_Out。
delete_max(List, Delete, List_Out) :-
  Delete > 0 ->
  max_list(List, Max), nth1(N, List, Max), replace(List, N, 0, Newlist), D is Delete - 1, delete_max(Newlist, D, List_Out);
  List_Out = List.

list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

%当只剩2个海盗时,所有的金子都是海盗1的。
proposal(Gold, 2, [Gold, 0]).

proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, proposal(Gold, Surplus, NextProposal), list_plus(NextProposal, Pricelist, []),
  need_support(Pirate, Need), Delete is Surplus - Need,
  delete_max(Pricelist, Delete, Paylist), sumlist(Paylist, Pay),
  (Pay > Gold -> Proposal = [-1|Paylist] ; Get is Gold - Pay, Proposal = [Get|Paylist]).


ending(Gold, Pirate, Get) :-
  proposal(Gold, Pirate, Proposal), nth1(1, Proposal, G),
  (G \= -1 -> Get = Proposal ; P is Pirate - 1, ending(Gold, P, NextProposal), Get = [-1|NextProposal]).

ending(Gold, Pirate, Index, Get) :- ending(Gold, Pirate, Get_list), nth1(Index, Get_list, Get).

%将List中第Index个元素以With替换,并输出为ListOut。
replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).

现在发现是proposal/3谓词里写错了,把第1个proposal改成ending就对了:

代码:
proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, ending(Gold, Surplus, NextProposal), list_plus(NextProposal, ......


之前学了CHR方法,又用此方法重写了这个题目,代码如下:

代码:
:- use_module(library(chr)).
:- chr_constraint ending/3, del/2, p/1.


p(N), ending(Gold, Pirate, Get) ==> Pirate < N | Del is Pirate - Pirate // 2, list_plus(Get, GG, []), del(GG, Del).
del(Get, N) <=> N > 0 | N1 is N - 1, max_list(Get, Max), nth1(X, Get, Max), replace(Get, X, 0, G1), del(G1, N1).
ending(Gold, Pirate, Get), del(Proposal, 0) <=>
    sumlist(Proposal, Pay), (Pay =< Gold -> SG is Gold - Pay, NG = [SG|Proposal]; NG = [-1|Get]), NP is Pirate + 1, ending(Gold, NP, NG).


replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).
 
list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

查询时给一个p(海盗人数),加上一个当海盗人数为2时的初始条件就可以查询了:

113 ?- p(5), ending(100, 2, [100, 0]).
ending(100,5,[98,0,1,0,1])
p(5)
true .

如果把代码中的"ending(Gold, Pirate, Get), del(Proposal, 0) <=>"
换成"ending(Gold, Pirate, Get) \ del(Proposal, 0) <=>"并重新consult后,
则每次查询可以得到小于等于想查询的海盗人数的所有结果,如下:

117 ?- p(5), ending(100, 2, [100, 0]).
ending(100,5,[98,0,1,0,1])
ending(100,4,[99,0,1,0])
ending(100,3,[99,0,1])
ending(100,2,[100,0])
p(5)
true .

查阅用户资料 http://prolog.longluntan.net
98, 0, 1, 0, 1 ?
呵呵,我没有看完全部的资料。但是这个结果。不太智能。。。。
如果这么分配,第一个人拿98个,那4个人都不会同意。第一个死的就是提出这个方案的人。

查阅用户资料
小马过河 写道::98, 0, 1, 0, 1 ?
呵呵,我没有看完全部的资料。但是这个结果。不太智能。。。。
如果这么分配,第一个人拿98个,那4个人都不会同意。第一个死的就是提出这个方案的人。


你这是没有按规则来,按规则来的话,
因为如果轮到第2个海盗提案,那3号、5号海盗什么都得不到,
所以有1个金子可以拿已经要偷笑了,会投赞成票的。

查阅用户资料 http://prolog.longluntan.net
原来如此啊。

查阅用户资料
Mercury Liao 写道::
wdx04 写道::
Mercury Liao 写道::
能大概讲一下编程的思路吗?
特别是,怎么算出决定给谁金子,不给谁金子?
首先确定需要收买多少人(NP=除自己以外的海盗数//2),然后递归计算“假如我被扔进海里,下一个人如何分配金子”(下一方案)。如果希望某人支持你,就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子,因此就把所有人在下一方案下获得的金子数量由低到高排序,只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了,所以我这里采用的是一种简化算法,排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象,正确性有待论证),其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时,方案成立,你可以得到剩余的金子;如果这个和大于金子总数,也就是说钱不够收买足够多的海盗,那就只能被扔进海里了。
感觉上,"排序后取第NP个人的金子数M,然后把所有金子数<=M的人当作潜在的收买对象",
这句话好像有时会有问题,比如如果<=M-1的有NP-1个,
<=M的有NP+X个,那你收买所有<=M的应该会多收买到不必要的X个人。
研究了一下这个问题,觉得wdx04兄的这个程序并没有问题……

首先他的六参数版本Payoff是会不断更新还需要收买的海盗人数,如果已经收买了足够人数是会停止收买的(余下的人全部给0金),所以绝不会花钱在不必要的人身上……

另一个比较不明显的问题,是他给金的方法(尽量先给高级的海盗),会否造成不必要的花费……举例:假设下一个会被通过的方案是[X,0,1,0,1,0,1](X>1),你必须收买四个海盗,那么排序后得[0,0,0,1,1,1,X],故M=1,所以你给金时会先跳过X然后向之后的四个人各多给1金,即:[0,1,2,1,2,0,0],共花费6金……但是实际上的最优解其实是[0,1,2,1,0,1,0],只花5金就够了……那是否说明他的方法是错误的呢?

答案是否定的……因为考虑到实际运行的情况,可以证明M的值永远是0,即你永远不需要给超过1金去收买任何一个海盗……

证明:假设包括你在内的海盗人数是N+1,那么在你之后会被通过的方案,需要收买的海盗人数最多是N/2(当N为偶数)或(N+1)/2(当N为奇数),也就是说最少有N/2(N偶)或(N-1)/2(N奇)人是不必被收买的,他们都必将在这方案下得到0金……而正好你现在立刻要收买的人数就是N/2(N偶)或(N-1)/2(N奇)人,所以在排序之后你会发现M必定是0……

所以,在wdx04兄的代码中,如果把这一段:
代码:
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).
改成:
代码:
payoff(NP, L0, L1, P) :- payoff(NP, L0, L1, P, 0, 0).
那么程序应该还是完全成立的……麻烦楼主核对一下?

查阅用户资料

浏览上一个主题 浏览下一个主题 返回页首  留言 [第1页/共1页]

您在这个论坛的权限:
不能在这个论坛回复主题