The Mathematics of P vs NP by hemant pandey - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

10.  ALGORITHM/ HEURISTICS FOR FINDING THE SHORTEST ROUTE

 

image036.jpgStep 1: Find the largest outer mesh which has maximum points lying on a SCP.

 

Step 2: Using a+b - c’ rule find the points which belong to this network in the sense that they are nearer to the net work than themselves.

 

Step 3: Find the other networks in which points are nearer to themselves. Step4: By repeated application of step 1, 2 , 3, find all such networks. Step5: Apply the case of hypothetical diagonals to get a shorter route. Step5: Join these networks by segment to segment rule i.e. a+ b-c-d’ rule. Step6: Apply segment test to get further reduction.