现在的位置: 首页 > 综合 > 正文

NP难Packing 问题的拟人拟物算法C#实现 NP难Packing 问题的拟人拟物算法C#实现

2019年05月03日 ⁄ 综合 ⁄ 共 9950字 ⁄ 字号 小 中 大 ⁄ 评论关闭

NP难Packing 问题的拟人拟物算法C#实现

分类： NP问题 C#2011-10-19
00:19 47人阅读 评论(0) 收藏 举报
界面很简单，只有一个"Button1"按钮，按下按钮后，自动开始移动大圆容器内的小圆，到局部最小值如果不满足条件，则为势能最大或势能最小的圆寻找一个随机位置重新进行计算和移动圆的位置，该算法的思想来自于黄文奇、许如初编写的《近世计算理论导引----NP难问题的背景、前景及其解算法研究》 Page 62。

[csharp] view
plaincopy

  1. using System;  
  2. using System.IO;  
  3. using System.Collections;  
  4. using System.Collections.Generic;  
  5. using System.ComponentModel;  
  6. using System.Data;  
  7. using System.Drawing;  
  8. using System.Linq;  
  9. using System.Text;  
  10. using System.Windows.Forms;  
  11. using System.Threading;  
  12. // Form1.cs  Packing Problem   
  13. namespace PackingOb1  
  14. {  
  15.     public partial class Form1 : Form  
  16.     {  
  17.         // 势能  
  18.         // 渐进移动的步长  
  19.         double Step;  
  20.         Circle[] circles = new Circle[10];  
  21.         StreamReader sr = new StreamReader("circles1.txt");  
  22.         string line;  
  23.         int Num;  
  24.         string[] r_str = new string[100];  
  25.         string[] co_str = new string[200];  
  26.         double[] radius = new double[100];  
  27.         PointF[] cordinates = new PointF[100];  
  28.         public Form1()  
  29.         {  
  30.             InitializeComponent();  
  31.         }  
  32.         void DrawCircle(Circle circle)  
  33.         {  
  34.             Graphics g = Graphics.FromHwnd(this.Handle);  
  35.             g.TranslateTransform(this.Width / 2, this.Height / 2);  
  36.             g.DrawEllipse(new Pen(Color.Black), new RectangleF((float)(circle.x - circle.r), (float)(circle.y - circle.r), (float)(2 * circle.r), (float)(2 * circle.r)));  
  37.             g.Dispose();  
  38.         }  
  39.         void ReadStream(StreamReader sr)  
  40.         {  
  41.             line = sr.ReadLine();  
  42.             Num = Convert.ToInt32(line);  // This is a Covert Class  
  43.             line = sr.ReadLine();  
  44.             r_str = line.Split(new char[] { ' ' }); // Pay attention to the use of the Split  
  45.             for (int i = 0; i < Num; i++)  
  46.             {  
  47.                 radius[i] = Convert.ToDouble(r_str[i]);  
  48.             }  
  49.             line = sr.ReadLine();  
  50.             co_str = line.Split(new char[] { ' ' });  
  51.             for (int i = 0; i < Num; i++)  
  52.             {  
  53.                 cordinates[i].X = (float)Convert.ToDouble(co_str[2 * i]);  
  54.                 cordinates[i].Y = (float)Convert.ToDouble(co_str[2 * i + 1]);  
  55.             }  
  56.   
  57.   
  58.         }  
  59.         private void Form1_Load(object sender, EventArgs e)  
  60.         {  
  61.             // 将数据从文本文件中读取出来，创建圆形  
  62.             ReadStream(sr);  
  63.             for (int i = 0; i < Num; i++)  
  64.             {  
  65.                 circles[i] = new Circle();  
  66.                 circles[i].r = radius[i];  
  67.                 circles[i].x = cordinates[i].X;  
  68.                 circles[i].y = cordinates[i].Y;  
  69.             }  
  70.   
  71.   
  72.   
  73.         }  
  74.         /// <summary>  
  75.         /// 计算整个系统的势能,同时计算最大势能的点max_PE和最小势能的点min_PE  
  76.         /// </summary>  
  77.         double calc_PE(Circle[] circles, ref Circle maxPE_circle, ref Circle minPE_circle)  
  78.         {  
  79.             double PE = 0;  
  80.             // 计算前，将以前的计算结果清零！！！  
  81.             for (int i = 1; i < Num; i++)  
  82.             {  
  83.                 circles[i].dx = 0;  
  84.                 circles[i].dy = 0;  
  85.                 circles[i].PE = 0;  
  86.             }  
  87.             calc_dx_dy(circles);  
  88.             for (int i = 1; i < Num; i++)  
  89.             {  
  90.                 PE += circles[i].PE;  
  91.             }  
  92.             maxPE_circle = minPE_circle = circles[1];  
  93.             for (int i = 2; i < Num; i++)  
  94.             {  
  95.                 maxPE_circle = maxPE_circle.PE < circles[i].PE ? circles[i] : maxPE_circle;  
  96.                 minPE_circle = minPE_circle.PE > circles[i].PE ? circles[i] : minPE_circle;  
  97.             }  
  98.             return PE;  
  99.         }  
  100.         /// <summary>  
  101.         /// 统计所有圆的dx 与dy   
  102.         /// </summary>  
  103.         void calc_dx_dy(Circle[] circles)  
  104.         {  
  105.             for (int i = 1; i < Num; i++)  
  106.             {  
  107.                 MoveDirection(circles[i], Num, circles, i);  
  108.             }  
  109.         }  
  110.         /// <summary>  
  111.         /// 计算每个圆要移动的方向  
  112.         /// </summary>  
  113.         /// <param name="circle"></param>  
  114.         /// <param name="Num"></param>  
  115.         /// <param name="numth"></param>  
  116.         void MoveDirection(Circle circle, int Num, Circle[] circles, int numth)  
  117.         {  
  118.             for (int i = 0; i < Num; i++)  
  119.             {  
  120.                 // 考虑与第0个圆的距离  
  121.                 if (i == 0)  
  122.                 {  
  123.                     double d0i = Math.Sqrt(circle.x * circle.x + circle.y * circle.y);  
  124.                     if (d0i + circle.r > circles[i].r)  
  125.                     {  
  126.                         circle.dx += circle.x / d0i * (d0i + circle.r - circles[i].r);  
  127.                         circle.dy += circle.y / d0i * (d0i + circle.r - circles[i].r);  
  128.                         circle.PE += Math.Pow(d0i + circle.r - circles[i].r, 2.0);  
  129.                     }  
  130.                 }  
  131.                 // 考虑容器内与其他圆的距离  
  132.                 else if (numth != i)  
  133.                 {  
  134.                     double dij = Math.Sqrt(Math.Pow(circle.x - circles[i].x, 2.0) + Math.Pow(circle.y - circles[i].y, 2.0));  
  135.                     if (dij < circle.r + circles[i].r)  
  136.                     {  
  137.                         circle.dx += (circles[i].x - circle.x) / dij * (circle.r + circles[i].r - dij);  
  138.                         circle.dy += (circles[i].y - circle.y) / dij * (circle.r + circles[i].r - dij);  
  139.                         circle.PE += Math.Pow(circle.r + circles[i].r - dij, 2.0);  
  140.                     }  
  141.                 }  
  142.             }  
  143.         }  
  144.   
  145.         private void Form1_Paint(object sender, PaintEventArgs e)  
  146.         {  
  147.   
  148.             for (int i = 0; i < Num; i++)  
  149.             {  
  150.                 DrawCircle(circles[i]);  
  151.             }  
  152.         }  
  153.         /// <summary>  
  154.         /// 单击，圆开始移动  
  155.         /// </summary>  
  156.         /// <param name="sender"></param>  
  157.         /// <param name="e"></param>  
  158.         private void button1_Click(object sender, EventArgs e)  
  159.         {  
  160.             Step = 0.1;  
  161.             Circle oldmaxPE = circles[0];  
  162.             Circle maxPE = circles[1];  
  163.             Circle minPE = circles[1];  
  164.             double New_PE;  
  165.             double Old_PE = 0;  
  166.             int t = 0;  
  167.             while (true)  
  168.             {  
  169.                 if (Step >= 0.001)  
  170.                 {  
  171.                     New_PE = calc_PE(circles, ref maxPE, ref minPE);  
  172.                     if (New_PE < 0.0001)  
  173.                     {  
  174.                         return;  
  175.                     }  
  176.                     else if (New_PE < Old_PE)  
  177.                     {  
  178.                         Old_PE = New_PE;  
  179.                         for (int i = 1; i < Num; i++)  
  180.                         {  
  181.                             circles[i].x -= Step * circles[i].dx;  
  182.                             circles[i].y -= Step * circles[i].dy;  
  183.                         }  
  184.                         Invalidate();  
  185.                         Update();  
  186.                         //Thread.Sleep(10);  
  187.                     }  
  188.                     else if (New_PE >= Old_PE)  
  189.                     {  
  190.                         Old_PE = New_PE;  
  191.                         Step = 0.8 * Step;  
  192.                         for (int i = 0; i < Num; i++)  
  193.                         {  
  194.                             circles[i].x -= Step * circles[i].dx;  
  195.                             circles[i].y -= Step * circles[i].dy;  
  196.                         }  
  197.                         Invalidate();  
  198.                         Update();  
  199.                         //Thread.Sleep(10);  
  200.                     }  
  201.                 }  
  202.                 else  
  203.                 {  
  204.                     if (maxPE == oldmaxPE)  
  205.                     {  
  206.                         t = t + 1;  
  207.                     }  
  208.                     if (t < 1)  
  209.                     {  
  210.                         // 在圆盘上随机选点，重新摆放势能最大的圆  
  211.                         // 注意此时的maxPE 和 oldmaxPE均指向old_Circles中的对象。  
  212.                         Random rand = new Random();  
  213.                         maxPE.x = -circles[0].r + 2 * circles[0].r * rand.NextDouble();  
  214.                         maxPE.y = -circles[0].r + 2 * circles[0].r * rand.NextDouble();  
  215.                         oldmaxPE = maxPE;  
  216.                         Step = 0.1;  
  217.                     }  
  218.                     else if (t == 1)  
  219.                     {  
  220.                         Random rand = new Random();  
  221.                         minPE.x = -circles[0].r + 2 * circles[0].r * rand.NextDouble();  
  222.                         minPE.y = -circles[0].r + 2 * circles[0].r * rand.NextDouble();  
  223.                         t = 0;  
  224.                         oldmaxPE = circles[0];  
  225.                         Step = 0.1;  
  226.                     }  
  227.                 }  
  228.             }  
  229.         }  
  230.     }  
  231.     /// <summary>  
  232.     /// 一个圆 接受坐标(x, y)和半径r  
  233.     /// </summary>  
  234.     public class Circle  
  235.     {  
  236.         // 圆的坐标  
  237.         public double x;  
  238.         public double y;  
  239.         // 圆的半径  
  240.         public double r;  
  241.         // 要移动的方向  
  242.         public double dx;  
  243.         public double dy;  
  244.         public double PE;  
  245.         /// <summary>  
  246.         /// 创建一个圆（不用参数）  
  247.         /// </summary>  
  248.         public Circle()  
  249.         {  
  250.             this.dx = 0;  
  251.             this.dy = 0;  
  252.             this.PE = 0;  
  253.         }  
  254.         /// <summary>  
  255.         /// 创建一个圆  
  256.         /// </summary>  
  257.         /// <param name="x"></param>  
  258.         /// <param name="y"></param>  
  259.         /// <param name="r"></param>  
  260.         public Circle(double x, double y, double r)  
  261.         {  
  262.             this.x = x;  
  263.             this.y = y;  
  264.             this.r = r;  
  265.             this.dx = 0;  
  266.             this.dy = 0;  
  267.             this.PE = 0;  
  268.         }  
  269.         /// <summary>  
  270.         /// 拷贝复制该Circle  
  271.         /// </summary>  
  272.         /// <returns>返回Circle</returns>  
  273.         public Circle Clone()  
  274.         {  
  275.             Circle clone_Circle = new Circle();  
  276.             clone_Circle.x = this.x;  
  277.             clone_Circle.y = this.y;  
  278.             clone_Circle.r = this.r;  
  279.             clone_Circle.dx = this.dx;  
  280.             clone_Circle.dy = this.dy;  
  281.             clone_Circle.PE = this.PE;  
  282.             return clone_Circle;  
  283.         }  
  284.     }  
  285. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