പെർകൊലേഷൻ

ഒരു വസ്തുവിന്റെ രണ്ടറ്റങ്ങൾ തമ്മിൽ ബന്ധമുണ്ടോയെന്ന് പരിശോധിക്കുന്ന ഗണം പ്രശ്നങ്ങളാണിവ. ഫിസിക്സിലും മറ്റും പലപ്പോഴും നേരിടേണ്ട ഒരു കൂട്ടം പ്രശ്നങ്ങളാണൂ പെർക്കൊലേഷൻ പ്രശ്നങ്ങൾ. ഒരു ദണ്ഡ് വൈദ്യുതിയുടെ ചാലകം ആണോ? ഒരു വസ്തു ദ്രാവകത്തിനെ ഒരറ്റത്തു നിന്നും മറ്റേ അറ്റത്തേയ്ക്ക് കടത്തി വിടുമോ തുടങ്ങിയവ ഉദാഹരണം.

മോഡൽ

പെർകൊലെഷൻ വസ്തുവിനെ ഒരു N*N കള്ളികൾ(site) ഉൾക്കൊള്ളുന്ന ഒരു ഗ്രിഡ് വഴി മോഡൽ ചെയ്യുകയും, അതിനൊരു കംബ്യൂട്ടർ മാതൃക സ്രിഷ്ടിക്കുകയും ചെയ്യാവുന്നതാണു. അത്തരമൊരു ഗ്രിഡിൽ, കറുത്ത കള്ളികൾ “അടഞ്ഞ കള്ളിയെന്നും”(blocked site), വെളുത്ത കള്ളി, തുറന്ന കള്ളിയെന്നും(open site) വിളിക്കുന്നു. മുകളിലത്തെ വരിയിലെ ഏതെങ്കിലും തുറന്ന കള്ളിയുമായി ബന്ധമുള്ള തുറന്ന കള്ളികളെ “മുഴുവൻ തുറന്ന കള്ളിയെന്നും” വിളിയ്ക്കുന്നു (full site). ഒരു വസ്തുവിന്റെ താഴത്തെ വരിയിലെ ഏതെങ്കിലുമൊരു കള്ളി ഫുൾ സൈറ്റായി മാട്ടുംബോൾ ആ വസ്തു പെർകൊലേറ്റ് ചെയ്യുന്നു.

ഉദാഹരണത്തിലെ ഇരുംബ് ദണ്ഡിലെ അചാലകവസ്തു “തടയുന്ന കള്ളിയും”(blocked site), ചാലക വസ്തു “തുറന്ന കള്ളിയും”(open site) ആയി മോഡൽ ചെയ്യപ്പെടുന്നു. ദണ്ഡിന്റെ രണ്ടരവും തമ്മിൽ ബന്ധിപ്പിയ്ക്കുന്ന “ഓപ്പൺ സൈറ്റ്” ഉണ്ടാവുംബോൾ ദണ്ഡ് ചാലക വസ്തുവായി മാറുന്നു. അത്തരമൊരു അവസ്ഥയിൽ, ആ മോഡൽ പെർകൊലേറ്റ് ചെയ്യുന്നു.

പ്രശ്നം

ഒരു N*N ഗ്രിഡിലെ കള്ളികളികൾ തുറന്നതാവാനുള്ള സാദ്ധ്യത P യും, അടഞ്ഞതാവാനുള്ള സാദ്ധ്യത് (1-p) യും ആണെങ്കിൽ, ആ ഗ്രിഡ് പെർകൊലേറ്റ് ചെയ്യാനുള്ള സാദ്ധ്യതയെന്ത് മാത്രമുണ്ട് എന്നതാണു ശാസ്ത്രകാരന്മാരെ അലട്ടിയിരുന്ന പ്രശ്നം. മറ്റൊരു വിധത്തിൽ പറയുകയാണെങ്കിൽ ഒരു സിസ്റ്റം പെർകൊലേറ്റ് ചെയ്യാനാവശ്യമായ തുറന്ന കള്ളികളുടെ സാദ്ധ്യത P*(ക്രിട്ടിക്കൽ സാദ്ധ്യതയെന്നു ഇതിനെ വിളിയ്ക്കാം. ) എത്രയെന്നതാണൂ പ്രശ്നം. (P< p* ആണെങ്കിൽ, പെർകോലേറ്റ് ചെയ്യുകയില്ല, p> p* ആണെങ്കിൽ പെർകൊലേറ്റ് ചെയ്യുമെന്നും കാണുന്നു. എങ്കിൽ p* എത്ര എന്നു ഈ പ്രശ്നത്തെ ചുരുക്കി പറയാം) ഇതു മനസ്സിലാക്കാൻ ഒരു മാത്തമാറ്റിക്കൽ മോഡലും വികസിപ്പിക്കാനായിട്ടില്ല എന്നതാണവർ നേരിട്ടിരുന്ന കുഴപ്പം.

