Hilbert希尔伯特曲线的非递归算法

posted at 2022.12.16 13:14 by Administrator

有些问题使用递归算法进行求解更容易理解,例如:计算阶乘、查找斐波那契数、解决棒料切割问题、在汉诺塔中移动圆盘、希尔伯特曲线绘制、八皇后及骑士巡游问题等。

遗憾的是,递归算法有一些不足之处,它虽然容易理解,但其效率却不高。例如生成斐波那契数时会使得计算机速度大大减慢。还有一些递归算法则会导致一系列递归方法的深度调用,从而耗尽调用堆栈,例如使用Warnsdorff启发式方法的骑士巡游问题,对于较大的棋盘会导致调用溢出错误。

幸运的是,我们可以采取一些方法来解决这个问题。

具体是:

一、   尾部递归的删除

该算法首先检查是否需要递归调用自己,或者是否可以简单地返回值1

二、   动态规划(dynamic programming

这项技术在20世纪50年代发明时可能看起来是动态的,但与其他基本上可以随时规划的神经网络、遗传算法和机器学习技术等现代技术相比,它似乎完全是静态的。该算法是在计算时记录中间结果值,这样就不需要重复进行计算。

三、   自底向上编程

即首先计算最小值,然后依次向上计算。

四、   传真(模拟程序在执行递归时所做的操作)

在进行递归调用之前,程序将当前状态的信息存储在调用堆栈中,

然后,当递归返回时,程序将从调用堆栈中弹出保存的信息,以便可以从停止的地方继续执行。

下面使用传真方法,构建非递归的希尔伯特曲线算法。

原始的希尔伯特曲线递归算法的伪代码:

       Hilbert(Integerdepth, Float dx, Float dy)
          if (depth > 0)  Then  Hilbert(depth - 1, dy, dx);
           DrawRelative(dx, dy);
           if (depth > 0)  Then  Hilbert(depth - 1, dx, dy);
           DrawRelative(dy, dx);
           if (depth > 0)  Then  Hilbert(depth - 1, dx, dy);
           DrawRelative(-dx, -dy);
           if (depth > 0)  Then  Hilbert(depth - 1, -dy, -dx);

     End Hilbert

我们将算法分成每次递归调用之前的各个节(section),并将其分别命名为123等。然后,创建一个名为section的变量,该变量指示算法下一步应该执行哪一节。最初将变量设置为1,以便算法从代码的第一节开始。

创建一个While循环,当section大于0时,重复执行。接下来,将算法的所有代码移到While循环中,并将其放入一系列If-Else语句中。使每条If语句将变量section与节编号进行比较,如果匹配,则执行相应代码。当算法进入某一节的代码时,递增变量section,以便算法知道下次循环时执行下一节代码。

当算法通常递归调用自己时,将所有参数的当前值推送到调用堆栈上。另外,将section推送到堆栈上,这样算法在从模拟递归返回时就知道要执行哪一节的代码。更新模拟递归应使用的所有参数。最后,设置section=1,从代码的第一节开始模拟递归调用。

具体C#代码:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
using System.Drawing.Drawing2D;
 
namespace Hilbert
{
    Public  partialclassForm1 : Form
    {
        public  Form1()
        {
            InitializeComponent();
        }
        privatevoid drawButton_Click(object sender, EventArgs e)
        {
            Bitmap bm = new Bitmap(
                hilbertPictureBox.ClientSize.Width,
                hilbertPictureBox.ClientSize.Height);
            using (Graphics gr = Graphics.FromImage(bm))
            {
                gr.SmoothingMode = SmoothingMode.AntiAlias;
                gr.Clear(Color.White);
                constint margin = 10;
                int depth = (int)depthNumericUpDown.Value;
                float dx = (float)((bm.Width - 2 * margin) / (Math.Pow(2, depth + 1) - 1));
                CurrentX = margin;
                CurrentY = margin;
                HilbertN(depth, gr, dx, 0);
            }
            hilbertPictureBox.Image = bm;
        }
        // The current position.
        privatefloat CurrentX, CurrentY;
        //绘制希尔伯特曲线
        privatevoid HilbertN(int depth, Graphics gr, float dx, float dy)
        {
            // 创建堆栈存储递归前的信息
            Stack<int> sections=new Stack<int>();
            Stack<int> depths=new Stack<int>();
            Stack<float> dxs=new Stack<float>();
            Stack<float> dys = new Stack<float>();
            //确定接下来执行哪一节的代码
            int section = 1;
            while (section > 0)
            {
                if(section==1)
                {
                    section++;
                    if(depth > 0)
                    {
                        sections.Push(section);
                        depths.Push(depth);
                        dxs.Push(dx);
                        dys.Push(dy);
                        depth--;
                        float temp = dx;
                        dx = dy;
                        dy = temp;
                        section=1;
                    }
                }
                elseif(section==2)
                {
                    DrawRelative(gr,dx,dy);
                    section++;
                    if (depth > 0)
                    {
                        sections.Push(section);
                        depths.Push(depth);
                        dxs.Push(dx);
                        dys.Push(dy);
                        depth--;
                        section = 1;
                    }
                }
                elseif (section == 3)
                {
                    DrawRelative(gr, dy, dx);
                    section++;
                    if (depth > 0)
                    {
                        sections.Push(section);
                        depths.Push(depth);
                        dxs.Push(dx);
                        dys.Push(dy);
                        depth--;
                        section = 1;
                    }
                }
                elseif (section == 4)
                {
                    DrawRelative(gr, -dx, -dy);
                    section++;
                    if (depth > 0)
                    {
                        sections.Push(section);
                        depths.Push(depth);
                        dxs.Push(dx);
                        dys.Push(dy);
                        depth--;
                        float temp = dx;
                        dx = -dy;
                        dy = -temp;
                        section = 1;
                    }
                }
                elseif (section == 5)
                {   //89级曲线几乎填充整个计算机屏幕,不再递归
//从递归返回
                    //如果没有任何数据弹出,则表明已到了栈顶
                    if (sections.Count == 0)
                    {
                        section = -1;
                    }
                    else
                    {
                        //弹出之前的参数
                        section=sections.Pop();
                        depth=depths.Pop();
                        dx=dxs.Pop();
                        dy=dys.Pop();
                    }
 
                }
            }
        }
        privatevoid Form1_Load(object sender, EventArgs e)
        {
        }
        // Draw starting at the indicated point and update x and y.
        privatevoid DrawRelative(Graphics gr, float dx, float dy)
        {
            gr.DrawLine(Pens.Blue,
            CurrentX, CurrentY,
             CurrentX + dx, CurrentY + dy);
            CurrentX += dx;
            CurrentY += dy;
        }
    }
}
namespace Hilbert
{
    staticclassProgram
    {
        [STAThread]
        staticvoid Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
        }
    }

} 

 

效果图:

 

Tags: ,

IT技术

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading