Bensonlar algoritmi (Go) - Bensons algorithm (Go) - Wikipedia

O'yinda Boring, Benson algoritmi (nomi bilan Devid B. Benson ) qarama-qarshi o'yinchi ketma-ket necha marta aylanishiga qaramay, tutishdan xavfsiz bo'lgan toshlarni aniqlash uchun ishlatilishi mumkin, ya'ni. shartsiz tirik.[1]

Algoritm

Umumiylikni yo'qotmasdan, biz Bensonning qora o'yinchi uchun algoritmini tasvirlaymiz.

Ruxsat bering X barcha Qora zanjirlarning to'plami bo'ling va R barcha Qora yopiq mintaqalar to'plami bo'lishi X. Keyin Benson algoritmi quyidagi zinapoyalarni yoki mintaqalarni o'chirishga qodir bo'lmaguncha quyidagi ikki bosqichni takrorlashni talab qiladi:

  1. Olib tashlash X ikkitadan kam qora tanli mintaqalarga ega bo'lgan barcha qora zanjirlar R, Qora bilan yopilgan mintaqa hayotiy Qora zanjirga X agar uning barcha bo'sh kesishmalari zanjirning erkinliklari bo'lsa.
  2. Olib tashlash R zanjirda atrofidagi tosh bilan barcha Qora yopiq mintaqalar X.

Oxirgi to'plam X - bu barcha shartsiz tirik Qora zanjirlarning to'plami.[2]

Shuningdek qarang

Adabiyotlar

  1. ^ Tapani Raiko (2005 yil 5-may). "Benson algoritmi". Olingan 21 mart, 2012.
  2. ^ "Sensei kutubxonasi: Bensonning shartsiz hayot ta'rifi". Olingan 21 mart, 2012.