Этот код Java демонстрирует, что существует разумное решение проблемы двух генералов, сводящее к минимуму риск для жизни мессенджера и время, необходимое для передачи сообщения.При разумном количестве времени достигается 99,9% повторения.Худший случай - бесконечно малая вероятность того, что генералы потратят бесконечное время на отправку посланников к другому через опасную зону, указывая на то, что они еще не уверены, что все посланники перехвачены.В этом худшем случае большую часть времени два генерала знают, что соглашение не было достигнуто.Существует небольшая вероятность того, что им не повезло, и один генерал совершает коммит, а другой колеблется.
В алгоритме есть определенная конечная точка, где каждый генерал может быть 99. (переменное число девяток), определенный надругой совершит.Он основан на том, сколько времени выбрано для молчания, указывающего на приверженность.Количество рискованных жизней мессенджера сведено к минимуму.
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 пробиться через опасную зону.