Этот Java-код демонстрирует, что существует разумное решение проблемы двух генералов, которое сводит к минимуму риск для жизни мессенджера и время, затрачиваемое на передачу сообщения. При разумном количестве времени достигается 99,9-процентная достоверность повторения. Наихудший случай — это бесконечно малая вероятность того, что генералы тратят бесконечное время на отправку гонцов друг другу через опасную зону, показывая, что они еще не уверены, что все гонцы перехвачены. В этом наихудшем случае два генерала в большинстве случаев знают, что соглашение не достигнуто. Есть крошечный шанс, что им не повезло, и один генерал совершает, а другой колеблется.
У алгоритма есть определенная конечная точка, в которой каждый генерал может быть на 99,0 (переменное число девяток) процентов уверен, что другой совершит его. Он основан на том, сколько времени выделено для молчания, указывающего на обязательство. Количество жизней курьеров, подвергающихся риску, сведено к минимуму.
import java.util.*;
public class Runner{
public static void main(String[] args) {
ArrayList<String> coordinated = new ArrayList<String>();
int fails = 0;
for(int x = 0; x < 1; x++){
General a = new General("Patton");
General b = new General("Bradley");
a.coordinateAttack(b, "9:00");
System.out.println("livesRisked = '" + (a.livesRisked + b.livesRisked) + "'");
System.out.println("" + a.attackIsCoordinated + b.attackIsCoordinated);
if (a.attackIsCoordinated == false || b.attackIsCoordinated == false)
fails++;
}
System.out.println("failed " + fails + " times");
}
}
class General{
public String name;
public boolean attackIsCoordinated;
public int livesRisked;
public General(String name){
this.name = name;
livesRisked = 0;
attackIsCoordinated = false;
}
public void coordinateAttack(General otherGeneral, String time){
System.out.println("General " + name + " intends to coordinate the attack with General " + otherGeneral.name + " at " + time);
System.out.println("");
int tryThisManyTimes = 100;
for(int x = 1; x <= tryThisManyTimes; x++){
if (attackIsCoordinated == false){
System.out.println(name + " will try " + tryThisManyTimes + " times, we still arn't sure, this is attempt number " + x);
sendAMessageTo(otherGeneral, time);
}
else{
System.out.println("General " + name + " has received a confirmation from " + otherGeneral.name + " and we are 100% certain the battle is coordinated");
break;
}
}
System.out.println("Patton is 100% sure Bradley is notified of the " + time + " attack.");
System.out.println("Bradley is 100% sure Patton is notified of the " + time + " attack.");
System.out.println("");
System.out.println("This algorithm will always result in 100% assurance that each general commits to the attack and , ");
System.out.println("is sure the other will join them. The only way it can fail is if all messengers are always intercepted ");
System.out.println("and the two generals spend infinite time sending messengers across an impassable dangerzone");
System.out.println("");
System.out.println("Given infinite time, it will always result in complete accuracy.");
attackIsCoordinated = true;
}
public void sendAMessageTo(General general_to_send_to, String time){
Random r = new Random();
boolean madeItThrough = r.nextBoolean();
livesRisked++;
System.out.println("General " + name + " sends a soldier with a message across the dangerzone to " + general_to_send_to.name);
if (madeItThrough)
general_to_send_to.receiveMessage(this, time);
else
System.out.println(name + "'s messenger was intercepted! Blast! Life used up with no results!");
}
public void sendConfirmation(General general_to_send_to, String time){
Random r = new Random();
System.out.println(name + " is risking a life to tell " + general_to_send_to.name + " we will comply.");
boolean madeItThrough = r.nextBoolean();
livesRisked++;
if (madeItThrough)
general_to_send_to.receiveConfirmation(this, time);
else
System.out.println(name + "'s confirmation messenger was intercepted, but we don't know that, we know " + general_to_send_to.name + " will continue to send us messengers until he is 100% sure.");
}
public void receiveMessage(General general_who_sent_it, String time){
attackIsCoordinated = true;
System.out.println("Messenger made it!! As agreed, General " + name + " is notified and commits 100% to the attack at " + time);
sendConfirmation(general_who_sent_it, time);
}
public void receiveConfirmation(General general_who_sent_it, String time){
System.out.println("Messenger made it!! General " + name + " has received confirmation from " + general_who_sent_it.name + ", therefore we know he's committed 100% to the attack and we don't need to keep sending messengers.");
attackIsCoordinated = true;
}
}
Результат и своего рода псевдокод:
General Patton intends to coordinate the attack with General Bradley at 9:00
Patton will try 100 times, we still arn't sure, this is attempt number 1
General Patton sends a soldier with a message across the dangerzone to Bradley
Patton's messenger was intercepted! Blast! Life used up with no results!
Patton will try 100 times, we still arn't sure, this is attempt number 2
General Patton sends a soldier with a message across the dangerzone to Bradley
Messenger made it!! As agreed, General Bradley is notified and will commit to
the attack when he is certain, Bradley is not certain yet.
Bradley is risking a life to tell Patton we will comply.
Bradley Messenger made it!! General Patton has received confirmation from Bradley,
therefore Patton knows he's committed 100% to the attack and we don't need
to keep sending messengers. Silence means I'm 100% sure.
General Patton has received a confirmation from Bradley and we are 100%
certain the battle is coordinated
Bradley receives no additional messages from Patton, and the silence is used to
mean Patton is 100% certain, the amount of time passed is so great that the
odds of all messengers being intercepted approaches zero.
Patton is 99.9 repeated % sure Bradley is committed to the 9:00 attack.
Bradley is 99.9 repeated % sure Patton is committed of the 9:00 attack.
Этот алгоритм всегда будет возвращать 99 (определенное количество девяток) повторяющихся процентов для каждого генерала, уверенного, что другой будет там. Единственный способ, которым это может потерпеть неудачу, - это если все гонцы всегда перехватываются, и два генерала тратят бесконечное время, отправляя гонцов через непроходимую опасную зону.
Все, что требуется, — это чтобы один мессенджер прошел и загудел, было получено уведомление, а тишина используется в качестве двунаправленного подтверждения для обеих сторон.
Количество активов или «жизней», которым рискуют, составляет от 3 до 8, учитывая шансы 50/50 пройти через опасную зону.
person
Eric Leschinski
schedule
16.11.2012