പ്രശ്ന പരിഹാരം

ഡയനാമിക് കണക്റ്റിവിറ്റി മോഡൽ ഉപയോഗിച്ച് വിവിദ്ധ N*N കള്ളികൾക്ക് ഒരുപാട് തവണ പ്രോഗ്രാം ഓടിക്കുന്ന ഒരു സിമുലേറ്റർ ഉണ്ടാക്കി സിമുലേറ്റ് ചെയ്താണു, സിസ്റ്റം പെർകൊലേറ്റ് ചെയ്യുന്ന ക്രിട്ടിക്കൽ സാദ്ധ്യതാ അക്കം മനസ്സിലാക്കിയത്. പ്രസിദ്ധമായ മോണ്ടി കാർലോ സിമുലേഷൻ വഴി ക്രിട്ടിക്കൽ സാദ്ധ്യതാ അക്കമായി 0.5929934999999997 കണ്ടു പിടിച്ചു.

യൂണിയൻ- ഫൈഡ് അൽഗരിതത്തിന്റെ പ്രധാന ഉപയോഗമാണീ പ്രശ്നത്തിന്റെ പരിഹാരം.

സിമുലേഷനിലെ പ്രധാന ഘട്ടങ്ങൾ

1. ഒരു N*N ഗ്രിഡ് തുടങ്ങുക. ഗ്രിഡിലെ എല്ലാ കള്ളികളും അടഞ്ഞ നിലയിൽ വെയ്ക്കുക.
2. ഗ്രിഡ് പെർകൊലേറ്റ് ചെയ്യുന്നത് വരെ, ആകസ്മികമായുള്ള ഏതെങ്കിലും ഒരു അടഞ്ഞ കള്ളി, കള്ളി തുറക്കുക.
3. പെർകൊലേറ്റ് ചെയ്യപ്പെടുംബോൾ ഉള്ള തുറന്ന കള്ളികളുടെ നിരക്കും, കള്ളികളുടെ മുഴുവൻ എണ്ണവും തമിലുള്ള അംശം കണ്ട് പിടിയ്ക്കുക. ഈ അംശമാണൂ മേൽപ്പറഞ്ഞ് കിട്ടിക്കൽ പെർകൊലേഷൻ സാധ്യതാ അക്കം.
4. സ്റ്റെപ് 1 തൊട്ട് 3 വരെ വിവിദ്ധ N*N ഗ്രിഡുകൾക്ക് പല തവണ ആവർത്തിക്കുക. ഈ പരീക്ഷണങ്ങളിൽ നിന്നും ക്രിട്ടിക്കൽ പെർകൊലേഷൻ സാധ്യതാ അക്കങ്ങളുടെ ശരാശരി മനസ്സിലാക്കുക.

അൽഗരിതം.

namespace Percolation
{
    class Program
    {

        static void Main(string[] args)
        {
            // geting the size of the N, to create an N*N grid
            int N = Convert.ToInt32(args[0]);
            /getting the number of times the model to run. simulation number 
            int T = Convert.ToInt32(args[1]);
            double[] P = new double[T];
            for (int k = 0; k < T; k++)
            {
                // creating an N*N percolation grid, initialize the site with block status
                Percolation per = new Percolation(N);
                Random rnd1 = new Random();
                //randomly opening the sites, till the system percolates
                while (!per.percolates())
                {
                    int i = rnd1.Next(N);
                    int j = rnd1.Next(N);
                    //randomly opening a site   
                    per.Open(i, j);
                }
                P[k] = (double)per.count / (N * N);
            }
		
            // mean
            double m = mean(P, T);
            //standard deviation
            double S = stddev(P,m, T);
            //95% confidence low
            double CL = confidenceLo(S, m, T);
            //95% confidence high
            double CH = confidenceLo(S, m, T);

            
        }

        public static double mean(double[] p, int T)
        {
            double mu = 0;
            foreach (var item in p)
            {
                mu += item;
            }
            mu /= T;

            
            return mu;
        }

        public static double stddev(double[] p, double mu, int T)
        {
            double sigma = 0;
            foreach (var item in p)
            {
                sigma += (item - mu) * (item - mu);
            }
            sigma /= (T - 1);

            return sigma;
        }

        public static double confidenceLo(double sigma, double mu, int T)
        {
            return (mu - 1.96 * sigma / Math.Sqrt(T));
        }

        public static double confidenceHi(double sigma, double mu, int T)
        {
            return (mu + 1.96 * sigma / Math.Sqrt(T));
        }
    }


