注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简单代码

寻找代码的灵魂

 
 
 

日志

 
 
关于我

对于本博客内所有原创文章和代码的引用必须标明“来源:http://simplesource.blog.163.com/”。如需应用于商业目的必须经本人同意,本人对所有原创文章和代码保留一切权利。 PS:需要部分程序源代码的请留下邮箱地址

网易考拉推荐

利用递归实现不定重数多重循环(附源代码)  

2007-07-16 10:17:39|  分类: 我的程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

利用递归实现不定重数多重循环(附源代码)


  很多情况下我们要实现的程序本身并不复杂但却很烦琐,这里举一个穷举的例子。多数穷举程序需要遍历多个循环点,我们遇到的情况经常是:变量a的变化范围是aMin~aMax,在a的每个取值上b又要从bMin~bMax全都遍历一遍……如果是只有a,b两个变量那实现起来当然方便,只需如下代码即可:
for(a = aMin; a < aMax; a += da)
{
  for(b = bMin; b < bMax; b += db)
  {
    // do some thing
    ...
  }
}
  但是如果循环点比较多,甚至是一个数组呢?你会说这好办,只要:
for(a = aMin; a < aMax; a += da)
{
  for(b = bMin; b < bMax; b += db)
  {
    for(c = cMin; c < cMax; c += dc)
    {
      for(d = dMin; d < bMax; d += dd)
      {
        for(e = eMin; e < eMax; e += de)
        {
          for(f = fMin; f < fMax; f += df)
          {
            ...
          }
        }
      }
    }
  }
}
  ……也许可行吧……
  不过,这篇文章要向大家推荐一种更为方便的方法——递归。
  递归,说白了就是自己调用自己的函数。利用递归这种特殊的机制,我们可以把上面大量重复的代码化繁为简。具体实现方法可以参考以下模型:
bool Recursion(int index, int min, int max)
{
  for(int i = min; i <= max; i++)
  {
    if(index == 0)
    {
      // 在这里添加搜索代码,如果要中途终止搜索,则返回true
      ...
      return true or false;
    }
    else
    {
      if(Recursion(index - 1, min, max))
      {
        // 收到搜索终止信号,直接跳出
        return true;
      }
    }
  }
  return true;
}

  这里index表示调用的层数,可以用来在一开始调用这个函数时控制多重循环的重数,min和max是每重循环的搜索范围,可以根据实际需要写出每重循环的搜索范围都不同的多重循环。
  当然这个只是最一般的模型,可以根据实际问题的需要进行变化。例如,如果min和max不会变化,可以在程序中写死;index也可以从0开始到特定值时结束。
  下面举一个实际的例子:
  以下这段代码实现了在城市数目较少的情况下,利用穷举法解决旅行商问题(tsp)(城市数目较多的情况可以参考我的另一篇文章《用遗传算法解决旅行商问题(附源代码)》)。这个程序在我的笔记本上运行11个或以下城市的tsp用时小于1秒,12个城市的tsp需要5~7秒,还是可以接受的。城市再多,已经没有什么实际意义,顶多还可以作为教学试验。不过城市数量较少的情况下穷举法也是一种非常具有竞争力的算法,至少它求出来的是确切全局最优解。
#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <time.h>
#include <conio.h>
#define MAX_NUM    20
double s_citys[MAX_NUM][2];
double s_distances[MAX_NUM][MAX_NUM];
int s_num = 0;
double s_min = 1e200;
int s_indexMin[MAX_NUM];
int s_index[MAX_NUM];
bool s_mark[MAX_NUM];

bool ReadFile()
{
  FILE * fp = fopen("citys.txt", "r");
  if(fp)
  {
    s_num = 0;
    while(!feof(fp) && s_num < MAX_NUM)
    {
      fscanf(fp, "%lf, %lf\n", &s_citys[s_num][0], &s_citys[s_num][1]);
      s_num++;
    }
    fclose(fp);
    return true;
  }
  return false;
}
void Search(int index)
{
  int i, j;
  double sum;
  for(i = 1; i < s_num; i++)
  {
    if(s_mark[i])
    {
      s_index[index] = i;
      s_mark[i] = false;
      if(index == s_num - 1)
      {
        sum = 0.0;
        for(j = 0;j < s_num - 1; j++)
        {
          sum += s_distances[s_index[j]][s_index[j + 1]];
        }
        sum += s_distances[s_index[s_num - 1]][s_index[0]];
        if(sum < s_min)
        {
          memcpy(s_indexMin, s_index, sizeof(s_index));
          s_min = sum;
        }
      }
      else
      {
        Search(index + 1);
      }
      s_mark[i] = true;
    }
  }
}

void WriteFile()
{
  FILE * fp = fopen("result.txt", "w");
  if(fp)
  {
    for(int i = 0; i < s_num; i++)
    {
      fprintf(fp, "%d\n", s_indexMin[i]);
    }
    fclose(fp);
  }
}

void main()
{
  int i, j;
  if(ReadFile())
  {
    time_t start, end;
    double timeUsed;
    time(&start);
    printf("开始穷举,请等待...");
    for(i = 1; i < s_num; i++)
    {
      for(j = 0; j < i; j++)
      {
        s_distances[i][j] =
          sqrt(
          (s_citys[i][0] - s_citys[j][0]) * (s_citys[i][0] - s_citys[j][0]) +
          (s_citys[i][1] - s_citys[j][1]) * (s_citys[i][1] - s_citys[j][1]));
        s_distances[j][i] = s_distances[i][j];
      }
    }
    s_min = 1e200;
    s_index[0] = 0;
    memset(s_mark, true, sizeof(s_mark));
    s_mark[0] = false;
    Search(1);
    time(&end);
    timeUsed = difftime(end, start);
    if(timeUsed < 1.0)
    {
      printf("\n用时小于1秒!\n");
    }
    else
    {
      printf("\n用时%.0lf秒!\n", timeUsed);
    }
    printf("\n最短行程%lf\n", s_min);
    printf("最佳访问序列:\n");
    for(int i = 0; i < s_num; i++)
    {
      printf("%02d\n", s_indexMin[i]);
    }
    WriteFile();
    printf("按任意键继续...");
    getch();
  }
  else
  {
    printf("读取文件失败");
  }
}

  程序的输入是一个名为citys.txt的文本文件,里面记录了城市的坐标(一般默认坐标的范围为(0.0,0.0)~(1.0,1.0))。输出是一个名为result.txt的文本文件,里面记录了最佳旅行路线所经过的城市序号顺序(城市序号为0~n-1,n为城市数目)。下面是这两个文件的一个样例:
citys.txt
0.930000, 0.620000
0.590000, 0.870000
0.430000, 0.440000
0.560000, 0.480000
0.050000, 0.300000
0.740000, 0.860000
0.130000, 0.210000
0.070000, 0.380000
0.690000, 0.120000
0.970000, 0.430000
0.850000, 0.730000
0.800000, 0.360000
result.txt
0
9
11
8
6
4
7
2
3
1
5
10
  以上是程序核心部分,我又写了一个程序为之服务,程序执行效果如图:

利用递归实现不定重数多重循环(附源代码) - 简单代码 - 简单代码利用递归实现不定重数多重循环(附源代码) - 简单代码 - 简单代码利用递归实现不定重数多重循环(附源代码) - 简单代码 - 简单代码利用递归实现不定重数多重循环(附源代码) - 简单代码 - 简单代码
  程序下载:small_tsp.rar

      small_tsp.rar(mofile)

  评论这张
 
阅读(2191)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018