    public class Percolation
    {
        int[,] Site;
        public float count = 0;
        WeightedQuickUnion WQU;
        int size;
        // create N-by-N grid, with all sites blocked
        public Percolation(int N)
        {
            Site = new int[N, N];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    Site[i, j] = 0;
                }
            }
            count = 0;
            size = N;
            WQU = new WeightedQuickUnion(N * N, N);

        }

        // open site (row i, column j) if it is not already
        public void Open(int i, int j)         
        {
            if (percolates())
                return;

            if (isOpen(i, j))
            {

                return;
            }
            count++;
            Site[i, j] = 1;

            if (i > 0 && j > 0 && isOpen(i - 1, j))
                WQU.Union(((i - 1) * size + j), i * size + j);

            if (j > 0 && isOpen(i, j - 1))
                WQU.Union(((i) * size + j - 1), i * size + j);

            if (i < size - 1 && j < size - 1 && isOpen(i + 1, j))
                WQU.Union(((i + 1) * size + j), i * size + j);

            if (j < size - 1 && isOpen(i, j + 1))
                WQU.Union(((i) * size + j + 1), i * size + j);

        }
        public bool isOpen(int i, int j)    // is site (row i, column j) open?
        {
            return Convert.ToBoolean(Site[i, j]);
        }

        public bool isFull(int i, int j)    // is site (row i, column j) full?
        {
            return (WQU.Find(0, size * i + j));
        }
        public bool percolates()            // does the system percolate?
        {
            return (WQU.Find(0, size * size - 1));

        }
    }
    
    // Union Find Algorithm.
    class WeightedQuickUnion
    {
        public int[] Id;
        int[] depth;
        public WeightedQuickUnion(int n, int size)
        {
            Id = new int[n];
            depth = new int[n];
            for (int i = 0; i < Id.Length; i++)
            {
                if (i < size)
                    Id[i] = 0;
                else if (i >= size * size - size)
                    Id[i] = n - 1;
                else
                    Id[i] = i;
                depth[i] = 1;
            }
        }

        public bool Find(int p, int q)
        {
            return GetRoot(p) == GetRoot(q);
        }

        public void Union(int p, int q)
        {
            if (Find(p, q))
                return;
            int pRoot = GetRoot(p);
            int qRoot = GetRoot(q);

            if (depth[pRoot] < depth[qRoot])
            {
              Id[pRoot] = qRoot;
            }
            else if (depth[pRoot] > depth[qRoot])
            {
              Id[qRoot] = pRoot;
            }
            else if (depth[pRoot] == depth[qRoot])
            {
              Id[pRoot] = qRoot;
            }
        }
        public int GetRoot(int p)
        {
            while (p != Id[p])
            {
                p = Id[p];
            }
            return p;
        }

    }

}

വിശദീകരണം

ഒരു ദ്വിമാന അറേ ഉപയോഗിച്ച്, N*N ഗ്രിഡ് സൃഷ്ടിയ്ക്കുന്നു. ഗ്രിഡിനെ ഓരോ കള്ളിയ്ക്കും 0 മുതൽ N² -1 വരെ നംബരിട്ട് ഒരു ഡൈനാമിക് കണക്റ്റിവിറ്റി മോഡൽ ഉണ്ടാക്കുന്നു. യൂണിയൻ ഫൈൻഡ് അലഗരിതത്തിലെ യൂണിയൻ ഫൺക്ഷൻ ഉപയോഗിച്ച് രണ്ട് കള്ളികൾ തമ്മിൽ റാൻഡം ആയി ബന്ധിപ്പിയ്ക്കുന്നു. ആ അൽഗരിതത്തിലെ ഫൈൻഡ് ഉപയോഗിച്ച് രണ്ട് കള്ളികൾ തമ്മിൽ ബന്ധമുണ്ടോയെന്നും, ഗ്രീഡ് പെർകൊലേറ്റ് ചെയ്യുന്നുണ്ടോയെന്നും പരിശോധിയ്ക്കുന്നു. ഗ്രിഡ് പെർകൊലേറ്റ് ചെയ്യുന്നത് വരെ, ആകസ്മികമായുള്ള ഏതെങ്കിലും ഒരു അടഞ്ഞ കള്ളി, തുറക്കുന്നു.പെർകൊലേറ്റ് ചെയ്യപ്പെടുംബോൾ ഉള്ള തുറന്ന കള്ളികളുടെ എണ്ണവും, കള്ളികളുടെ മുഴുവൻ എണ്ണവും തമിലുള്ള അംശം കണ്ട് പിടിയ്ക്കുന്നു. ഇവ വീണ്ടും വിവിദ്ധ N*N ഗ്രിഡുകൾക്ക് പല തവണ ആവർത്തിക്കുന്നു. ഈ പരീക്ഷണങ്ങളിൽ നിന്നും ക്രിട്ടിക്കൽ പെർകൊലേഷൻ സാധ്യതാ അക്കങ്ങളുടെ ശരാശരി മനസ്സിലാക്കുന്നു.

അവലംബം

http://coursera.cs.princeton.edu/algs4/assignments/percolation.html